Hao Wu / Field Notes

Typeclass: Foldable

Foldable

Readings

Parametric Type : t a

Intuition based on Algebraic Data Type

This section needs more theoretical backup.
Jump to Intuition for Real World Implementation for recap.

instance declaration Context type define
instance Foldable Tree in ‘Data.Tree’
instance Foldable [] in ‘Data.Foldable’
instance Foldable Maybe in ‘Data.Foldable’
instance Foldable (Either a) in ‘Data.Foldable’
instance Foldable ((,) a) in ‘Data.Foldable’

It’s all about foldMap

1.Only one value of Target Type a in t a.

2.More values of Target type a in t a.

This is the main part of this doc.

If there is more than one value of the target type in the data structure, they must be organized based on the Product of Target type a. Two most used examples:

So we know:

  1. Step a of foldMap replace a with m, we have: List a = 1 + a + ... + a*a*... -> 1 + m + ... + m*m*... Tree a = a + a*a + ... + a*a*... -> m + m*m + ... + m*m*...

  2. Step b of foldMap. A product m*m*m needs to be

    1. Aggregated with '<>'.
    2. Aggregated with '<>'.
    3. Aggregated with '<>'. \

    means replace * of product type with <>.
    Now:
    (Monoid m) => m * m * m == m <> m <> m.

The computation foldMap f List are essentially the same as foldMap f Tree, except:

  1. When List could be empty, then: foldMap f List = mempty.
  2. T cannot be empty, it must contains at least one value of type a, it is equivalent to a List of only one element. In this case foldMap f L = foldMap f T = m

Summary

Intuition for Real World Implementation

  1. foldr intuition for List

    • Replace Con with f.
      • Or replace : with f (if f is an infix function).
    • Replace Nil with z. foldr foldr
    l = (Con a (Con b (Con c(Con ... (Con Nil))))
foldr f z l =(f a (f b (f c(f ... (f z))))
    • Justificatoin

      • foldr (a -> b -> b) b (List a) = foldMap (a -> b -> b) (List a) $ b replace a with b -> b , replace * with <> in this case .

      • foldr f z t = (b -> b) . (b -> b) . (b -> b) $ z

      • Con :: a -> List -> List
        z = Nil
        List a = (Con a (Con a (Con a..(Con a Nil))))

      • Con a (Con a( ....)) is the composition order, therefore

      • if f:: a -> b -> b , replace Con with f and Nil with z.

      • foldr f z l =(f a (f b (f c(f ... (f z))))

  2. foldr intuition for Tree

    • Tree a and List a are equivalent to each other as instances of Foldable.
    • Therefore, foldr f z (Tree a) == foldr f z (List a), foldr over a Tree of target type a is the same as foldr over a List of target type a. The structure information of Tree disappeared.
    • Tree and List are gone. Only a*a*...*a information. 
      > t1 = Node 1 []
> t2 = Node 2 []
> t3 = Node 3 []
> t4 = Node 4 []
> t5 = Node 5 [t1,t2]
> t6 = Node 6 [t3,t4]
> t7 = Node 7 [t5,t6]
> foldr (:) [] t7
    [7,5,1,2,6,3,4]
> flatten t7
    [7,5,1,2,6,3,4]
      So We could construct a List a from Tree a based on foldr using (:) to replace * and use [] to terminate aggregate function of type [] -> []. 
      instance Foldable Tree where
    ...
    toList = flatten
    ...
-- > flatten (Node 1 [Node 2 [], Node 3 []]) == [1,2,3]
flatten :: Tree a -> [a]
flatten t = squish t []
    where squish (Node x ts) xs = x:Prelude.foldr squish xs ts

  3. foldr Generalized Iintuition.

    • More than one value in Parametric Type :: t a means t is or wrapping a product type a*a*...*a.
    • Being instance of Foldable means t only implies the existence of a*a...*a. All other information such as structure information of being Tree or List are irrelevant.
    • foldMap is the basic function that replace a with Monoid m; replace * with <>.
    • foldr is an extension of foldMap. It equivalent to
      • Treat t a of any type as List t.
      • Replace Con with f.
      • Replace Nil with z.
    • Values of target type a got folded.
    • Foldable includes the toList :: Foldable t => t a -> [a] method. That means any Foldable data structure can be turned into a list [haskell wikibook]

  4. Summary
    For a parametric type 't a' being an instance of Foldable means we could use foldMap or foldr to fold value(s) of target type a. So basically t a is Foldable when it is an instance of Foldable.
    Pretty self-explanatory.

Others

1. foldrM

|function| constraint|type| define | import |
|:–:|:–:|:–:|:–:|:–:|:–:| |foldrM| Monad m, Foldable t| (a -> b -> m b) -> b -> t a -> m b| Data.Foldable | Data.Foldable| |foldlM| Monad m, Foldable t| (b -> a -> m b) -> b -> t a -> m b| Data.Foldable | Data.Foldable| |foldM| Monad m, Foldable t| (b -> a -> m b) -> b -> t a -> m b| Control.Monad (=foldlM) | Control.Monad|

Starts from foldr

  1. The semantics of foldr is:

    • t a is a collection of elements with the same type a.
    • a function f of type a -> b -> b
    • a single element of type b.
    • foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b:

      each element of t a contribute a piece of information to a element of type b through function f.

    • Foldable treat all structure t equally as a List.
    • foldr replaces component of List a. It replaces Con or : with f, and [] with z.

  2. The semantics of foldrM:

Option A: Replace : with =<< , [] with m b we have (b -> m b) =<< (b -> m b) =<< ... =<< ( b-> m b) =<< m b In this case:

foldrM f z xs = foldr (=<<) (pure z) (f <$> xs)

Option B: Replace : with <=<, [] with b -> m b we have (b -> m b) <=< (b -> m b) <=< ... <=< ( b-> m b) <=< (b -> m b) In this case:

foldrM f z xs = foldr (<=<) pure (f <$> xs) $ z

Example:

*>import Control.Monad.Trans.Writer    -- Use Wirter Monad in this example.
*>import Control.Monad                 -- import (<=<)
*>import Data.Foldable                 -- import foldr, foldrM, etc.

*>:{
*|wf a b = do 
*|        tell $ show b             -- introduce String type log
*|        return $ a * b            -- target computation a*b.
*|:}
*>:info wf
*w :: (Monad m, Show b, Num b) => b -> b -> WriterT String m b

*>let tl = [1,2,3,4]
*>let z = 1

*>r1 <- runWriterT $ foldrM wf z tl
*>r1
*(4,"141224")

*>let r2 = foldr (=<<) (pure z) $ wf <$> tl
*>rr2 <- runWriterT r2
*>rr2
*(4,"141224")

*>let r3 = foldr (<=<) pure (wf <$> tl) $ z
*>rr3 <- runWriterT r3
*>rr3
(24,"141224")

foldrM Summary

TODO:

  1. Why is this flatten in Data.Tree better than foldr version above.
  2. How to rewrite foldM(foldlM) in the form of foldr + fmap

    The official definition of foldlM and foldrM is hard to understand.

    *> let pl = foldM wf 1 tl 
*> l <- runWriterT pl
*> l
(24,"1234")
    Try combine the answer in stackoverflow to get an intuitive understanding.
  3. Intuition about all examples in youtube ConfEngine