# 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.)