haskellrecursion-schemescatamorphismanamorphism# A recursion scheme from Int -> Int?

The foldr identity is

```
foldr (:) []
```

More generally, with folds you can either destroy structure and end up with a summary value or inject structure in such a way that you end up with the same output structure.

`[Int] -> [Int]`

or
`[Int] -> Int`

or
`[Int] -> ?`

I'm wondering if there a similar identity with unfoldr/l.

I know how to get

`Int -> [Int]`

with unfold/ana.

I'm looking for some kind of way to go from

`Int -> Int`

with a recursion scheme.

Solution

Taking a cue from your remark about factorials, we can note that natural numbers can be treated as a recursive data structure:

```
data Nat = Zero | Succ Nat
```

In terms of the *recursion-schemes* machinery, the corresponding base functor would be:

```
data NatF a = ZeroF | SuccF a
deriving (Functor)
```

`NatF`

, however, is isomorphic to `Maybe`

. That being so, *recursion-schemes* conveniently makes `Maybe`

the base functor of the `Natural`

type from *base*. For instance, here is the type of `ana`

specialised to `Natural`

:

```
ana @Natural :: (a -> Maybe a) -> a -> Natural
```

We can use it to write the identity unfold for `Natural`

:

```
{-# LANGUAGE LambdaCase #-}
import Numeric.Natural
import Data.Functor.Foldable
idNatAna :: Natural -> Natural
idNatAna = ana $ \case
0 -> Nothing
x -> Just (x - 1)
```

The coalgebra we just gave to `ana`

is `project`

for `Natural`

, `project`

being the function that unwraps one layer of the recursive structure. In terms of the *recursion-schemes* vocabulary, `ana project`

is the identity unfold, and `cata embed`

is the identity fold. (In particular, `project`

for lists is `uncons`

from `Data.List`

, except that it is encoded with `ListF`

instead of `Maybe`

.)

By the way, the factorial function can be expressed as a paramorphism on naturals (as pointed out in the note at the end of this question). We can also implement that in terms of *recursion-schemes*:

```
fact :: Natural -> Natural
fact = para $ \case
Nothing -> 1
Just (predec, prod) -> prod * (predec + 1)
```

`para`

makes available, at each recursive step, the rest of the structure to be folded (if we were folding a list, that would be its tail). In this case, I have called the value thus provided `predec`

because at the `n`

-th recursive step from bottom to top `predec`

is `n - 1`

.

Note that user11228628's hylomorphism is probably a more efficient implementation, if you happen to care about that. (I haven't benchmarked them, though.)

- 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