Почему эта реализация - плохой экземпляр Foldable Typeclass?

Jan 02 2021

Я работаю над замечательной книгой Haskell . В конце главы о проходимости (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

Когда я запускаю foldableтестовый пакет QuickCheck , я получаю несколько сбоев. При изменении моей 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функции ing, которую использует QuickCheck.

Вопросы:

  1. Почему случаются сбои?
  2. Есть ли способ получить функцию, используемую в тесте с помощью QuickCheck?

Ответы

4 duplode Jan 02 2021 at 06:30

foldrможет быть получен с foldMap помощью Endoмоноида , когда a -> b -> bфункция превращает aзначения в b -> bфункции, которые могут быть (моноидально) составлены. В таком случае, если ваш 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

Как вы уже поняли, вы получаете сбои потому, что эти две реализации различимы, что вы можете наблюдать, используя некоммутативный моноид.


Получить функцию, используемую quickcheck, не так-то просто. См., Например, этот вопрос / ответ о Showфункциях, созданных с помощью quickcheck, для получения дополнительной информации.

Способ получить Showспособные функции из QuickCheck является обернуть функцию по Funтипу . Тем не менее, код, который вы вызываете ( найденный здесь ), просто использует функции напрямую, поэтому они никогда не могут быть показаны. Один из вариантов, который вы можете попробовать, - создать свою собственную версию foldableфункции, в которой вы будете использовать тип Fun a bвместо a -> bи по applyFunмере необходимости для применения функций.

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)})}

Это, наверное, простой случай. Я полагаю, что в производственном коде с реальными типами данных это может быть намного сложнее.