ようこそ。睡眠不足なプログラマのチラ裏です。

F#でsleep sort

プログラミング F#2.0 F# アルゴリズム 息抜き

追記しました


元ネタは、以下あたり。


常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream
http://d.hatena.ne.jp/gfx/20110519/1305810786


Sleep sortの各言語での実装まとめ – Yuyak
http://www.yuyak.com/1339



ただいま流行っている sleep sort です。
既出かもしれませんが、せっかく書いたので置いておきます。

open System.Collections.Concurrent
let sleepSort f s =
  let q = new ConcurrentQueue<'a> ()
  seq {for x in s ->
         async { do! Async.Sleep((f:'a -> int) >> ( * ) 100 <| x)
                 q.Enqueue x }
      } |> Async.Parallel |> Async.RunSynchronously |> ignore
  q :> seq<'a>
             
["5";"3";"6";"3";"6";"3";"1";"4";"7"] |> sleepSort int |> Seq.iter (printf "%s,")
System.Console.ReadLine () |> ignore


いろんな書き方があると思うけど、一応F#らしさをプンプン匂わせてみたつもり。




追記:シグネチャ ファイルも書こう！


あ、シグネチャ ファイルって、実はあんまし書いたことなかったですよ^^;
ということで、せっかくなので書いておきます。


SleepSort.fsi

namespace Sort

[<AutoOpen>]
module Sort = 
  val sleepSort : ('a -> int) -> seq<'a> ->  seq<'a>

SleepSort.fs

namespace Sort

[<AutoOpen>]
module Sort = 
  open System.Collections.Concurrent
  let sleepSort f s =
    let q = new ConcurrentQueue<'a> ()
    seq {for x in s ->
            async { do! Async.Sleep((f:'a -> int) >> ( * ) 100 <| x)
                    q.Enqueue x }
        } |> Async.Parallel |> Async.RunSynchronously |> ignore
    q :> seq<'a>
             
  ["5";"3";"6";"3";"6";"3";"1";"4";"7"] |> sleepSort int |> Seq.iter (printf "%s,")
  System.Console.ReadLine () |> ignore

これでよいかな？



追記:よいシグネチャ ファイルは、よいドキュメントでもある


ぜんぜん勝ててなかったorz... なるほど。勉強になります。
ホッピーうまいですよね！ということで、コメントと引数名をさらに追記しました。


SleepSort.fsi

namespace Sort

[<AutoOpen>]
module Sort = 

  /// 定義であり、ドキュメントにもなる。ここで、関数に対する熱き思いをぶつけるといい。
  /// 常識を覆すソートアルゴリズム！その名も"sleep sort"！のシグネチャです。
  val sleepSort : projection:('T -> int) -> source:seq<'T> -> seq<'T>

SleepSort.fs

namespace Sort

[<AutoOpen>]
module Sort = 
  open System.Collections.Concurrent

  /// 常識を覆すソートアルゴリズム！その名も"sleep sort"！をしちゃいます。
  let sleepSort f s =
    let q = new ConcurrentQueue<'a> ()
    seq {for x in s ->
            async { do! Async.Sleep(f >> ( * ) 100 <| x)
                    q.Enqueue x }
        } |> Async.Parallel |> Async.RunSynchronously |> ignore
    q :> seq<'a>
             
  ["5";"3";"6";"3";"6";"3";"1";"4";"7"] |> sleepSort int |> Seq.iter (printf "%s,")
  System.Console.ReadLine () |> ignore


という具合に、引数名を変えてもOKだし、ジェネリックの型名を'Tから'aに変えても問題ない、と。
そして、f の型についてはシグネチャファイルに定義してあるので省略可能になる、と。
こんどこそ、これで勝つる！


追記：シグネチャ ファイルを自動生成しよう


シグネチャファイル(.fsi)をよしなに自動生成したあとに、自分でいろいろ追記すればよい、と。
でも、大幅にコードの構成を変えた場合はやり直し。それはちょっとツライね。