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