Skąd pochodzą składanie/składanie implementacji składanego dla drzew binarnych w haskell?

Question

Pracuję poprzez Learn You a Haskell, a ja zajmuję się sekcją o monoidach. W tej części autor definiuje metodę foldMap na drzewie, co następuje:

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 

który działa dobrze i jest całkowicie Baller. Jednak on stwierdza: "Teraz, gdy mamy już składaną instancję dla naszego typu drzewa, otrzymamy foldr i foldl za darmo!" i pokazuje następujący kod:

testTree = Node 5 
      (Node 3 
       (Node 1 Empty Empty) 
       (Node 6 Empty Empty) 
      ) 
      (Node 9 
       (Node 8 Empty Empty) 
       (Node 10 Empty Empty) 
      ) 

ghci> F.foldl (+) 0 testTree 
42 
ghci> F.foldl (*) 1 testTree 
64800 

Teraz jestem zdezorientowany. Nigdzie nie było implementacji foldl lub foldr napisanych dla drzew. Wydaje się, że funkcje działają podobnie do mapy foldmap, ale umieszczają początkowy akumulator jako głowę drzewa, a następnie foldMapping na odpowiednim monoidzie, ale tak naprawdę nie może działać tak, ponieważ foldl i foldr mają bardziej ogólne funkcje niż monoidy "+" i "*" jako argumenty. Gdzie faktycznie są zaimplementowane foldl i foldr, jak działają i dlaczego definiowanie foldMap powoduje ich istnienie?

Answer 1

Wystarczy spojrzeć na source of Foldable. Definiuje foldr użyciu foldMap i vice versa, więc to wystarczy, aby określić jeden, który jest bardziej wygodne dla Ciebie (choć wdrażaniu zarówno może dać pewne korzyści wydajności):

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

Przeanalizujmy, co dzieje się tutaj, na przykład. Załóżmy, że mamy zamiar złożyć listę [i, j, k]. Prawo krotnie f i z jest

f i (f j (f k z)) 

ten może być wyrażony alternatywnie

(f i . f j . f k) z 

Stosując f, że konwersja każdy element listy w produkt endomorphism na b i układać je razem. Teraz endomorfizmy tworzą monoid, który jest wyrażany w Haskell przy użyciu Endo: jego mempty jest tylko id i mappend jest .. Tak więc możemy przepisać jako

appEndo (Endo (f i) `mappend` Endo (f j) `mappend` Endo (f k)) z 

i możemy wyrazić wewnętrzną część jak foldMap (Endo . f) [i, j, k].

Podsumowując: Kluczową ideą jest to, że endomorfizm ponad jakiejś domeny tworzą monoid i f :: a -> (b -> b) odwzorowuje elementy a do endomorfizm nad b.

---

odwrotna jest wyrażona jako

foldMap f = foldr (mappend . f) mempty 

Mamy tu f :: a -> m gdzie m jest monoid i tworzenia go mappend otrzymujemy mappend . f :: a -> (m -> m), który bierze element x typu a i konstruowania funkcję na m, który przekształca u :: m w mappend (f u) k. A następnie używa tej funkcji, aby złożyć wszystkie elementy konstrukcji.

Answer 2

Od http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-Foldable.html#Foldable:

class Foldable t where 

    ... 

    foldMap :: Monoid m => (a -> m) -> t a -> m 
    foldMap f = foldr (mappend . f) mempty 

    ... 

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

    ... 

    foldl :: (a -> b -> a) -> a -> t b -> a 
    foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z 

Więc masz domyślne implementacje (w tym przypadku nawet kołowym). Dlatego istnieje komentarz: "Minimalna pełna definicja: foldMap lub foldr". w opisie klasy Foldable typu (patrz http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Foldable.html)

Prostszy przykład dla tej techniki jest klasa Eq typ, gdzie (==) i (/=) są zdefiniowane pod względem siebie, ale oczywiście trzeba realizować co najmniej jeden z nich w instancji (dostaniesz nieskończoną pętlę).