Thinking Functionally with Haskell勉強メモ: 第６章問題４
Exercise K
第一部
takePrefix pをリストxsに適用すると、xsの頭から連続してpを満たし続ける最も長いセグメントを返す。
takePrefix :: ([a] -> Bool) -> [a] -> [a]
takePrefix nondec [1, 3, 7, 6, 8, 9] = [1, 3, 7] -- リストの先頭から上がり続ける最長のセグメント takePrefix (all even) [2, 4, 7, 8] = [2, 4]
次の式の右辺を定義せよ：
takePrefix (all p) = takeWhile p
takePrefixをinitsを使って定義せよ：
takePrefix p = last . takeWhile p . inits
実はこの問題、模範解答では
takePrefix p = last . filter p . inits
となっているが、これだとpartial listや無限リストの場合takePrefixは有限リストを返すのに対して、この定義だとundefinedになってしまう。例えば
takePrefix (==1) [1..]
が反例になるので間違いだと思う。
第二部
以下の関数が定義されているとする：
one x = [x] none x = []
以下の式の右辺を完成させよ：
none . f = none map f . none = none map f . one = one . f
第三部
fork (f, g) x = (f x, g x)であることを踏まえて以下の式を完成させよ：
fst . fork (f, g) = f snd . fork (f, g) = g fork (f, g) . h = fork (f . h, g . h)
第四部
testが以下のように定義されている：
test p (f, g) x = if p x then f x else g x
以下の式を完成させよ：
test p (f, g) . h = test (p . h) (f . h, g . h) h . test p (f, g) = test p (h . f, h . g)
filterが以下のように定義されている：
filter p = concat . map (test p (one, none))
以下の等式が成り立つことを証明せよ：
filter p = map fst . filter snd . map (fork (id, p))
右辺を変換していく：
map fst . filter snd . map (fork (id, p)) = {filter p = concat . map (test p (one, none))} map fst . concat . map (test snd (one, none)) . map (fork (id, p)) = {map f . concat = concat . map (map f)} concat . map (map fst) . map (test snd (one, none)) . map (fork (id, p)) = {functor law of map} concat . map (map fst . test snd (one, none) . fork (id, p)) = {test p (f, g) . h = test (p . h) (f . h, g . h)} concat . map (map fst . test (snd . fork (id, p)) (one . fork (id, p), none . fork (id, p))) = {none . f = none} concat . map (map fst . test (snd . fork (id, p)) (one . fork (id, p), none)) = {snd . fork (f, g) = g} concat . map (map fst . test p (one . fork (id, p), none)) = {h . test p (f, g) = test p (h . f, h . g)} concat . map (test p (map fst . one . fork (id, p), map fst . none)) = {map f . none = none} concat . map (test p (map fst . one . fork (id, p), none)) = {map f . one = one . f} concat . map (test p (one . fst . fork (id, p), none)) = {fst . fork (f, g) = f} concat . map (test p (one . id, none)) = {f . id = f} concat . map (test p (one, none)) = {filter p = concat . map (test p (one, none))} filter p
証明終わり。
第五部
以下の式を完成させよ：
map (fork (f, g)) = uncurry zip . fork (map f, map g)
第六部
以下の式をfがO(n)回だけ適用されるような式に変換せよ：
takePrefix (p . foldl f e)
これは模範解答に出てきた多分間違っているtakePrefixの定義を使って変換することになる。
takePrefix (p . foldl f e) = {takePrefixの定義} last . filter (p . foldl f e) . inits = {filter p = map fst . filter snd . map (fork (id, p))} last . map fst . filter snd . map (fork (id, (p . foldl f e))) . inits = {map (fork (f, g)) = uncurry zip . fork (map f, map g)} last . map fst . filter snd . uncurry zip . fork (map id, map (p . foldl f e)) . inits = {fork (f, g) . h = fork (f . h, g . h)} last . map fst . filter snd . uncurry zip . fork (map id . inits, map (p . foldl f e) . inits) = {map id . f = id . f = f} last . map fst . filter snd . uncurry zip . fork (inits, map (p . foldl f e) . inits) = {functor law of map} last . map fst . filter snd . uncurry zip . fork (inits, map p . map (foldl f e) . inits) = {foldl f e . inits = scanl f e} last . map fst . filter snd . uncurry zip . fork (inits, map p . scanl f e)
scanlの性質上、fは引数の要素数ごとに（すなわちO(n)）適用される。
多分以下が成り立つので：
takeWhile p = map fst . takeWhile snd . map (fork (id, p))
私が考えるtakePrefixの正しい定義でも：
last . map fst . takeWhile snd . uncurry zip . fork (inits, map p . scanl f e)
となってO(n)が成立すると思う。がtakeWhileの性質については証明していない。
