リストの畳み込みと展開

リストの畳み込みには、foldr が使われる。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _  ini []     = ini
foldr op ini (x:xs) = x `op` foldr op ini xs

Data.List には、この双対となる関数 unfoldr が定義してある。

unfoldr :: (a -> Maybe (b,a)) -> a -> [b]
unfoldr f x = case f x of
  Nothing -> []
  Just (z,x') -> z : unfoldr f x'

unfoldr は種からリストを生成する。

既存の関数

unfoldr をプリミティブと考えて、他の関数を定義してみる。まずは、iterate。

iterate :: (a -> a) -> a -> [a]
iterate f = unfoldr (\x -> Just (x, f x))

次は repeat。

repeat :: a -> [a]
repeat x = unfoldr (\y -> Just (y, y)) x

map は、入力がリストなので foldr で定義できる。

map :: (a -> b) -> [a] -> [b]
map f = foldr (\y ys -> f y : ys) []

また、出力がリストなので unfoldr でも定義できる。

map :: (a -> b) -> [a] -> [b]
map f = unfoldr go
  where
    go []     = Nothing
    go (x:xs) = Just (f x, xs)

ソート

挿入ソートは畳み込みで実現できる。

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x yys@(y:ys)
  | x < y     = x:yys
  | otherwise = y:insert x ys

isort :: Ord a => [a] -> [a]
isort = foldr insert []

選択ソートは、展開で定義できる。

select :: Ord a => [a] -> Maybe (a,[a])
select [] = Nothing
select xs = Just (x, delete x xs)
  where
    x = minimum xs

ssort :: Ord a => [a] -> [a]
ssort = unfoldr select

バブルソートも、展開で定義できる。泡はリストの末尾から先頭に向かって移動することに注意。

bubble :: Ord a => [a] -> Maybe (a,[a])
bubble = foldr go Nothing
  where
    go x Nothing  = Just (x,[])
    go x (Just (y,ys))
      | x < y     = Just (x,y:ys)
      | otherwise = Just (y,x:ys)

bsort :: Ord a => [a] -> [a]
bsort = unfoldr bubble

おまじない

import Data.List (delete)
import Prelude hiding (iterate, repeat, map, foldr)