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

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)]

となる。時間はかかるが・・・

Arantium Maestum

プログラミング、囲碁、読書の話題