Data.Functor.Foldable

Obtain the base functor for a recursive datatype.

The core idea of this library is that instead of writing recursive functions on a recursive datatype, we prefer to write non-recursive functions on a related, non-recursive datatype we call the "base functor".

For example, [a] is a recursive type, and its corresponding base functor is ListF a:

data ListF a b = Nil | Cons a b
type instance Base [a] = ListF a

The relationship between those two types is that if we replace b with ListF a, we obtain a type which is isomorphic to [a].

Base functor of [].

A recursive datatype which can be unrolled one recursion layer at a time.

For example, a value of type [a] can be unrolled into a ListF a [a]. If that unrolled value is a Cons, it contains another [a] which can be unrolled as well, and so on.

Typically, Recursive types also have a Corecursive instance, in which case project and embed are inverses.

A recursive datatype which can be rolled up one recursion layer at a time.

For example, a value of type ListF a [a] can be rolled up into a [a]. This [a] can then be used in a Cons to construct another ListF a [a], which can be rolled up as well, and so on.

Typically, Corecursive types also have a Recursive instance, in which case embed and project are inverses.

Folds a recursive type down to a value, one layer at a time.

>>> :{let mySum :: [Int] -> Int    mySum = fold $ \case      Nil -> 0      Cons x sumXs -> x + sumXs:}

>>> mySum [10,11,12]33

In our running example, one layer consists of an Int and a list of recursive positions. In Tree Int, those recursive positions contain sub-trees of type Tree Int. Since we are working one layer at a time, the Base t a -> a function is not given a Tree Int, but a TreeF Int String. That is, each recursive position contains the String resulting from recursively folding the corresponding sub-tree.

>>> :{let pprint1 :: Tree Int -> String    pprint1 = fold $ \case      NodeF i [] -> show i      NodeF i ss -> show i ++ ": [" ++ intercalate ", " ss ++ "]":}

>>> putStrLn $ pprint1 myTree0: [1, 2, 3: [31: [311: [3111, 3112]]]]

More generally, the t argument is the recursive value, the a is the final result, and the Base t a -> a function explains how to reduce a single layer full of recursive results down to a result.

An alias for fold.

fold is by far the most common recursion-scheme, because working one layer at a time is the most common strategy for writing a recursive function. But there are also other, rarer strategies. Researchers have given names to the most common strategies, and their name for fold is "catamorphism". They also give its Base t a -> a argument a special name, "(Base t)-algebra". More generally, a function of the form f a -> a is called an "f-algebra".

The names might seem intimidating at first, but using the standard nomenclature has benefits. If you program with others, it can be useful to have a shared vocabulary to refer to those recursion patterns. For example, you can discuss which type of recursion is the most appropriate for the problem at hand. Names can also help to structure your thoughts while writing recursive functions.

The rest of this module lists a few of the other recursion-schemes which are common enough to have a name. In this section, we restrict our attention to those which fold a recursive structure down to a value. In the examples all functions will be of type Tree Int -> String.

A specialization of cata for effectful folds.

cataA is the same as cata, but with a more specialized type. The only reason it exists is to make it easier to discover how to use this library with effects.

For our running example, let's improve the output format of our pretty-printer by using indentation. To do so, we will need to keep track of the current indentation level. We will do so using a Reader Int effect. Our recursive positions will thus contain Reader Int String actions, not Strings. This means we need to run those actions in order to get the results.

>>> :{let pprint2 :: Tree Int -> String    pprint2 = flip runReader 0 . cataA go      where        go :: TreeF Int (Reader Int String)           -> Reader Int String        go (NodeF i rss) = do          -- rss :: [Reader Int String]          -- ss  :: [String]          ss <- local (+ 2) $ sequence rss          indent <- ask          let s = replicate indent ' ' ++ "* " ++ show i          pure $ intercalate "\n" (s : ss):}

>>> putStrLn $ pprint2 myTree* 0  * 1  * 2  * 3    * 31      * 311        * 3111        * 3112

The fact that the recursive positions contain Reader actions instead of Strings gives us some flexibility. Here, we are able to increase the indentation by running those actions inside a local block. More generally, we can control the order of their side-effects, interleave them with other effects, etc.

A similar technique is to specialize cata so that the result is a function. This makes it possible for data to flow down in addition to up. In this modified version of our running example, the indentation level flows down from the root to the leaves, while the resulting strings flow up from the leaves to the root.

>>> :{let pprint3 :: Tree Int -> String    pprint3 t = cataA go t 0      where        go :: TreeF Int (Int -> String)           -> Int -> String        go (NodeF i fs) indent            -- fs :: [Int -> String]          = let indent' = indent + 2                ss = map (\f -> f indent') fs                s = replicate indent ' ' ++ "* " ++ show i            in intercalate "\n" (s : ss):}

>>> putStrLn $ pprint3 myTree* 0  * 1  * 2  * 3    * 31      * 311        * 3111        * 3112

A variant of cata in which recursive positions also include the original sub-tree, in addition to the result of folding that sub-tree.

For our running example, let's add a number to each node indicating how many children are below it. To do so, we will need to count those nodes from the original sub-tree.

>>> :{let pprint4 :: Tree Int -> String    pprint4 = flip runReader 0 . para go      where        go :: TreeF Int (Tree Int, Reader Int String)           -> Reader Int String        go (NodeF i trss) = do          -- trss :: [(Tree Int, Reader Int String)]          -- ts   :: [Tree Int]          -- rss  :: [Reader Int String]          -- ss   :: [String]          let (ts, rss) = unzip trss          let count = sum $ fmap length ts          ss <- local (+ 2) $ sequence rss          indent <- ask          let s = replicate indent ' '               ++ "* " ++ show i               ++ " (" ++ show count ++ ")"          pure $ intercalate "\n" (s : ss):}

>>> putStrLn $ pprint4 myTree* 0 (7)  * 1 (0)  * 2 (0)  * 3 (4)    * 31 (3)      * 311 (2)        * 3111 (0)        * 3112 (0)

One common use for para is to construct a new tree which reuses most of the sub-trees from the original. In the following example, we insert a new node under the leftmost leaf. This requires allocating new nodes along a path from the root to that leaf, while keeping every other sub-tree untouched.

>>> :{let insertLeftmost :: Int -> Tree Int -> Tree Int    insertLeftmost new = para go      where        go :: TreeF Int (Tree Int, Tree Int)           -> Tree Int        go (NodeF i []) = Node i [Node new []]        go (NodeF i ((_orig, recur) : tts))            -- tts :: [(Tree Int, Tree Int)]          = let (origs, _recurs) = unzip tts            in Node i (recur : origs):}

>>> putStrLn $ pprint4 $ insertLeftmost 999 myTree* 0 (8)  * 1 (1)    * 999 (0)  * 2 (0)  * 3 (4)    * 31 (3)      * 311 (2)        * 3111 (0)        * 3112 (0)

A variant of cata which includes the results of all the descendents, not just the direct children.

Like para, a sub-tree is provided for each recursive position. Each node in that sub-tree is annotated with the result for that descendent. The Cofree type is used to add those annotations.

For our running example, let's recreate GitHub's directory compression algorithm. Notice that in the repository for this package, GitHub displays src/Data/Functor, not src:

GitHub's code page

GitHub does this because src only contains one entry: Data. Similarly, Data only contains one entry: Functor. Functor contains several entries, so the compression stops there. This helps users get to the interesting folders more quickly.

Before we use histo, we need to define a helper function rollup. It collects nodes until it reaches a node which doesn't have exactly one child. It also returns the labels of that node's children.

>>> :{let rollup :: [Cofree (TreeF node) label]           -> ([node], [label])    rollup [_ :< NodeF node cofrees] =      let (nodes, label) = rollup cofrees      in (node : nodes, label)    rollup cofrees =      ([], fmap extract cofrees):}

>>> let foobar xs = 1 :< NodeF "foo" [2 :< NodeF "bar" xs]>>> rollup [foobar []](["foo","bar"],[])>>> rollup [foobar [3 :< NodeF "baz" [], 4 :< NodeF "quux" []]](["foo","bar"],[3,4])

The value foobar [] can be interpreted as the tree NodeF "foo" [NodeF "bar" []], plus two annotations. The "foo" node is annotated with 1, while the "bar" node is annotated with 2. When we call histo below, those annotations are recursive results of type Int -> String.

>>> :{let pprint5 :: Tree Int -> String    pprint5 t = histo go t 0      where        go :: TreeF Int (Cofree (TreeF Int) (Int -> String))           -> Int -> String        go (NodeF node cofrees) indent            -- cofrees :: [Cofree (TreeF Int) (Int -> String)]            -- fs :: [Int -> String]          = let indent' = indent + 2                (nodes, fs) = rollup cofrees                ss = map (\f -> f indent') fs                s = replicate indent ' '                 ++ "* " ++ intercalate " / " (fmap show (node : nodes))            in intercalate "\n" (s : ss):}

>>> putStrLn $ pprint5 myTree* 0  * 1  * 2  * 3 / 31 / 311    * 3111    * 3112

One common use for histo is to cache the value computed for smaller sub-trees. In the Fibonacci example below, the recursive type is Natural, which is isomorphic to [()]. Our annotated sub-tree is thus isomorphic to a list of annotations. In our case, each annotation is the result which was computed for a smaller number. We thus have access to a list which caches all the Fibonacci numbers we have computed so far.

>>> :{let fib :: Natural -> Integer    fib = histo go      where        go :: Maybe (Cofree Maybe Integer) -> Integer        go Nothing = 1        go (Just (_ :< Nothing)) = 1        go (Just (fibNMinus1 :< Just (fibNMinus2 :< _)))          = fibNMinus1 + fibNMinus2:}

>>> fmap fib [0..10][1,1,2,3,5,8,13,21,34,55,89]

In general, Cofree f a can be thought of as a cache that has the same shape as the recursive structure which was given as input.

A generalization of unfoldr. The starting seed is expanded into a base functor whose recursive positions contain more seeds, which are themselves expanded, and so on.

>>> :{>>> let ourEnumFromTo :: Int -> Int -> [Int]>>>     ourEnumFromTo lo hi = ana go lo where>>>         go i = if i > hi then Nil else Cons i (i + 1)>>> :}

>>> ourEnumFromTo 1 4[1,2,3,4]

An alias for unfold.

An optimized version of fold f . unfold g.

Useful when your recursion structure is shaped like a particular recursive datatype, but you're neither consuming nor producing that recursive datatype. For example, the recursion structure of quick sort is a binary tree, but its input and output is a list, not a binary tree.

>>> data BinTreeF a b = Tip | Branch b a b deriving (Functor)

>>> :{>>> let quicksort :: Ord a => [a] -> [a]>>>     quicksort = refold merge split where>>>         split []     = Tip>>>         split (x:xs) = let (l, r) = partition (<x) xs in Branch l x r>>> >>>         merge Tip            = []>>>         merge (Branch l x r) = l ++ [x] ++ r>>> :}

>>> quicksort [1,5,2,8,4,9,8][1,2,4,5,8,8,9]

An alias for refold.

Convert from one recursive representation to another.

>>> refix ["foo", "bar"] :: Fix (ListF String)Fix (Cons "foo" (Fix (Cons "bar" (Fix Nil))))

Convert from one recursive type to another.

>>> showTree $ hoist (\(NonEmptyF h t) -> NodeF [h] (maybeToList t)) ( 'a' :| "bcd")(a (b (c d)))

An effectful version of hoist.

Properties:

transverse sequenceA = pure

Examples:

The weird type of first argument allows user to decide an order of sequencing:

>>> transverse (\x -> print (void x) *> sequence x) "foo" :: IO StringCons 'f' ()Cons 'o' ()Cons 'o' ()Nil"foo"

>>> transverse (\x -> sequence x <* print (void x)) "foo" :: IO StringNilCons 'o' ()Cons 'o' ()Cons 'f' ()"foo"

A coeffectful version of hoist.

Properties:

cotransverse distAna = runIdentity

Examples:

Stateful transformations:

>>> :{cotransverse  (\(u, b) -> case b of    Nil -> Nil    Cons x a -> Cons (if u then toUpper x else x) (not u, a))  (True, "foobar") :: String:}"FoObAr"

We can implement a variant of zipWith

>>> data Pair a = Pair a a deriving Functor

>>> :{let zipWith' :: forall a b. (a -> a -> b) -> [a] -> [a] -> [b]    zipWith' f xs ys = cotransverse g (Pair xs ys) where      g :: Pair (ListF a c) -> ListF b (Pair c)      g (Pair Nil        _)          = Nil      g (Pair _          Nil)        = Nil      g (Pair (Cons x a) (Cons y b)) = Cons (f x y) (Pair a b)    :}

>>> zipWith' (*) [1,2,3] [4,5,6][4,10,18]

>>> zipWith' (*) [1,2,3] [4,5,6,8][4,10,18]

>>> zipWith' (*) [1,2,3,3] [4,5,6][4,10,18]