Thinking Functionally with Haskell勉強メモ: 第4章問題1
Exercise A
null :: [a] -> Bool null [] = True null _ = False
という定義を
null = (==[])
と変えても大丈夫か?という問題。
実際使ってみると大丈夫そうなのだが:
Prelude> null = (==[]) Prelude> null [] True Prelude> null [1] False Prelude> null [True] False Prelude> null [False] False
念のため、型を調べてみる:
Prelude> :t null null :: Eq t => [t] -> Bool
Eq t
という条件が入ってきているのがわかる。つまりリストの要素に「等号で比較可能」という型クラスの指定が入っている。
Eq
のインスタンスではない型を作成してみてnull
にその型の要素を持つリストを渡してみる:
Prelude> data Greek = Alpha | Beta Prelude> null [Alpha] <interactive>:8:1: error: • No instance for (Eq Greek) arising from a use of ‘null’ • In the expression: null [Alpha] In an equation for ‘it’: it = null [Alpha]
これで問題点がはっきりする。リストに対する(==)
は多分処理が「すべての要素が一致する」というものなので、要素自体が等号で比較できなければいけない。
パターンマッチなら大丈夫:
Prelude> :{ Prelude| null :: [a] -> Bool Prelude| null [] = True Prelude| null _ = False Prelude| :} Prelude> null [Alpha] False
というわけで(==[])
には(かなりわかりにくい形で)型クラスの制限が紛れ込んでしまう、というのが問題。
Exercise B
[(0,0), (1, 0), (0, 1) ...]
など、任意のnとmで構成される(n, m)
が有限o個目の要素として出てくるリストを作成する、という問題。
allPairs = [(x, y) | x <- [0..], y <- [0..]]
という問題文に登場する実装だと、[(0,1), (0,2), (0,3) ... (0, n) ...]
と有限個目の要素はすべて(0, m)
の形になる。
oneSidedPairs = [(x, y) | x <- [0..], y <- [0..x]] mirrorPairs :: (Eq a) => [(a, a)] -> [(a, a)] mirrorPairs [] = [] mirrorPairs ((x, y):xys) | x == y = (x, y) : mirrorPairs xys | otherwise = (x, y) : (y, x) : mirrorPairs xys allPairs = mirrorPairs oneSidedPairs
というふうに、yの上限をxの値までにすればいい。
Exercise C
二つのソートされたリストに同じ要素が含まれているか判定する関数disjoint
を定義せよ:
disjoint :: (Ord a) => [a] -> [a] -> Bool disjoint [] _ = True disjoint _ [] = True disjoint xs'@(x:xs) ys'@(y:ys) | x == y = False | x < y = disjoint xs ys' | otherwise = disjoint xs' ys
Exercise D
以下の二つのリストが同一である条件は:
[e | x <- xs, p x, y <- ys] [e | x <- xs, y <- ys, p x]
実際には結果が同一でない条件の方が厳しい。
[e | x <- [0..], y <- (if x == 5 then [0..] else [0..5]), (>5) x]
といった場合、つまりp x
が成り立たない場合にys
が無限になるケースがあり、その後に来る結果を隠してしまう状況だと不一致になる。
結果は同一になりやすいが、計算時間は大きく違ってくる。前者はp x
が成り立たない場合そもそもy <- ys
が抜けるので、そのループ部分は評価されない。後者は二重ループを評価してからフィルタしているようなイメージ。
Exercise E
a^3+b^3=c^3+d^3=x
でa,b
がc,d
とは違うという条件で最小のx
は1729だという事実に関連したラマヌジャンの逸話がある。他のx
の値を小さい順に算出せよ。
cubeSums = [ (x, a, b, c, d) | x <- [1..], a <- (takeWhile (\a -> a^3 < x) [1..]), b <- (takeWhile (\b -> a^3 + b^3 <= x) [a..]), a^3 + b^3 == x, c <- (takeWhile (\c -> c^3 < x) [a+1..]), d <- (takeWhile (\d -> c^3 + d^3 <= x) [c..]), c^3 + d^3 == x]
これで結果が
Prelude> take 5 cubeSums [(1729,1,12,9,10),(4104,2,16,9,15),(13832,2,24,18,20),(20683,10,27,19,24),(32832,4,32,18,30)]
となる。時間はかかるが・・・