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