haskellrecursionorder-of-executionrecursion-schemes# Top-down recursion schemes

Can we define a recursion scheme (without losing any of their generality) that ** constructs the value top-down**, instead of bottom-up?

This would be quite helpful as I've seen plenty of times where the function, defined internally with a recursion scheme was first applying `reverse`

to its input, clearly signalling the need for a `foldl`

-like "front to back" execution.

Solution

Although it's a common belief that `cata`

works "bottom-up", it can actually express many "top-down" constructions, by instantiating the carrier with a function whose parameter is the information being passed "top-down":

```
cata :: (F c -> c ) -> Fix F -> c -- general signature
:: (F (i -> d) -> (i -> d)) -> Fix F -> i -> d -- with c = (i -> d)
```

That's how you can implement `foldl`

or `reverse`

using `foldr`

(which is `cata`

for lists).

```
-- foldl :: (b -> a -> b) -> b -> [a] -> b
-- using
-- foldr :: (a -> (b -> b) -> (b -> b)) -> (b -> b) -> [a] -> b -> b
foldl f b xs = foldr (\x go z -> go (f z x)) id xs b
```

Here's another example to label a tree by depth, counting from the root:

```
data Tree a = Node (Tree a) a (Tree a) | Leaf
makeBaseFunctor ''Tree -- recursion-schemes
byDepth :: Tree a -> Tree Integer
byDepth t = cata byDepthF t 0 where
byDepthF :: TreeF a (Integer -> Tree Integer) -> Integer -> Tree Integer
byDepthF (NodeF u _ v) !d = Node (u (d + 1)) d (v (d + 1))
byDepthF LeafF = Leaf
```

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code