月: 2016年9月

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つのリスト(の要素)を交互に混ぜる) – 分室の分室

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

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

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 には省略可能な引数 delim と grammer があった。

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

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

(define my-string-join
  (case-lambda
    ((slist) (my-string-join slist " "))
    ((slist delim)
    (apply string-append (intersperse delim slist)))))

(print (my-string-join '("foo" "bar" "baz")))
(print (my-string-join '("foo" "bar" "baz") "-"))
takatoh@apostrophe $ gosh my-string-join.scm
foo bar baz
foo-bar-baz

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

(define my-string-join
  (case-lambda
    ((slist) (my-string-join slist " " 'infix))
    ((slist delim) (my-string-join slist delim 'infix))
    ((slist delim grammer)
      (let ((l (intersperse delim slist)))
        (cond ((eq? grammer 'infix) (apply string-append l))
              ((eq? grammer 'prefix) (apply string-append (cons delim l)))
              ((eq? grammer 'suffix) (apply string-append (append l (list delim))))
              (else (error "Illegal grammer.")))))))

(print (my-string-join '("foo" "bar" "baz")))
(print (my-string-join '("foo" "bar" "baz") "-"))
(print (my-string-join '("foo" "bar" "baz") "/" 'prefix))
(print (my-string-join '("foo" "bar" "baz") ";" 'suffix))
(print (my-string-join '("foo" "bar" "baz") ";" 'surfix)) ;; misspell
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]

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

module Main where

intersperse :: a -> [a] -> [a]
intersperse _ (x:[]) = x : []
intersperse y (x:xs) = x : y : intersperse y xs

main :: IO ()
main = print $ intersperse 0 [1..3]
takatoh@apostrophe $ runhaskell intersperse.hs
[1,0,2,0,3]

素直な再帰関数だ。

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

(define my-intersperse
  (lambda (delim lis)
    (let loop ((l (cdr lis)) (r (list (car lis))))
      (if (null? l)
        (reverse r)
        (loop (cdr l) (cons (car l) (cons delim r)))))))

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

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

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

(define my-intersperse
  (lambda (delim lis)
    (reverse (fold (lambda (x acc) (cons x (cons delim acc)))
      (list (car lis))
        (cdr lis)))))

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

同様に Haskell で。

module Main where

intersperse :: a -> [a] -> [a]
intersperse y xs = reverse $ foldl f [head xs] (tail xs)
  where
    f acc a = a : y : acc

main :: IO ()
main = print $ intersperse 0 [1..3]
takatoh@apostrophe $ runhaskell intersperse2.hs
[1,0,2,0,3]

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

string-reverse

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

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

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

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

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

(define string-reverse
  (case-lambda
    ((s) (string-reverse s 0 (string-length s)))
    ((s start) (string-reverse s start (string-length s)))
    ((s start end)
      (let loop ((c 0) (l (string->list s)) (r '()))
        (cond ((= c end) (list->string r))
              ((< c start) (loop (+ c 1) (cdr l) r))
              (else (loop (+ c 1) (cdr l) (cons (car l) r))))))))

(print (string-reverse "abcdefg"))
(print (string-reverse "abcdefg" 3))
(print (string-reverse "abcdefg" 3 5))
takatoh@apostrophe $ gosh string-reverse.scm
gfedcba
gfed
ed