この実装がFoldableTypeclassの悪いインスタンスであるのはなぜですか?

Jan 02 2021

私は素晴らしいHaskellBookに取り組んでいます。Traversableの章(21)の終わりに、次のツリーのインスタンスを作成する必要があります。

data Tree a =
    Empty
  | Leaf a
  | Node (Tree a) a (Tree a)

これが私のソリューションの完全なコードへのリンクです。演習では、との両方を実装することをお勧めfoldMapfoldrます。これは私が実装した方法です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}

foldQuickCheckが使用しているing関数について、私が理解していないことがあるのではないかと思います。

質問:

  1. なぜ障害が発生しているのですか?
  2. QuickCheckによるテストで使用される関数を取得する方法はありますか?

回答

4 duplode Jan 02 2021 at 06:30

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の回答に従います。。

3 DDub Jan 02 2021 at 05:40

すでに推測したように、失敗する理由は、2つの実装が区別できるためです。これは、非可換モノイドを使用して観察できます。


クイックチェックで使用する関数を取得するのはそれほど簡単ではありません。もう少し詳しい情報については、たとえば、クイックチェックによって生成されたing関数に関するこの質問/回答を参照してShowください。

取得する方法ShowQuickCheckのうち、可能な機能は、関数をラップすることであるタイプ。とは言うものの、あなたが呼び出しているコード(ここにあります)は関数を直接使用しているだけなので、それらを表示することはできません。試すことができる1つのオプションは、関数の代わりに、必要に応じて関数を適用するために型を使用する独自のバージョンの関数を作成することです。FunfoldableFun a ba -> bapplyFun

2 javinor Jan 02 2021 at 03:00

可換モノイドを使用していることに気づきました...非可換モノイドを使用して障害を再現することができました。

> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}

これはおそらく単純なケースです。実際のデータ型を使用する本番コードでは、これははるかに複雑になる可能性があると思います。