Thinking Functionally with Haskell勉強メモ: 第４章問題２

Exercise F

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

というリストの別定義があったとする。

headとlast関数を定義せよ：

last :: List a -> a
last (Snoc xs x) = x

head :: List a -> a
head (Snoc Nil x) = x
head (Snoc xs x) = head xs

toListとfromListを実装せよ。例えばfromListは

[1, 2, 3] == fromList (Snoc (Snoc (Snoc Nil 1) 2) 3)

となる：

toList :: [a] -> List a
toList = toReverseList . reverse
  where toReverseList [] = Nil
        toReverseList (x:xs) = Snoc (toReverseList xs) x

fromList :: List a -> [a]
fromList = reverse . fromReverseList
  where fromReverseList Nil = []
        fromReverseList (Snoc xl x) = x : fromReverseList xl

Exercise G

length :: [a] -> Int
length [] = 0
length (x:xs) = 1 + length xs

というリストの長さを計算する関数のメモリ量は

length [1, 2, 3] = 1 + (1 + (1 + 0))

のようにO(n)である。それは定義が

length :: [a] -> Int
length xs = loop (0, xs)
  where loop (n, []) = n
        loop (n, (x:xs)) = loop (n+1, xs)

のようにかわっても同じ。何故かというと遅延評価で

length [1, 2, 3] = loop ((((0 + 1) + 1) + 1), [])

となるまで計算されないので、加算処理がO(n)でメモリに積みあがっていく。先行評価ならloopを使う方法だとO(1)になる。

Exercise H

takeとdropの再帰的な定義：

take :: Int -> [a] -> [a]
take _ [] = []
take 0 _ = []
take n (x:xs) = x : take (n-1) xs

drop :: Int -> [a] -> [a]
drop _ [] = []
drop 0 xs = xs
drop n (x:xs) = drop (n-1) xs

この定義だとtake undefined []は[]だがtake 0 undefinedはundefinedになる。なぜならtake _ []とマッチするか確認するためにtake 0 undefinedの二番目の引数を評価しないといけないからだ。

そう考えると、take _ [] = []とtake 0 _ = []の順番を入れ替えることによってtake undefined []とtake 0 undefinedのどちらかを[]にすることはできるが、かならずどちらかはundefinedになる。

splitAt :: Int -> [a] -> ([a], [a])の定義：

splitAt n xs = move n ([] xs)
  where move _ xst@(ys, []) = xst
        move 0 xst = xst
        move n (ys, (z:zs)) = move (n-1) (ys++[z], zs)

ただys++[z]って遅そう・・・

Exercise I

map (f .g) xs = map f (map g xs)

という等式に関して：

• 任意のリストxs (finite, partial, infinite)、任意の（型のあった）関数fとgにおいて成り立つ。なのでmap (f . g) = map f . map gと表すこともできる。
• mapと.の定義から証明されなければいけない
• 右辺から左辺へと変換するのは最適化
• 遅延評価でmapがすべての要素に一気に適用されないとはいえ、二つの遅延リストが存在するより一つだけのほうが効率がいい

といった点が挙げられる。