snocリストを作ってみよう。

30分プログラム、その597。snocリストを作ってみよう。

普通、リストは

data List a = Cons a (List a) | Nil

と定義するところを逆に

data List a = Snoc (List a) a | Nil

と定義したsnoc listというものがあるらしいです。

普通のリストと逆なので、末尾への要素追加がO(1)で、先頭への要素追加がO(n)になります。あとおもしろいことに、foldrが末尾再帰で定義できたりします。
というわけで、これを作ってみよう。

使い方

-- 普通のリストからsnocリストを作る
*Main> fromList [1,2,3]
Snoc (Snoc (Snoc Nil 1) 2) 3

-- map
*Main> Main.map (+1) $ fromList [1, 2, 3]
Snoc (Snoc (Snoc Nil 2) 3) 4

ソースコード

data List a = Snoc (List a) a| Nil deriving (Show,Eq)

snoc :: List a -> a -> List a
last :: List a -> a
init :: List a -> List a
head :: List a -> a
tail :: List a -> List a
fromList :: [a] -> List a
map   :: (a -> b) -> List a -> List b
length :: List a -> Int
foldr :: (a -> b -> b) -> b -> List a -> b
foldl :: (a -> b -> a) -> a -> List b -> a

fromList xs = aux Nil xs
    where aux xs []     = xs
          aux xs (y:ys) = aux (Snoc xs y) ys

snoc xs x = Snoc xs x

last Nil = error "empty list"
last (Snoc _ x) = x

init Nil = error "empty list"
init (Snoc xs _) = xs

head Nil = error "empty list"
head (Snoc Nil x) = x
head (Snoc xs _)  = Main.head xs

tail Nil = error "empty list"
tail (Snoc Nil x) = Nil
tail (Snoc xs x)  = Snoc (Main.tail xs) x

map _ Nil = Nil
map f (Snoc xs x) = Snoc (Main.map f xs) (f x)

length Nil = 0
length (Snoc xs _) = 1 + Main.length xs

foldr f init Nil = init
foldr f init (Snoc xs x) = Main.foldr f (f x init) xs

foldl f init Nil = init
foldl f init (Snoc xs x) = f (Main.foldl f init xs) x

参考

• 過去の30分プログラム