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 は非正格だから、リスト全体をたどる必要（それも２回も）のある前者よりも後者のほうが効率がいいのかも。