Почему эта реализация - плохой экземпляр Foldable Typeclass?
Я работаю над замечательной книгой 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.
Вопросы:
- Почему случаются сбои?
- Есть ли способ получить функцию, используемую в тесте с помощью QuickCheck?
Ответы
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. .
Как вы уже поняли, вы получаете сбои потому, что эти две реализации различимы, что вы можете наблюдать, используя некоммутативный моноид.
Получить функцию, используемую quickcheck, не так-то просто. См., Например, этот вопрос / ответ о Show
функциях, созданных с помощью quickcheck, для получения дополнительной информации.
Способ получить Show
способные функции из QuickCheck является обернуть функцию по Funтипу . Тем не менее, код, который вы вызываете ( найденный здесь ), просто использует функции напрямую, поэтому они никогда не могут быть показаны. Один из вариантов, который вы можете попробовать, - создать свою собственную версию foldable
функции, в которой вы будете использовать тип 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)})}
Это, наверное, простой случай. Я полагаю, что в производственном коде с реальными типами данных это может быть намного сложнее.