¿Por qué esta implementación es una mala instancia de la clase de tipo plegable?
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 foldMap
y 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 foldMap
siguiente 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 foldable
lote de prueba de QuickCheck , obtengo algunas fallas. Cambiar mi foldr
implementació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 fold
función ing que está usando QuickCheck.
Preguntas:
- ¿Por qué ocurren las fallas?
- ¿Hay alguna forma de que QuickCheck utilice la función en la prueba?
Respuestas
foldr
se puede obtener foldMap
utilizando el Endomonoide , con la a -> b -> b
función convirtiendo a
valores en b -> b
funciones que se pueden componer (monoidalmente). Siendo eso así, si tu foldMap
es ...
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 foldr
debe 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 foldr
como 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. .
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 Show
las funciones de ing generadas por quickcheck para obtener un poco más de información.
La forma de obtener Show
funciones 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 foldable
función en la que use el tipo Fun a b
en lugar de a -> b
y applyFun
según sea necesario para aplicar las funciones.
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.