練習問題 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