Por que essa implementação é uma instância incorreta do Foldable Typeclass?
Estou trabalhando no maravilhoso livro de Haskell . No final do capítulo Traversable (21), preciso escrever uma instância para a seguinte Árvore:
data Tree a =
Empty
| Leaf a
| Node (Tree a) a (Tree a)
Aqui está um link para o código completo da minha solução. Os exercícios recomendam tentar implementar ambos foldMap
e foldr
. É assim que implementei foldr
(sem pensar muito na ordem de invocação):
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
Em seguida, implementei foldMap
o seguinte:
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) =
foldMap f left <> f x <> foldMap f right
Quando executo o foldable
lote de teste do QuickCheck , recebo algumas falhas. Alterar minha foldr
implementação para o seguinte faz todos os testes passarem:
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
Tentei executar o caso de teste com falha sozinho, mas não consegui recriar a falha:
*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}
Suspeito que há algo que não estou descobrindo sobre a fold
função ing que QuickCheck está usando.
Questões:
- Por que as falhas estão ocorrendo?
- Existe uma maneira de obter a função usada no teste pelo QuickCheck?
Respostas
foldr
pode ser obtido foldMap
usando o Endomonóide , com a a -> b -> b
função transformando a
valores em b -> b
funções que podem ser (monoidalmente) compostas. Sendo assim, se o seu 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
... o correspondente foldr
deve ser:
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 (.)
Se arrumarmos um pouco ...
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)
... obtemos a definição correta de foldr
como está escrito em sua pergunta. Como a diferença entre as implementações tem a ver com a ordem de composição, experimentar um monóide não comutativo prontamente leva a um caso de falha, como você descobriu .
Na subquestão QuickCheck, adio a resposta de DDub. .
Como você já deduziu, o motivo de estar obtendo falhas é porque as duas implementações são distinguíveis, o que você pode observar usando um monóide não comutativo.
Obter a função usada pelo quickcheck não é tão simples. Veja, por exemplo, esta pergunta / resposta sobre Show
as funções geradas pelo quickcheck para mais informações.
A maneira de obter Show
funções capazes dentre QuickCheck é envolver a função no o Funtipo . Dito isso, o código que você está chamando ( encontrado aqui ) apenas usa funções diretamente, então elas nunca podem ser mostradas. Uma opção que você pode tentar é criar sua própria versão da foldable
função onde você usa o tipo Fun a b
no lugar de a -> b
e applyFun
conforme necessário para aplicar as funções.
Acabei de perceber que usei um monóide comutativo ... Consegui recriar a falha usando um monóide não comutativo:
> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}
Este é provavelmente um caso simples. Eu imagino que em código de produção com tipos de dados reais isso possa ser muito mais complicado.