Thinking Functionally with Haskell勉強メモ: 第４章３ zipWithとmerge sortの実装

zipWith

ふたつのリストから一要素ずつ取って関数を適用するzipWith関数：

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith f _ _ = []

この定義はちょっと面白い。再帰を書く場合、いつも停止条件を最初に書く作法でやっているのだが、停止条件が最後にきて、しかもdon't care記法なので、「最初の条件にマッチしなければ再帰終了」というロジックが非常に簡潔に記述できる。

zipWithは便利で、例えばリストが小さい順に並んでいるか判定するnondec関数をこのように表記できる：

nondec :: (Ord a) => [a] -> Bool
nondec xs = and (zipWith (<=) xs (tail xs))

これはPythonでも

def nondec(xs): 
  return all(x < y for x, y in zip(xs, xs[1:]))

と書きたくなる。

Merge sort実装

sort :: (Ord a) => [a] -> [a]
sort [] = []
sort [x] = [x]
sort xs = merge (sort ys) (sort zs)
          where (ys, zs) = halve xs

halve :: [a] -> ([a], [a])
halve xs = (take n xs, drop n xs)
           where n = length xs `div` 2
           
merge :: (Ord a) => [a] -> [a] -> [a]
merge [] xs = xs
merge xs [] = xs
merge xs'@(x:xs) ys'@(y:ys)
  | x <= y    = x : merge xs ys'
  | otherwise = y : merge xs' ys

これはすごく綺麗だ。まさに宣言的なコード、という感じがする。