Por que essa implementação é uma instância incorreta do Foldable Typeclass?

Jan 02 2021

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 foldMape 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 foldMapo 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 foldablelote de teste do QuickCheck , recebo algumas falhas. Alterar minha foldrimplementaçã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 foldfunção ing que QuickCheck está usando.

Questões:

  1. Por que as falhas estão ocorrendo?
  2. Existe uma maneira de obter a função usada no teste pelo QuickCheck?

Respostas

4 duplode Jan 02 2021 at 06:30

foldrpode ser obtido foldMap usando o Endomonóide , com a a -> b -> bfunção transformando avalores em b -> bfunçõ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 foldrdeve 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 foldrcomo 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. .

3 DDub Jan 02 2021 at 05:40

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 Showas funções geradas pelo quickcheck para mais informações.

A maneira de obter Showfunçõ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 foldablefunção onde você usa o tipo Fun a bno lugar de a -> be applyFunconforme necessário para aplicar as funções.

2 javinor Jan 02 2021 at 03:00

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.