haskell - foldable - Foldr/Foldl gratis cuando Tree está implementando Plegado Plegable?

foldable en español

Question

Soy principiante en Haskell y aprendí de "Learn You a Haskell". Hay algo que no entiendo acerca de la implementación Tree de Pledable.

instance F.Foldable Tree where  
    foldMap f Empty = mempty  
    foldMap f (Node x l r) = F.foldMap f l `mappend`  
                             f x           `mappend`  
                             F.foldMap f r  

Cita de: LYOH: "Entonces, si implementamos foldMap para algún tipo, obtenemos foldr y foldl en ese tipo de forma gratuita ".

¿Alguien puede explicar eso? No entiendo por qué y cómo obtengo foldr y foldl gratis ahora ...

Answer 1

foldr siempre se puede definir como:

foldr f z t = appEndo (foldMap (Endo . f) t) z

donde appEndo y Endo son simplemente desempaquetadores / envoltorios de tipo nuevo. De hecho, este código fue extraído directamente de la clase de tipo Plegable. Por lo tanto, al definir foldMap, automáticamente obtiene foldr.

Answer 2

Comenzamos con el tipo de foldMap :

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

foldMap funciona mapeando la función a -> m sobre la estructura de datos y luego ejecutándola destruyendo los elementos en un solo valor acumulado con mappend .

Luego, notamos que, dado algún tipo b , las funciones b -> b forman un monoide, con (.) Como su operación binaria (es decir, mappend ) y id como el elemento de identidad (es decir, mempty . En caso de que no se haya encontrado aún, id se define como id x = x ). Si tuviéramos que especializar foldMap para ese monoide, obtendríamos el siguiente tipo:

foldEndo :: Foldable t => (a -> (b -> b)) -> t a -> (b -> b)

(Llamé a la función foldEndo porque una función foldEndo es una función de un tipo al mismo tipo).

Ahora, si miramos la firma de la lista foldr

foldr :: (a -> b -> b) -> b -> [a] -> b

podemos ver que foldEndo combina, excepto la generalización de cualquier Foldable y para algunos reordenamientos de los argumentos.

Antes de llegar a una implementación, hay una complicación técnica en que b -> b no se puede convertir directamente en una instancia de Monoid . Para resolver eso, usamos el envoltorio Endo newtype de Data.Monoid en Data.Monoid lugar:

newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

Escrito en términos de Endo , foldEndo es solo foldMap especializado:

foldEndo :: Foldable t => (a -> Endo b) -> t a -> Endo b

Entonces saltaremos directamente a foldr , y lo definiremos en términos de foldMap .

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z

Cuál es la definición predeterminada que puede encontrar en Data.Foldable . El bit más complicado es probablemente Endo . f Endo . f ; si tiene problemas con eso, piense en f no como un operador binario, sino como una función de un argumento con tipo a -> (b -> b) ; luego envolvemos la función end resultante con Endo .

En cuanto a foldl , la derivación es esencialmente la misma, excepto que usamos un monoide diferente de endofunciones, con flip (.) Como la operación binaria (es decir, componemos las funciones en la dirección opuesta).