この実装がFoldableTypeclassの悪いインスタンスであるのはなぜですか?
私は素晴らしいHaskellBookに取り組んでいます。Traversableの章(21)の終わりに、次のツリーのインスタンスを作成する必要があります。
data Tree a =
Empty
| Leaf a
| Node (Tree a) a (Tree a)
これが私のソリューションの完全なコードへのリンクです。演習では、との両方を実装することをお勧めfoldMap
しfoldr
ます。これは私が実装した方法ですfoldr
(呼び出し順序をあまり考慮せずに):
foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) =
f x $ foldr f (foldr f z left) right
次にfoldMap
、次のように実装しました。
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) =
foldMap f left <> f x <> foldMap f right
QuickCheckのfoldable
テストバッチを実行すると、いくつかの失敗が発生します。foldr
実装を次のように変更すると、すべてのテストに合格します。
foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) =
foldr f (f x (foldr f z right)) left
失敗したテストケースを自分で実行しようとしましたが、失敗を再現できませんでした。
*Ch21_12_ExercisesTree Data.Monoid> tree = Node (Node (Leaf (-5)) 3 (Node (Leaf 3) 5 Empty)) (-2) Empty
*Ch21_12_ExercisesTree Data.Monoid> foldr (<>) (mempty :: Sum Int) t
Sum {getSum = 4}
*Ch21_12_ExercisesTree Data.Monoid> foldMap Sum t
Sum {getSum = 4}
fold
QuickCheckが使用しているing関数について、私が理解していないことがあるのではないかと思います。
質問:
- なぜ障害が発生しているのですか?
- QuickCheckによるテストで使用される関数を取得する方法はありますか?
回答
foldr
得ることができるfoldMap
使用して、Endoモノイドを用いて、a -> b -> b
機能が旋回a
に値をb -> b
(monoidally)構成することができる機能。そうです、もしあなたfoldMap
が...
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) =
foldMap f left <> f x <> foldMap f right
...対応するものfoldr
は次のとおりです。
foldr f z Empty = id z -- mempty amounts to id
foldr f z (Leaf x) = (f x) z
foldr f z (Node left x right) =
((\e -> foldr f e left) . f x . (\e -> foldr f e right)) z -- (<>) amounts to (.)
それを少し片付ければ...
foldr f z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) =
foldr f (f x (foldr f z right)) left)
...私たちfoldr
はあなたの質問に書かれているように正しい定義を取得します。実装間の違いは構成の順序に関係しているため、非可換モノイドを試してみると、ご存知のように、失敗するケースにすぐにつながります。
QuickCheckサブ質問については、DDubの回答に従います。。
すでに推測したように、失敗する理由は、2つの実装が区別できるためです。これは、非可換モノイドを使用して観察できます。
クイックチェックで使用する関数を取得するのはそれほど簡単ではありません。もう少し詳しい情報については、たとえば、クイックチェックによって生成されたing関数に関するこの質問/回答を参照してShow
ください。
取得する方法Show
QuickCheckのうち、可能な機能は、関数をラップすることであるタイプ。とは言うものの、あなたが呼び出しているコード(ここにあります)は関数を直接使用しているだけなので、それらを表示することはできません。試すことができる1つのオプションは、関数の代わりに、必要に応じて関数を適用するために型を使用する独自のバージョンの関数を作成することです。Funfoldable
Fun a b
a -> b
applyFun
可換モノイドを使用していることに気づきました...非可換モノイドを使用して障害を再現することができました。
> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}
これはおそらく単純なケースです。実際のデータ型を使用する本番コードでは、これははるかに複雑になる可能性があると思います。