練習問題 4.1.4
本文のリストと双対になるリストの見方として,リストの後に要素を加えてリストを構成するというものがある.
data Liste a = Nil | Snoc (Liste a) a
Snocはもちろん
Consを逆順に綴ったものである. このようなリストの見方では,
[1,2,3]は以下のような
Liste Intの値として表現されることになる.
Snoc (Snoc (Snoc Nil 1) 2) 3
2つの見方からは全く同じ情報が得られるが,その組み立てられ方は違う. たとえば,空ではないリストの最初の要素を返す関数
headを
[a]型に対して定義するのはやさしい. しかし,これを
Liste aに対して定義するのは複雑である. 2つのリスト型に対して
headを定義せよ. また,一方の型から他方の型への変換を行う関数
convert :: Liste a -> [a]
を定義せよ.
sample :: [Int]
sample = [1,2,3]
sample' :: Liste Int
sample' = Snoc (Snoc (Snoc Nil 1) 2) 3
head :: [a] -> a
head (x:_) = x
head [] = error "head applied empty"
head' :: Liste a -> a
head' (Snoc Nil x) = x
head' (Snoc xs _) = head' xs
head' Nil = error "head' applied empty"
{-
convert xs = conv [] xs
where
conv ys Nil = ys
conv ys (Snoc zs z) = conv (z:ys) zs
-}
convert Nil = []
convert (Snoc xs x) = convert xs ++ [x]
convert' :: [a] -> Liste a
convert' = foldl Snoc Nil