haskellrecursionbinary-treerecursion-schemes# Is it possible to create efficient recombining trees using (co)recursion?

By co-recursion I mean unfolding a tree, such as with `ana`

morphism from Ed Kmett's recursion-schemes

By re-combining trees I mean graphs that share structure. For example, a binomial option pricing tree, or Pascal's triangle. Both of these have some symmetry, so for efficiency, we would like to avoid re-calculating part of the tree, instead re-using the already-calculated branches.

n.b. this question is *not* about some clever way to calculate the values in aforementioned examples; it's a general question about recursion.

For example, for options pricing, the tree can be generated like so:

```
data Tree x = Leaf x | Branch x (Tree x) (Tree x)
ana \(x, depth) ->
if depth == maxDepth
then LeafF x
else BranchF x (p * x, depth + 1) ( (1.0 - p) * x, depth + 1) -- p < 1.0
```

So the value in an 'up' branch is `p * x`

and the value in a 'down' branch is `(1-p) * x`

. Because of this symmetry, an 'up' followed by a 'down' node will have the same value as a 'down' followed by an 'up' branch. As will it's entire sub-tree.

I think it may be possible to do this passing along `State`

that contains a hashmap of already calculated nodes somehow.

Or if I could somehow access the already-calculated subtree, I could pass it in as a `Left`

in an `apo`

morphism.

Is there some existing morphism that allows this? Or can I code my own?

Solution

`ana`

defines a recursive function `x -> Tree a`

(given a coalgebra `alg :: x -> TreeF a x`

). You can define a memoized version of `ana`

by using a specialized fixpoint operator (whereas the usual definition is more or less equivalent to using `fix`

), for example, as found in the MemoTrie library.

```
memoFix :: (...) => ((a -> b) -> (a -> b)) -> (a -> b)
-- for some constraints "(...)" depending on the implementation.
```

```
-- ana': Memoized version of ana
type Memo a b = ((a -> b) -> (a -> b)) -> a -> b
memoAna :: Memo x (Tree a) -> (x -> TreeF a x) -> x -> Tree a
memoAna memo alg = memo $ \ana_ x ->
case alg x of
LeafF a -> Leaf a
BranchF a x1 x2 -> Branch a (ana_ x1) (ana_ x2)
ana' :: HasTrie x => (x -> TreeF a x) -> x -> Tree a
ana' = memoAna memoFix
```

This ensures all trees generated from the same seed `x`

will in fact be the same tree.

You also have to be a little careful with the type of seed. In your example, with `(Double, Int)`

, the imprecision of `Double`

operations makes memoization unreliable. So you also need to modify the algebra. For example, since the price is always of the form `p^i (1-p)^(depth-i)`

, you could remember the index `i`

instead.

```
optionsAlg' :: Num a => a -> (Int, Int) -> TreeF a (Int, Int)
optionsAlg' p (ups, depth) =
if depth >= maxDepth then
LeafF price
else
BranchF price (ups+1, depth+1) (ups, depth+1)
where
price = p ^ ups * (1 - p) ^ (depth - ups)
```

Implementations of memoization have various trade offs. Depending on your particular use case, further optimizations and more adaptation may be necessary.

- 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