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

Exercise J

以下のものの意味を考え、間違っているものを見つけよ：

map f . take n = take n . map f

リストの先頭からからn個の要素を取ってfを適用するのと、リストのすべての要素にfを適用してできた新しいリストの先頭からn個の要素を取るのは等しい。正しい。

map f . reverse = reverse . map f

リストを逆順にしてすべての要素にfを適用するのと、リストのすべての要素にfを適用してから逆順にするのは等しい。正しい。

map f . sort = sort . map f

リストをソートしてからすべての要素にfを適用するのと、リストの要素すべてにfを適用してからソートするのは等しい。間違い。a < bだからf a < f bとは限らないため。

map f . filter p = map fist . filter snd . map (fork (f, p))
fork :: (a -> b, a -> c) -> a -> (b, c)
fork (f, g) x = (f x, g x)

forkは二つの関数のtupleとひとつのナニカ（これって何て呼ぶべきなんだろう？オブジェクト？要素？）を引数にとり、そのナニカに二つの関数適用した結果をtupleとして返す。

あるリストを関数pでフィルタして、残った要素すべてにfを適用するのは、そのリストの各要素にfが適用された結果とpが適用された結果のtupleのリストをtupleの第二要素でフィルタして第一要素だけ取り出すのと等しい。正しい。

filter (p . g) = map (invertg) . filter p . map g
invertg . g = id

あるリストを、各要素にgとpをその順に適用した結果でフィルタするのは、そのリストの全要素にgを適用しpでフィルタしてからgの逆関数を残った要素すべてに適用するのと等しい。正しい。

reverse . concat = concat . reverse . map reverse

あるリストを統合してから逆順にするのは、そのリストの要素の中身を逆順にしてからリスト自体を逆順にして統合するのに等しい。正しい。

filter p . concat = concat . map (filter p)

リストを統合してからpでフィルタするのは、リストの中のリスト一つ一つをpでフィルタしてからすべて統合するのに等しい。正しい。

Exercise K

zipとcrossが以下のように定義されているとする：

unzip = fork (map fst, map snd)
cross (f, g) = fork (f . fst, g . snd)

unzipとcrossの型は？：

unzip :: [(a, b)] -> ([a], [b])
cross :: (a->b, c->d) -> (a, c) -> (b, d)

unzip、cross、forkなどに関して以下の等式が成り立つ：

cross (f, g) . fork (h, k) = fork (f . h, g . k)
fork (f, g) . h = fork (f . h, g . h)
fst . cross (f, g) = f . fst
snd . cross (f, g) = g . snd

上記の等式とfunctor law of mapsを使って

cross (map f, map g) . unzip = unzip . map (cross (f, g))

が成り立つことを証明せよ：

cross (map f, map g) . unzip
= {unzipの定義}
cross (map f, map g) . fork (map fst, map snd)
= {等式１：cross().fork()=fork()}
fork (map f . map fst, map g . map snd)
= {functor law of map}
fork (map (f . fst), map (g . snd))
= {等式３：fst . cross(f, g) = f . fst}
fork (map (fst . cross (f, g)), map (g . snd))
= {等式４：snd . cross(f, g) = g . snd}
fork (map (fst . cross (f, g)), map (snd . cross (f, g)))
= {functor law of map}
fork (map fst . map (cross (f, g)), map snd . map (cross (f, g)))
= {等式２：fork (f, g) . h = fork (f . h, g . h)}
fork (map fst, map snd) . map (cross (f, g))
= {unzipの定義}
unzip . map (cross (f, g))

Exercise L

cross (f, g) . cross (h, k) = cross (f . h, g . k)

を証明せよ：

cross (f, g) . cross (h, k)
= {crossの定義}
cross (f, g) . fork (h . fst, k . snd)
= {等式１：cross() . fork() = fork()}
fork (f . h . fst, g . k . snd)
= {crossの定義}
cross (f . h, g . k)

cross (id, id) = idの理由は？：

cross (id, id) = fork (id . fst, id . snd) = fork (fst, snd)=id

最後の一歩はforkの定義から自明な気がするが証明できていない・・・

Functorが一つの関数をとって要素に適用するfmapが定義されているデータ構造の型クラスだとしたら、Bifunctorは二つの関数をとって要素に適用するbimapが定義されている型クラスである。crossはbimapに非常に近いが、bimapの型は：

bimap :: (a -> c) -> (b -> d) -> bif a b -> bif c d

である。(bifはBifunctorインスタンスの型）

crossをbimapを使って定義するとcross (x, y) = bimap x yになる。

data Either a b = Left a | Right b

という型をBifunctorのインスタンスにしたい場合の定義は：

instance Bifunctor Either where
  bimap (f, g) Left a = f a
  bimap (f, g) Right b = g b