練習問題 4.2.13

連接はリスト上の基本操作であるように見えるので，連接をプリミティブとしてデータ型を構成してみよう． たとえば，

data CatList a = Nil | Wrap a | Cat (CatList a) (CatList a)
とする． 
Nil
は 
[]
， 
Wrap x
は 
[x]
， 
Cat xs ys
は 
xs++ys
をそれぞれ表すためのものである．しかし， 
++
は結合性のある演算子なので，以下の2つの式は等しいとみなすべきである． 



Cat xs (Cat ys zs) と Cat (Cat xs ys) zs


CatList

について

Eq

クラスのインスタンスと

Ord

クラスのインスタンスを適切に定義せよ．






toList :: CatList a -> [a]
toList Nil      = []
toList (Wrap x) = [x]
toList (Cat Nil ys) = toList ys
toList (Cat (Wrap x) ys) = x : toList ys
toList (Cat (Cat xs xs') ys) = toList xs ++ toList (Cat xs' ys)


instance Eq a => Eq (CatList a) where
  xs == ys = toList xs == toList ys

instance Ord a => Ord (CatList a) where
  xs <= ys = toList xs <= toList ys