¿Por qué esta implementación es una mala instancia de la clase de tipo plegable?

Jan 02 2021

Estoy trabajando en el maravilloso libro Haskell . Al final del capítulo Traversable (21), necesito escribir una instancia para el siguiente árbol:

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

Aquí hay un enlace al código completo de mi solución. Los ejercicios recomiendan intentar implementar ambos foldMapy foldr. Así es como lo implementé foldr(sin pensar mucho en el orden de invocación):

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

Luego implementé de la foldMapsiguiente manera:

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

Cuando ejecuto el foldablelote de prueba de QuickCheck , obtengo algunas fallas. Cambiar mi foldrimplementación a lo siguiente hace que todas las pruebas pasen:

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

Intenté ejecutar el caso de prueba fallido por mi cuenta, pero no pude recrear el fallo:

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

Sospecho que hay algo que no estoy averiguando sobre la foldfunción ing que está usando QuickCheck.

Preguntas:

  1. ¿Por qué ocurren las fallas?
  2. ¿Hay alguna forma de que QuickCheck utilice la función en la prueba?

Respuestas

4 duplode Jan 02 2021 at 06:30

foldrse puede obtener foldMap utilizando el Endomonoide , con la a -> b -> bfunción convirtiendo avalores en b -> bfunciones que se pueden componer (monoidalmente). Siendo eso así, si tu foldMapes ...

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

... el correspondiente foldrdebe 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 (.)

Si lo arreglamos un poco ...

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)

... obtenemos la definición correcta de foldrcomo está escrito en su pregunta. Como la diferencia entre las implementaciones tiene que ver con el orden de composición, probar un monoide no conmutativo conduce fácilmente a un caso fallido, como ha descubierto .

En la subpregunta QuickCheck, me someto a la respuesta de DDub. .

3 DDub Jan 02 2021 at 05:40

Como ya dedujo, la razón por la que tiene fallas es porque las dos implementaciones son distinguibles, lo que puede observar usando un monoide no conmutativo.


Obtener la función utilizada por quickcheck no es tan simple. Consulte, por ejemplo, esta pregunta / respuesta sobre Showlas funciones de ing generadas por quickcheck para obtener un poco más de información.

La forma de obtener Showfunciones capaces de QuickCheck es envolver la función en el Funtipo . Dicho esto, el código que está llamando (que se encuentra aquí ) solo usa funciones directamente, por lo que nunca se pueden mostrar. Una opción que puede probar es crear su propia versión de la foldablefunción en la que use el tipo Fun a ben lugar de a -> by applyFunsegún sea necesario para aplicar las funciones.

2 javinor Jan 02 2021 at 03:00

Me acabo de dar cuenta de que usé un Monoide conmutativo ... Pude recrear la falla usando un Monoide no conmutativo:

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

Probablemente este sea un caso simple. Me imagino que en el código de producción con tipos de datos reales esto podría ser mucho más complicado.