Monoids and Foldables

Table of Contents

  • Index
  • Repository
    •

    1 Monoids and Foldables

    1.1 Monoids

    1.1.1 Overview

    A monoid is a type constructor with an identity value mempty and a binary operation mappend that defines how two monoids can be combinated to generate a new one. The function moncat concatenates a list of monoids into a one monoid.

    The monoid type class and monoid combinators are defined in the module Data.Monoid. 

    class Monoid m where

    {- Identity Element -}
    mempty :: m

    {- Associative / Binary operator - the alias
       for mappend is (<>) -}
    mappend :: m -> m -> m

    {- Fold a list using the monoid -}
    mconcat :: [m] -> m
    mconcat ms = foldr mappend mempty ms
    Function   Signature Description
    mempty :: m Identity element or Identity value
    mappend :: m -> m -> m Binary operator
    moncat :: [m] -> m Concatenate list of monoids
    <> :: m -> m -> Operator alias to mappend.

    Mappend

    Combine two monoids into a new one. 

    mappend :: Monoid m => m -> m -> m

    Mappend Operator

    Alias for Mappend. 

    (<>) :: Monoid a => a -> a -> a
(<>) = mappend

    Moncat

    Append a list of monoids into a new one. 

    moncat :: Monoid m => [m] -> m

    Monoid Properties

    Monoid Laws      
    Associativity a <> (b <> c) = (a <> b) <> c
    Left Identity mempty <> a = a
    Right Identity a <> mempty = a

    Some Monoids

    Monoid Operation Identity
    Natural Number + 0
    Integer > 0 * 1
    Lists ++ []
    Strings ++ ""

    1.1.2 Instances of Monoid Type Class

    1.1.2.1 List
    Function   Signature Description
    Monoid instance   [a]  
           
    mempty :: [] Identity element is empty list.
    mappend :: [a] -> [a] -> [a] Concatenate two lists
    moncat :: [a] -> a Concatenate a list of lists
    <> :: [a] -> [a] -> [a] Alias to mappend.
            
    instance Monoid [a] where
    mempty  = []
    mappend = (++)

    -- mconcat :: [m] -> m
    -- mconcat ms = foldr mappend mempty ms
    mconcat = concat

    Example: 

    ----------------------
-- Test List Monoids

>>> import Data.Monoid
>>>
>>> :t mconcat
mconcat :: Monoid a => [a] -> a
>>>
>>> :t mempty
mempty :: Monoid a => a
>>>
>>> :t mappend
mappend :: Monoid a => a -> a -> a
>>>
>>> :t (<>)
(<>) :: Monoid m => m -> m -> m
>>>

>>> [9, 3] <> [1, 2, 3]
[9,3,1,2,3]
>>>

>>> mempty :: [a]
[]
>>>

>>> [1, 2, 3] <> mempty
[1,2,3]

>>> mempty <> [1, 2, 3]
[1,2,3]
>>>

>>> [9, 3] <> [1, 2, 3] <> [9, 3, 10]
[9,3,1,2,3,9,3,10]
>>>

>>> [9, 3] `mappend` [1, 2, 3] `mappend` [9, 3, 10]
[9,3,1,2,3,9,3,10]
>>>
    1.1.2.2 String

    Strings are similar to lists and the mempty element is a empty string.

    Function   Signature Description
    Monoid instance   String  
           
    mempty :: "" Empty string
    mappend :: String -> String -> String Concatenate two strings
    moncat :: [String] -> String Concatenate a list of strings
    <> :: String -> String -> String Same as mappend.
            
    >>> import Data.Monoid

>>> :t mempty
mempty :: Monoid a => a
>>>

>>> mempty :: String
""
>>>

>>> :t mappend
mappend :: Monoid a => a -> a -> a
>>>

>>> "Testing " `mappend` " String " `mappend` " monoids"
"Testing  String  monoids"
>>>

>>> "Testing " <> " String " <> " monoids"
"Testing  String  monoids"
>>>

>>> :t mconcat
mconcat :: Monoid a => [a] -> a
>>>


>>> mconcat ["Testing ", "String", " monoids"]
"Testing String monoids"
>>>
    1.1.2.3 Sum
    Function   Signature Description
    Monoid instance   newtype Sum a = Sum { getSum :: a }  
           
    mempty :: Sum 0 Identity element
    mappend :: Sum a -> Sum a -> Sum a Binary operation is sum (+)
    moncat :: [Sum a] -> Sum a Sum all numbers of a list
    <> :: Sum a -> Sum a -> Sum a Alias to mappend.
            
    -- | Monoid under addition.
newtype Sum a = Sum { getSum :: a }
        deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)

instance Num a => Monoid (Sum a) where
        mempty = Sum 0
        mappend = coerce ((+) :: a -> a -> a)
--        Sum x `mappend` Sum y = Sum (x + y)

    Example: 

    >>> import Data.Monoid


{- Sum Monoid
 ----------------------------------}
> :t Sum 
Sum :: a -> Sum a
> Sum 10 
Sum {getSum = 10}
> 

> :t getSum 
getSum :: Sum a -> a
> 

>>> mempty :: Sum Int
Sum {getSum = 0}

>>> mempty :: Product Int
Product {getProduct = 1}
>>>

>>> getSum (mempty :: Sum Int)
0

>>> 1 <> mempty <> 2 <> 3 <> 10 :: Sum Int
Sum {getSum = 16}
>>>

>>> 1 `mappend` mempty `mappend` 2 `mappend` 3 `mappend` 10 :: Sum Int
Sum {getSum = 16}
>>>

>>> mconcat [1, mempty, 2, 3, 10] :: Sum Int
Sum {getSum = 16}
>>>

>>> getSum ( mconcat [1, mempty, 2, 3, 10] :: Sum Int)
16
>>>
    1.1.2.4 Product
    Function   Signature Description
    Monoid instance   Product { getProduct :: a }  
           
    mempty :: Product 1 Identity element
    mappend :: Product a -> Product a -> Product a Binary operation is product (*)
    moncat :: [Product a] -> Product a Product of all numbers in list
    <> :: Prduct a -> Product a -> Product a Alias to mappend.
            
    -- | Monoid under multiplication.
newtype Product a = Product { getProduct :: a }
        deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)

instance Num a => Monoid (Product a) where
        mempty = Product 1
        mappend = coerce ((*) :: a -> a -> a)
--        Product x `mappend` Product y = Product (x * y)

    Example: 

    >>> import Data.Monoid


{- Product Monoid
 ---------------------------------}

>>> 2 <> mempty :: Product Int
Product {getProduct = 2}
>>> mempty <> mempty :: Product Int
Product {getProduct = 1}
>>> mempty <> 2 :: Product Int
Product {getProduct = 2}
>>>

>>> getProduct (mempty :: Product Int)
1
>>>

>>> 2 <> 3 :: Product Int
Product {getProduct = 6}
>>>
>>> getProduct (2 <> 3 :: Product Int)
6
>>>

>>> mconcat [1, 2, 3, 4, 5, mempty] :: Product Int
Product {getProduct = 120}
>>>

>>> getProduct ( mconcat [1, 2, 3, 4, 5, mempty] :: Product Int)
120
>>>

:{
let value :: Product Int
    value = mconcat [1, 2, 3, 4, 5, mempty]
:}

>>> value
Product {getProduct = 120}
>>>
    1.1.2.5 Maybe

    It is useful to deal with monoids resulting from failed computations.

    The contents of Maybe must be an instance of Monoid type class. 

    instance Monoid a => Monoid (Maybe a) where

  mempty = Nothing

  Nothing `mappend` m       = m
  m       `mappend` Nothing = m
  Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

    Example: 

    >>> mempty :: Maybe String
Nothing
>>>

>>> Just "Hello " `mappend` Just "World"
Just "Hello World"
>>>

>>> Just "Hello "  `mappend` Nothing
Just "Hello "
>>>

>>> Nothing  `mappend` Just "World"
Just "World"
>>>

>>> Nothing `mappend` Nothing
Nothing
>>>


>>> Just "Hello " <> Nothing
Just "Hello "
>>>

>>> Just "Hello " <>  Just "World"
Just "Hello World"
>>>

>>> Just "Hello " <>  Just "World" <> Just " Haskell" <> Just " rocks!"
Just "Hello World Haskell rocks!"
>>>

>>> Just "Hello " <>  Nothing <> Nothing  <> Just " rocks!"
Just "Hello  rocks!"
>>>

>>> mconcat [Just "Hello ", Nothing, Just " Haskell", Just " rocks"]
Just "Hello  Haskell rocks"
>>>

>>> mconcat [Nothing, Nothing]
Nothing
>>>

>>> mconcat [] :: Maybe String
Nothing
>>>


>>> Just (Product 4) <> Just (Product 5)
Just (Product {getProduct = 20})
>>>

>>> Just (Product 4) <> Nothing
Just (Product {getProduct = 4})
>>>

>>> Just (Product 4)  <> Nothing <> Just (Product 5) <> Just (Product 3)
Just (Product {getProduct = 60})
>>>

>>> mconcat [Just $ Sum 2, Just $ Sum 3, Nothing, Just $ Sum 10, Nothing]
Just (Sum {getSum = 15})
>>>

>>> fmap getSum $ mconcat [Just $ Sum 2, Just $ Sum 3, Nothing, Just $ Sum 10, Nothing]
Just 15
>>>

>>> getSum <$> mconcat [Just $ Sum 2, Just $ Sum 3, Nothing, Just $ Sum 10, Nothing]
Just 15
>>>
    1.1.2.6 First

    Gets the first Just value of the two operands. The content of Maybe doesn't need to be a instance of Monoid type class. 

    newtype First a = First { getFirst :: Maybe a }
     deriving (Eq, Ord, Read, Show)


instance Monoid (First a) where

     mempty = First Nothing

     First (Just x) `mappend` _ = First (Just x)
     First Nothing  `mappend` x = x

    Example: 

    >>> First (Just 100)
First {getFirst = Just 100}
>>>

>>> getFirst $ First (Just 100)
Just 100
>>>

>>> getFirst $ First Nothing
Nothing
>>>

>>> First (Just 100) <> First Nothing
First {getFirst = Just 100}
>>>

>>> First (Just 100) <> First (Just 10)
First {getFirst = Just 100}
>>>

>>> First Nothing <> First (Just 10)
First {getFirst = Just 10}
>>>

>>> First Nothing <> First Nothing
First {getFirst = Nothing}
>>>

>>> mconcat [First Nothing, First (Just 10), First (Just 2)]
First {getFirst = Just 10}

>>> mconcat [First Nothing, First Nothing, First (Just 2)]
First {getFirst = Just 2}
>>>

>>> mconcat [First Nothing, First Nothing, First Nothing]
First {getFirst = Nothing}
>>>
    1.1.2.7 Last

    Gets the last Just value of two operands. The contents of Maybe doesn't need to be a instance of Monoid. 

    newtype Last a = Last { getLast :: Maybe a }
        deriving (Eq, Ord, Read, Show, Generic, Generic1,
                  Functor, Applicative, Monad)

instance Monoid (Last a) where
        mempty = Last Nothing
        l `mappend` Last Nothing = l
        _ `mappend` r            = r

    Example: 

    >>> import Data.Monoid
>>>

>>> :info Last
newtype Last a = Last {getLast :: Maybe a}
    -- Defined in ‘Data.Monoid’
instance Eq a => Eq (Last a) -- Defined in ‘Data.Monoid’
instance Monad Last -- Defined in ‘Data.Monoid’
instance Functor Last -- Defined in ‘Data.Monoid’
instance Ord a => Ord (Last a) -- Defined in ‘Data.Monoid’
instance Read a => Read (Last a) -- Defined in ‘Data.Monoid’
instance Show a => Show (Last a) -- Defined in ‘Data.Monoid’
instance Applicative Last -- Defined in ‘Data.Monoid’
instance Monoid (Last a) -- Defined in ‘Data.Monoid’
>>>

>>> Last Nothing
Last {getLast = Nothing}
>>> Last (Just 100)
Last {getLast = Just 100}
>>>

>>> getLast $ Last (Just 100)
Just 100
>>> getLast $ Last Nothing
Nothing
>>>

>>> Last (Just 10) <> Last (Just 100)
Last {getLast = Just 100}
>>>
>>> Last Nothing `mappend` Last (Just 100)
Last {getLast = Just 100}
>>>
>>> Last (Just 10) <> Last Nothing
Last {getLast = Just 10}
>>>
>>> Last Nothing <> Last (Just 100)
Last {getLast = Just 100}
>>>
>>> Last Nothing <> Last Nothing
Last {getLast = Nothing}
>>>

>>> mconcat [Last (Just 10), Last (Just 2), Last Nothing, Last (Just 3)]
Last {getLast = Just 3}
>>>

>>> mconcat [Last (Just 6),  Last Nothing, Last (Just 3)]
Last {getLast = Just 3}
>>>

>>> mconcat [Last (Just 6),  Last Nothing]
Last {getLast = Just 6}
>>>

>>> mconcat [Last Nothing]
Last {getLast = Nothing}
>>>
    1.1.2.8 Endo

    Endo is a Monoid defined for endomorphism which means transformation (a -> a) from a type to itself.

    Function   Signature Description
    Monoid instance   newtype Endo a = Endo { appEndo :: a -> a }  
           
    mempty :: Endo id Identity element is identity function
    mappend :: Endo a -> Endo a -> Endo a Binary operation is function composition (.)
    moncat :: [Endo a] -> Endo a Composition of all functions in a list
    <> :: Endo a -> Endo a -> Endo a Alias to mappend.
            
    -- | The monoid of endomorphisms under composition.
newtype Endo a = Endo { appEndo :: a -> a }
               deriving (Generic)

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

    Example: 

    > import Data.Monoid
>

-- Check the types 
--
> :info Endo
newtype Endo a = Endo {appEndo :: a -> a}
        -- Defined in ‘Data.Monoid’
instance Monoid (Endo a) -- Defined in ‘Data.Monoid’
> 
> 


> :t Endo
Endo :: (a -> a) -> Endo a
> 
> :t appEndo
appEndo :: Endo a -> a -> a
> 

-- Define test functions 
-- 
> let f1 x = 10 * x
> let f2 x = 5 * x
> let f3 x = x + 9
> let f4 x = x - 7
> 
> let m = Endo f1 
> :t m
m :: Num a => Endo a
> 
> appEndo m 3
30
> f1 3
30
>


-- Monoid Identity value 
-- 

> let m1 = mempty :: Num a => Endo a
> :t m1
m1 :: Num a => Endo a
> app
appEndo     appendFile
> appEndo m1 3
3
> appEndo m1 100
100
> 


-- It is just function composition.
--
> let a = Endo f1 <> Endo f2 
> appEndo a 3
150
> f1 . f2 $ 3
150
> 
> let b = Endo f1 <> Endo f2 <> Endo f3
> :t b
b :: Num a => Endo a
> 
> appEndo b 3
600
> f1 . f2 . f3 $ 3
600
> 
> let flist = [f1, f2, f3, f4]
> :t flist
flist :: Num a => [a -> a]
> 


---  Compose all functions in the list.
--- 
> let flist = [Endo f1, Endo f2, Endo f3, Endo f4]
> :t flist
flist :: Num a => [Endo a]
> 
> let mm = mconcat flist
> :t mm
mm :: Num a => Endo a
> 
> app
appEndo     appendFile
> appEndo mm 3
250
> f1 . f2 . f3 . f4 $ 3
250
> f1 $ f2 $ f3 $ f4 $ 3
250
> f1 ( f2 ( f3 ( f4  3 )))
250
> 


> let mm2 = map Endo [f1, f2, f3, f4]
> :t mm2
mm2 :: Num a => [Endo a]
> 
> let mm2 = mconcat $ map Endo [f1, f2, f3, f4]
> :t mm2
mm2 :: Num a => Endo a
> 
> appEndo mm2 3
250
> map (appEndo mm2) [1, 2, 3, 4, 5]
[150,200,250,300,350]
>

    1.2 Foldable

    1.2.1 Overview

    Foldable is a class of data structures that can be folded to a summary value. It is a generalization of fold.

    Module documentation: Data.Foldable 

    class Foldable t where
    fold :: Monoid m => t m -> m
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldr :: (a -> b -> b) -> b -> t a -> b
    foldr' :: (a -> b -> b) -> b -> t a -> b
    foldl :: (a -> b -> a) -> a -> t b -
    foldl' :: (a -> b -> a) -> a -> t b -> a
    foldr1 :: (a -> a -> a) -> t a -> a
    foldl1 :: (a -> a -> a) -> t a -> a
    ... ... ...

    A minimal implementation of type class Foldable must implement the functions fold or foldMap.

    • Combine the elements of a structure using a monoid. 
    fold :: Monoid m => t m -> m
fold = foldMap id
    • Map each element of the structure to a monoid, and combine the results. 
    foldMap :: Monoid m => (a -> m) -> t a -> m
{-# INLINE foldMap #-}
-- This INLINE allows more list functions to fuse. See Trac #9848.
foldMap f = foldr (mappend . f) mempty

    1.2.2 Instance of class foldable

    1.2.2.1 Get all Foldable instances
    > import Data.Foldable

> :info Foldable

class Foldable (t :: * -> *) where
  fold :: Monoid m => t m -> m
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b
  foldr' :: (a -> b -> b) -> b -> t a -> b
  foldl :: (b -> a -> b) -> b -> t a -> b
  foldl' :: (b -> a -> b) -> b -> t a -> b
  foldr1 :: (a -> a -> a) -> t a -> a
  foldl1 :: (a -> a -> a) -> t a -> a
  toList :: t a -> [a]
  null :: t a -> Bool
  length :: t a -> Int
  elem :: Eq a => a -> t a -> Bool
  maximum :: Ord a => t a -> a
  minimum :: Ord a => t a -> a
  sum :: Num a => t a -> a
  product :: Num a => t a -> a
  {-# MINIMAL foldMap | foldr #-}

        -- Defined in ‘Data.Foldable’
instance Foldable [] -- Defined in ‘Data.Foldable’
instance Foldable Sum -- Defined in ‘Data.Foldable’
instance Foldable Product -- Defined in ‘Data.Foldable’
instance Foldable Maybe -- Defined in ‘Data.Foldable’
instance Foldable Last -- Defined in ‘Data.Foldable’
instance Foldable First -- Defined in ‘Data.Foldable’
instance Foldable (Either a) -- Defined in ‘Data.Foldable’
instance Foldable Dual -- Defined in ‘Data.Foldable’
instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
>
    1.2.2.2 List
    instance Foldable [] where
    foldMap _ [] = mempty
    foldMap f (x : xs) = f x <> foldMap xs

    Example 1: Foldable list and list monoid 

    > import Data.Foldable
>

-- For lists - Data.Foldable.fold is equivalent to concat 
--
-- fold :: [[a]] -> [a]
-- 
> :t fold
fold :: (Monoid m, Foldable t) => t m -> m
> 

> fold [[1, 10, 30], [1, 2, 3, 4, 5], [], [3, 4]]
[1,10,30,1,2,3,4,5,3,4]
> 

> concat [[1, 10, 30], [1, 2, 3, 4, 5], [], [3, 4]]
[1,10,30,1,2,3,4,5,3,4]
> 


-- Lazy letf fold -> Can cause memory leak 
--
> foldl (\acc x -> 10 * acc + x) 0 [1, 2, 3, 4, 5]
12345
> 

-- Strict left fold
--
> foldl' (\acc x -> 10 * acc + x) 0 [1, 2, 3, 4, 5]
12345
> 

-- Right fold 
--
> 
> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
> 
> foldr (\x acc -> 10 * acc + x) 0 [1, 2, 3, 4, 5]
54321

-- foldMap - Equivalent to map and concat for list.
--
-- For lists:
--  foldMap :: (a -> [a]) -> [a] -> [a]
-- 
> :t foldMap 
foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
> 

> foldMap (\x -> [2 * x, 3 * x, 5 * x]) [1, 2, 3, 4, 5]
[2,3,5,4,6,10,6,9,15,8,12,20,10,15,25]
> 

> 
> map (\x -> [2 * x, 3 * x, 5 * x]) [1, 2, 3, 4, 5]
[[2,3,5],[4,6,10],[6,9,15],[8,12,20],[10,15,25]]
> 
> concat $ map (\x -> [2 * x, 3 * x, 5 * x]) [1, 2, 3, 4, 5]
[2,3,5,4,6,10,6,9,15,8,12,20,10,15,25]
>

    Example 2: Foldable list and string monoid 

    > import Data.Monoid
> import Data.Foldable 
> 

> mempty :: String
""
> "hello " <> " world " <> " Haskell "
"hello  world  Haskell "
> 


--
-- fold :: [String] -> String
--
> :t fold
fold :: (Monoid m, Foldable t) => t m -> m
>

> fold ["hello ",  " world ", " Haskell "]
"hello  world  Haskell "
> 

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

> foldMap (\x -> " x = " ++ show x ++ ", ") [1, 2, 3, 4, 5]
" x = 1,  x = 2,  x = 3,  x = 4,  x = 5, "
>

    Example 3: Foldable list and sum monoid 

    > import Data.Monoid
> import Data.Foldable as DF
> 

--
-- fold :: [Sum a] -> Sum a 
--
> :t fold
fold :: (Monoid m, Foldable t) => t m -> m
>

> fold [Sum 3, Sum 10, Sum 6, Sum 10]
Sum {getSum = 29}
> 
> getSum $ fold [Sum 3, Sum 10, Sum 6, Sum 10]
29
> 


-- 
-- foldMap :: (a -> Sum a) -> [a] -> Sum a 
--
> :t foldMap 
DF.foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
>

> 
> foldMap Sum [1, 2, 3, 4, 5]
Sum {getSum = 15}
> 
> getSum $ foldMap Sum [1, 2, 3, 4, 5]
15
>

    Example 4: Foldable list and Endo monoid 

    > import Data.Monoid
> import Data.Foldable
> 

> :t Endo
Endo :: (a -> a) -> Endo a
>

-- Composes all functions wrapped by Endo 
-- 
-- fold :: [Endo a] -> Endo a 
--
--
> :t fold
fold :: (Monoid m, Foldable t) => t m -> m
>


> let m = fold [Endo (+10), Endo (*3), Endo $ \x -> 10 * x - 5] :: Endo Int

> :t m
m :: Endo Int

> appEndo m 5
145

> appEndo m 4
115
> 

 -- Equivalent expressions 

> (+10) . (*3) . (\x -> 10 * x - 5) $ 5 :: Int
145
> (+10) . (*3) . (\x -> 10 * x - 5) $ 5 
145
> (+10) . (*3) . (\x -> 10 * x - 5) $ 5 :: Int
145
> (+10) . (*3) . (\x -> 10 * x - 5) $ 4 :: Int
115
> (+10) $ (*3) $ (\x -> 10 * x - 5) $ 4 :: Int
115
> 


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

> let f = foldMap Endo [ (+10),  (*3),  \x -> 10 * x - 5] 
> :t f
f :: Num a => Endo a
> 
> appEndo f 4
115
> appEndo f 5
145
> 

> let f2 = foldMap (\f -> Endo $ \x -> f (3 * x - 2))  [ (+10),  (*3),  \x -> 10 * x - 5] 

> appEndo f2 4
2555
> appEndo f2 5
3365

> let f3 = fold $ map  (\f -> Endo $ \x -> f (3 * x - 2))  [ (+10),  (*3),  \x -> 10 * x - 5] 
> :t f3
f3 :: Num a => Endo a
> appEndo f3 4
2555
> appEndo f3 5
3365
>
    1.2.2.3 Maybe
    instance Foldable Maybe where
    foldMap _ Nothing  = mempty
    foldMap f (Just x) = f x

    Example 1: Maybe foldable and list monoid 

    > import Data.Monoid
> import Data.Foldable 
> 

-- List Monoid
--
> mempty :: [Int]
[]
> [1, 2, 3] <> [3, 5] <> [9, 10]
[1,2,3,3,5,9,10]
> 


--
-- fold :: Maybe [Int] -> [Int]
--
> :t fold
fold :: (Monoid m, Foldable t) => t m -> m
>

> fold (Just [1, 2, 3, 4])
[1,2,3,4]
>
> fold Nothing :: [Int]
[]
>


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

> foldMap (\x -> [2 * x, 3 + x]) (Just 10)
[20,13]
> foldMap (\x -> [2 * x, 3 + x, x + 8]) (Just 10)
[20,13,18]
> foldMap (\x -> [2 * x, 3 + x, x + 8]) (Just 5)
[10,8,13]
> foldMap (\x -> [2 * x, 3 + x, x + 8]) Nothing
[]
>


> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
> 
> foldl (\ acc x -> 10 * acc + x) 10 (Just 4)
104
> foldl (\ acc x -> 10 * acc + x) 10 Nothing
10
> 

> 
> foldr (\x acc -> 10 * acc + x) 10 (Just 5)
105
> foldr (\x acc -> 10 * acc + x) 10 Nothing
10
>

    Example: Maybe foldable and Sum monoid 

    import Data.Foldable
import Data.Monoid     

> fold (Just $ Sum 10)
Sum {getSum = 10}

> fold (Just $ Sum 10) :: Sum Int
Sum {getSum = 10}
> 

> fold Nothing :: Sum Int
Sum {getSum = 0}
>

> 
> foldMap (\x -> Sum $ x * 3) (Just 10)
Sum {getSum = 30}
> foldMap (\x -> Sum $ x * 3) Nothing
Sum {getSum = 0}
>

    Author: nobody

    Created: 2018-05-07 Mon 10:11

    Emacs 25.3.1 (Org mode 8.2.10)

    Validate