Haskellでリフル・シャッフル

こないだのリフル・シャッフルを Haskell でやってみた。

Prelude> concat $ zip [0,2,4,6,8] [1,3,5,7,9]

:2:10:
    Couldn't match type `(a1, b0)' with `[a0]'
    Expected type: [[a0]]
      Actual type: [(a1, b0)]
    In the return type of a call of `zip'
    In the second argument of `($)', namely
      `zip [0, 2, 4, 6, ....] [1, 3, 5, 7, ....]'
    In the expression:
      concat $ zip [0, 2, 4, 6, ....] [1, 3, 5, 7, ....]

あれ。そうか、zip はタプルのリストを返すんだっけ。

Prelude> zip [0,2,4,6,8] [1,3,5,7,9]
[(0,1),(2,3),(4,5),(6,7),(8,9)]

じゃあ、foldr を使ってみようか。

Prelude> foldr (\(x,y) acc -> x:y:acc) [] $ zip [0,2,4,6,8] [1,3,5,7,9]
[0,1,2,3,4,5,6,7,8,9]

うまくいった。
いや、zipWith のほうがいいか?

Prelude> concat $ zipWith (\x y -> x:y:[]) [0,2,4,6,8] [1,3,5,7,9]
[0,1,2,3,4,5,6,7,8,9]

riffle-shuffle

「リフル・シャッフルとは、カードの山札を半分ずつに分けて、パラパラと交互に重ねていくトランプ札の切り方を言う」んだそうで。

 cf. riffle-shuffle (2つのリスト(の要素)を交互に混ぜる) – 分室の分室

詳しくはリンク先を見てもらうとして、要は2つのリストの要素を交互に混ぜようってことだ(て、リンクのタイトルに書いてあるじゃん)。

まあ、ベタに書こうと思うとリンク先のようなコードになるんだろうけど、ここは用意されている便利な手続きを使って:

gosh> (use srfi-1)
#<undef>
gosh> (concatenate (zip '(0 2 4 6 8) '(1 3 5 7 9)))
(0 1 2 3 4 5 6 7 8 9)

てなかんじで、どうっスか。

string-join

intersperse があれば string-join は簡単だ。デリミタを差し込んだ文字列のリストに string-append を適用してやればいい。

gosh> (apply string-append (intersperse "-" '("foo" "bar" "baz")))
"foo-bar-baz"

と、思ったら string-join には省略可能な引数 delimgrammer があった。

 cf. 6.12 文字列 – Gauche ユーザリファレンス

delim はデリミタで、省略すると空白文字1文字が使われる。

takatoh@apostrophe $ gosh my-string-join.scm
foo bar baz
foo-bar-baz

grammer は手続きの挙動を決めるためのシンボルで、infixstrict-infixprefixsuffix のいずれか。
今回、strict-infix は面倒そうだったのでそれ以外を実装してみた。

takatoh@apostrophe $ gosh my-string-join3.scm
foo bar baz
foo-bar-baz
/foo/bar/baz
foo;bar;baz;
gosh: "error": Illegal grammer.

intersperse

Haskell の Data.List モジュールに intersperse という関数がある。リストの要素の間に値を挿入する関数だ。

Prelude> import Data.List
Prelude Data.List> intersperse 0 [1..3]
[1,0,2,0,3]

これを自前で実装するとこうなる。

takatoh@apostrophe $ runhaskell intersperse.hs
[1,0,2,0,3]

素直な再帰関数だ。

Scheme ではどうだろうか。実は Gauche には intersperse が用意されているんだけど、自前で実装してみたらこうなった。

takatoh@apostrophe $ gosh my-intersperse.scm
(1 0 2 0 3)

Haskell のと違って末尾再帰になっているのは、まあ、それが身についていると言ってもいいのかな。

さて、ここまで書いてみて畳み込みが使えそうだと気がついた。

takatoh@apostrophe $ gosh my-intersperse2.scm
(1 0 2 0 3)

同様に Haskell で。

takatoh@apostrophe $ runhaskell intersperse2.hs
[1,0,2,0,3]

Haskell の場合は foldl を使うよりも、単純な再帰のほうが見やすい気がする。それに Haskell は非正格だから、リスト全体をたどる必要(それも2回も)のある前者よりも後者のほうが効率がいいのかも。

string-reverse

SRFI-13 に string-reverse という手続きがある。その名のとおり、文字列を逆順にする手続きだ。

gosh> (use srfi-13)
#<undef>
gosh> (string-reverse "abcdefg")
"gfedcba"

で、何故か省略可能な引数が2つあって、逆順にするときの始端と終端を指定できる(逆順になった部分文字列が返ってくる)。

gosh> (string-reverse "abcdefg" 3)
"gfed"
gosh> (string-reverse "abcdefg" 3 5)
"ed"

これを自分で作ってみた。こないだの case-lambda の練習。

takatoh@apostrophe $ gosh string-reverse.scm
gfedcba
gfed
ed

リストから要素を間引きする

真ん中優先。真ん中がないときは右側優先。

^o^ > gosh thin-out.scm
(0 1 2 3 4 5 6 7 8 9)
(0 1 2 3 4 6 7 8 9)
(0 1 2 3 6 7 8 9)
(0 1 2 3 7 8 9)

リストのn番目の要素を削除する

最初の要素は0番目。

^o^ > gosh delete-nth.scm
(0 1 2 3 4 5 6 7 8 9)
(0 1 2 4 5 6 7 8 9)
(a b c d e f g h i j)
(a b c e f g h i j)

ちゃんと 3 と d が消えている。

これを拡張して、「n番目」を複数とれるようにしてみよう。

^o^ > gosh delete-nth2.scm
(0 1 2 3 4 5 6 7 8 9)
(0 1 2 4 6 8 9)
(a b c d e f g h i j)
(a b c e g i j)

要素がリストに含まれているか否かを判定する述語が見当たらなかったので、include? を自作した。

整数のリストを作る(2)-あるいは省略可能な引数の扱いについて

先週のエントリを見て省略可能な引数を扱う方法を書いてくれた人がいる。

 cf. 省略可能引数 – 主題のない日記

そこでは、R6RS/R7RS で定められている case-lambda と Gauche の拡張である let-optionals* が紹介されている。どちらも省略可能な引数を簡単に扱うためのマクロのようだ。

my-iotacase-lambda を使って書くとこうなる。

ついでに step に負数を指定すると期待通りに動作しない不具合も直しておいた。
実行例:

^o^ > gosh my-iota4a.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)
(2 0 -2 -4 -6 -8 -10 -12 -14 -16)

一方、let-optionals* を使って書くとこんな感じ:

^o^ > gosh my-iota4b.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)
(2 0 -2 -4 -6 -8 -10 -12 -14 -16)

当然ながら実行結果はどちらも同じだけど、どちらかというと case-lambda のほうが好みだな。引数の数でパターンマッチしてる感じがいい。let-optionals* だと省略可能引数の部分だけ別に書くことになるのでコードの見通しが悪いような気がする。

Gauche のマニュアルだと、case-lambdahttp://practical-scheme.net/gauche/man/gauche-refj_24.html の一番下、let-optionals*http://practical-scheme.net/gauche/man/gauche-refj_58.html6.18.4 省略可能引数のパージング にある。

整数のリストを作る

たまには Scheme を。

Scheme で整数のリストを作るには iota 手続きが使える。

^o^ > gosh
gosh> (iota 10)
(0 1 2 3 4 5 6 7 8 9)
gosh> (iota 10 2)
(2 3 4 5 6 7 8 9 10 11)
gosh> (iota 10 2 2)
(2 4 6 8 10 12 14 16 18 20)

これを自前で実装してみよう。
最初に作ったのがこれ。可変長引数なので、引数の数に応じて対応する補助手続きを呼び出している。

実行例:

^o^ > gosh my-iota.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)

上の実装では3つの補助手続きを定義しているけど、内容は同じようなものなので1つにまとめることにした。つまり、引数を3つとる補助手続き my-iota-general を定義しておいて、本体手続き my-iota のほうで場合分けをして呼び出す。

^o^ > gosh my-iota2.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)

だいぶシンプルになった。もう一歩進めてみよう。上の my-iota 手続きの中では場合分けをして my-iota-general の引数 start、step を決めているので、let で局所変数にしてしまえば my-iota-general の本体部分を取り込むことができる。

^o^ > gosh my-iota3.scm
(0 1 2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9 10 11)
(2 4 6 8 10 12 14 16 18 20)

めでたく1つの手続きにできた。

逆関数法で指数分布する乱数を生成する

[0,1)区間の一様乱数から、指数分布にならう乱数を生成するには、逆関数法というのが使える。
指数分布の密度関数は、パラメータをτとすると:
f(\tau)=\lambda e^{-\lambda\tau}
であり、分布関数 g(τ) は:
g(\tau)=\int^\tau_{-\infty}{\lambda e^{-\lambda\tau}}d\tau=1-e^{-\lambda\tau}
となる。g(τ)は 0~1 の値をとるので、この逆関数:
\tau=-\frac{1}{\lambda}log(1-g(\tau))
の g(τ) の代わりに一様乱数を入力してやれば、τ は指数分布する乱数になる。

じゃあ Ruby でやってみよう。

λ=0.5とし、10000個の乱数を発生させている。
これを Excel でグラフ化したのがこれ。
expon
「指数分布」の曲線は、上に書いた密度関数の曲線を、スケールを合わせるために8000倍して描いている。乱数はちゃんと指数分布になっているようだ。

参考にしたページ:
 cf. http://www.ishikawa-lab.com/montecarlo/4shou.html