Haskell IntroductionData.Aeson - JSON in HaskellHaskell Applicative FunctorHaskell Arbitrary-rank polymorphism with RankNTypesHaskell ArithmeticHaskell ArrowsHaskell AttoparsecHaskell BifunctorHaskell CabalHaskell Category TheoryHaskell Common functors as the base of cofree comonadsHaskell Common GHC Language ExtensionsHaskell Common monads as free monadsHaskell ConcurrencyHaskell Containers - Data.MapHaskell Creating Custom Data TypesHaskell Data.TextHaskell DatabasesHaskell Date and TimeHaskell Fixity declarationsHaskell FoldableHaskell Foreign Function InterfaceHaskell Free MonadsHaskell Function call syntaxHaskell Function compositionHaskell FunctorHaskell Generalized Algebraic Data TypesHaskell GHCJSHaskell Google Protocol BuffersHaskell Graphics with GlossHaskell Gtk3Haskell Higher-order functionsHaskell Infix operatorsHaskell IOHaskell LensHaskell List ComprehensionsHaskell ListsHaskell LoggingHaskell ModulesHaskell Monad TransformersHaskell MonadsHaskell MonoidHaskell OptimizationHaskell Overloaded LiteralsHaskell ParallelismHaskell Parsing HTML with taggy-lens and lensHaskell Partial ApplicationHaskell Phantom typesHaskell PipesHaskell ProfunctorHaskell ProxiesHaskell QuickCheckHaskell Reactive-bananaHaskell Reader / ReaderTHaskell Record SyntaxHaskell Recursion SchemesHaskell Rewrite rules (GHC)Haskell RoleHaskell Sorting AlgorithmsHaskell StackHaskell State MonadHaskell Streaming IOHaskell StrictnessHaskell Syntax in FunctionsHaskell Testing with TastyHaskell TraversableHaskell Tuples (Pairs, Triples, ...)Haskell Type algebraHaskell Type ApplicationHaskell Type ClassesHaskell Type FamiliesHaskell Typed holesHaskell Using GHCiHaskell VectorsHaskell Web DevelopmentHaskell XMLHaskell zipWithMTemplate Haskell & QuasiQuotes

Haskell Foldable

From WikiOD

Foldable is the class of types t :: * -> * which admit a folding operation. A fold aggregates the elements of a structure in a well-defined order, using a combining function.

Remarks[edit | edit source]

If t is Foldable it means that for any value t a we know how to access all of the elements of a from "inside" of t a in a fixed linear order. This is the meaning of foldMap :: Monoid m => (a -> m) -> (t a -> m): we "visit" each element with a summary function and smash all the summaries together. Monoids respect order (but are invariant to different groupings).

An instance of Foldable for a binary tree[edit | edit source]

To instantiate Foldable you need to provide a definition for at least foldMap or foldr.

data Tree a = Leaf
            | Node (Tree a) a (Tree a)

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

    foldr f acc Leaf = acc
    foldr f acc (Node l x r) = foldr f (f x (foldr f acc r)) l

This implementation performs an in-order traversal of the tree.

ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf)
**    +--'b'--+
**    |       |
** +-'a'-+ +-'c'-+
** |     | |     |
** *     * *     *

ghci> toList myTree

The DeriveFoldable extension allows GHC to generate Foldable instances based on the structure of the type. We can vary the order of the machine-written traversal by adjusting the layout of the Node constructor.

data Inorder a = ILeaf
               | INode (Inorder a) a (Inorder a)  -- as before
               deriving Foldable

data Preorder a = PrLeaf
                | PrNode a (Preorder a) (Preorder a)
                deriving Foldable

data Postorder a = PoLeaf
                 | PoNode (Postorder a) (Postorder a) a
                 deriving Foldable
** injections from the earlier Tree type
inorder :: Tree a -> Inorder a
inorder Leaf = ILeaf
inorder (Node l x r) = INode (inorder l) x (inorder r)

preorder :: Tree a -> Preorder a
preorder Leaf = PrLeaf
preorder (Node l x r) = PrNode x (preorder l) (preorder r)

postorder :: Tree a -> Postorder a
postorder Leaf = PoLeaf
postorder (Node l x r) = PoNode (postorder l) (postorder r) x

ghci> toList (inorder myTree)
ghci> toList (preorder myTree)
ghci> toList (postorder myTree)

Definition of Foldable[edit | edit source]

class Foldable t where
    {-# MINIMAL foldMap | foldr #-}

    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

    -- and a number of optional methods

Intuitively (though not technically), Foldable structures are containers of elements a which allow access to their elements in a well-defined order. The foldMap operation maps each element of the container to a Monoid and collapses them using the Monoid structure.

Counting the elements of a Foldable structure[edit | edit source]

length counts the occurences of elements a in a foldable structure t a.

ghci> length [7, 2, 9]  -- t ~ []
ghci> length (Right 'a')  -- t ~ Either e
1  -- 'Either e a' may contain zero or one 'a'
ghci> length (Left "foo")  -- t ~ Either String
ghci> length (3, True)  -- t ~ (,) Int
1  -- '(c, a)' always contains exactly one 'a'

length is defined as being equivalent to:

class Foldable t where
    -- ...
    length :: t a -> Int
    length = foldl' (\c _ -> c+1) 0

Note that this return type Int restricts the operations that can be performed on values obtained by calls to the length function. fromIntegralis a useful function that allows us to deal with this problem.

Folding a structure in reverse[edit | edit source]

Any fold can be run in the opposite direction with the help of the Dual monoid, which flips an existing monoid so that aggregation goes backwards.

newtype Dual a = Dual { getDual :: a }

instance Monoid m => Monoid (Dual m) where
    mempty = Dual mempty
    (Dual x) `mappend` (Dual y) = Dual (y `mappend` x)

When the underlying monoid of a foldMap call is flipped with Dual, the fold runs backwards; the following Reverse type is defined in Data.Functor.Reverse:

newtype Reverse t a = Reverse { getReverse :: t a }

instance Foldable t => Foldable (Reverse t) where
    foldMap f = getDual . foldMap (Dual . f) . getReverse

We can use this machinery to write a terse reverse for lists:

reverse :: [a] -> [a]
reverse = toList . Reverse

Flattening a Foldable structure into a list[edit | edit source]

toList flattens a Foldable structure t a into a list of as.

ghci> toList [7, 2, 9]  -- t ~ []
[7, 2, 9]
ghci> toList (Right 'a')  -- t ~ Either e
ghci> toList (Left "foo")  -- t ~ Either String
ghci> toList (3, True)  -- t ~ (,) Int

toList is defined as being equivalent to:

class Foldable t where
    -- ...
    toList :: t a -> [a]
    toList = foldr (:) []

Performing a side-effect for each element of a Foldable structure[edit | edit source]

traverse_ executes an Applicative action for every element in a Foldable structure. It ignores the action's result, keeping only the side-effects. (For a version which doesn't discard results, use Traversable.)

** using the Writer applicative functor (and the Sum monoid)
ghci> runWriter $ traverse_ (\x -> tell (Sum x)) [1,2,3]
((),Sum {getSum = 6})
** using the IO applicative functor
ghci> traverse_ putStrLn (Right "traversing")
ghci> traverse_ putStrLn (Left False)
** nothing printed

for_ is traverse_ with the arguments flipped. It resembles a foreach loop in an imperative language.

ghci> let greetings = ["Hello", "Bonjour", "Hola"]
ghci> :{
ghci|     for_ greetings $ \greeting -> do
ghci|         print (greeting ++ " Stack Overflow!")
ghci| :}
"Hello Stack Overflow!"
"Bonjour Stack Overflow!"
"Hola Stack Overflow!"

sequenceA_ collapses a Foldable full of Applicative actions into a single action, ignoring the result.

ghci> let actions = [putStrLn "one", putStLn "two"]
ghci> sequenceA_ actions

traverse_ is defined as being equivalent to:

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
traverse_ f = foldr (\x action -> f x *> action) (pure ())

sequenceA_ is defined as:

sequenceA_ :: (Foldable t, Applicative f) -> t (f a) -> f ()
sequenceA_ = traverse_ id

Moreover, when the Foldable is also a Functor, traverse_ and sequenceA_ have the following relationship:

traverse_ f = sequenceA_ . fmap f

Flattening a Foldable structure into a Monoid[edit | edit source]

foldMap maps each element of the Foldable structure to a Monoid, and then combines them into a single value.

foldMap and foldr can be defined in terms of one another, which means that instances of Foldable need only give a definition for one of them.

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

Example usage with the Product monoid:

product :: (Num n, Foldable t) => t n -> n
product = getProduct . foldMap Product

Checking if a Foldable structure is empty[edit | edit source]

null returns True if there are no elements a in a foldable structure t a, and False if there is one or more. Structures for which null is True have a length of 0.

ghci> null []
ghci> null [14, 29]
ghci> null Nothing
ghci> null (Right 'a')
ghci> null ('x', 3)

null is defined as being equivalent to:

class Foldable t where
    -- ...
    null :: t a -> Bool
    null = foldr (\_ _ -> False) True