Perché questa implementazione è una cattiva istanza di Foldable Typeclass?

Question

Sto lavorando al meraviglioso Libro Haskell . Alla fine del capitolo Traversable (21), ho bisogno di scrivere un'istanza per il seguente albero:

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

Ecco un collegamento al codice completo della mia soluzione. Gli esercizi consigliano di provare a implementare sia foldMape foldr. Ecco come ho implementato foldr(senza riflettere molto sull'ordine di chiamata):

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

Ho quindi implementato foldMapcome segue:

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 eseguo il foldablebatch di prova di QuickCheck , ottengo alcuni errori. La modifica della mia foldrimplementazione nel modo seguente fa passare tutti i test:

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

Ho provato a eseguire il test case non riuscito da solo, ma non sono riuscito a ricreare l'errore:

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

Ho il sospetto che ci sia qualcosa che non sto cercando di capire sulla foldfunzione ing che QuickCheck sta utilizzando.

Domande:

1. Perché si verificano guasti?
2. C'è un modo per ottenere la funzione utilizzata nel test da QuickCheck?

Answer 1

foldrpuò essere ottenuto foldMap utilizzando il Endomonoide , con la a -> b -> bfunzione che trasforma i avalori in b -> bfunzioni che possono essere composte (monoidalmente). Stando così le cose, se il tuo 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

... il corrispondente foldrdeve essere:

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 riordiniamo un po '...

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)

... otteniamo la definizione corretta di foldrcome scritto nella tua domanda. Poiché la differenza tra le implementazioni ha a che fare con l'ordine di composizione, provare un monoide non commutativo porta prontamente a un caso fallito, come hai scoperto .

Sulla domanda secondaria QuickCheck, rimando alla risposta di DDub. .

Answer 2

Come hai già dedotto, il motivo per cui stai riscontrando errori è perché le due implementazioni sono distinguibili, cosa che puoi osservare utilizzando un monoide non commutativo.

---

Ottenere la funzione utilizzata da quickcheck non è così semplice. Vedi, ad esempio, questa domanda / risposta sulle Showfunzioni generate da quickcheck per qualche informazione in più.

Il modo per ottenere Showfunzioni capaci di QuickCheck è quello di avvolgere la funzione del Funtipo . Detto questo, il codice che stai chiamando ( che trovi qui ) utilizza direttamente le funzioni, quindi non possono mai essere mostrate. Un'opzione che potresti provare è creare la tua versione della foldablefunzione in cui usi il tipo Fun a bal posto di a -> be applyFunsecondo necessità per applicare le funzioni.

Answer 3

Mi sono appena reso conto di aver utilizzato un Monoide commutativo ... Sono stato in grado di ricreare il guasto utilizzando un Monoide non commutativo:

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

Questo è probabilmente un caso semplice. Immagino che nel codice di produzione con tipi di dati reali questo potrebbe essere molto più complicato.