Arantium Maestum

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

Thinking Functionally with Haskell勉強メモ: 第4章問題3

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

zipcrossが以下のように定義されているとする:

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

unzipcrossの型は?:

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

unzipcrossforkなどに関して以下の等式が成り立つ:

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)
= {等式1:cross().fork()=fork()}
fork (map f . map fst, map g . map snd)
= {functor law of map}
fork (map (f . fst), map (g . snd))
= {等式3:fst . cross(f, g) = f . fst}
fork (map (fst . cross (f, g)), map (g . snd))
= {等式4: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)))
= {等式2: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)
= {等式1: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が定義されている型クラスである。crossbimapに非常に近いが、bimapの型は:

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

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

crossbimapを使って定義すると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