1

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.

Conor Quinn
  • 529
  • 4
  • 13
  • 2
    The corresponding identity to `foldr (:) []` is `unfoldr uncons`. But what kind of `Int -> Int` function are you looking for? There's no structure there to construct, destruct, or otherwise recurse over. – user11228628 May 06 '19 at 20:32
  • 1
    @user11228628 There would be an unfold that wouldn't be entirely trivial if the OP were using recursively defined naturals, though I'm not exactly sure about how relevant doing so would be to this specific question. – duplode May 06 '19 at 20:38
  • I'm looking for something that will recurse based on an input integer and also return an integer. Something like fact using a recursion scheme. – Conor Quinn May 06 '19 at 20:38
  • factorial 0 = 1 factorial n = n * factorial (n - 1) – Conor Quinn May 06 '19 at 20:39
  • You can write factorial with a `hylo`morphism; are you asking for how exactly to do that? That question seems unrelated to whether unfoldl/r can be used to define the identity function, since factorial isn't the identity function. – user11228628 May 06 '19 at 20:43
  • I asked about it in those terms because I've always thought about fold and unfold as being symmetric. I'm just looking for a recursion scheme that takes and Int and returns an Int. I'm looking into the Nat base type and that looks promising. – Conor Quinn May 06 '19 at 20:51
  • If it is best done with a hylomorphism how to do it would be the answer im looking for. – Conor Quinn May 06 '19 at 20:51
  • Maybe you could edit the question to make that more clear? From the headline and the first half of the body, it really looks like you're asking for `unfoldr uncons` instead of an explanation of how recursion schemes could be used to define functions that stay within `Int`. – user11228628 May 06 '19 at 21:04

2 Answers2

4

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

duplode
  • 33,731
  • 7
  • 79
  • 150
3

The kind of recursion scheme that deals with building up an intermediate structure and tearing it down, so that the structure doesn't appear in the input or output, is a hylomorphism, spelled hylo in recursion-schemes.

To use a hylomorphism, you need to specify an algebra (something that consumes one step of a recursive structure) and a coalgebra (something that produces one step of a recursive structure), and you need to have a data type for the kind of structure you're using, of course.

You suggested factorial, so let's look into how to write that as a hylomorphism.

One way to look at factorial is as the product of a list of numbers counting down from the initial n. In this framing, we can think of the product as our algebra, tearing down the list one cons at a time, and the count-down as our coalgebra, building up the list as n is decremented.

recursion-schemes gives us ListF as a handy base functor for lists, so we'll use that as the data type produced by the coalgebra and consumed by the algebra. Its constructors are Nil and Cons, which of course resemble the constructors for full lists, except that a ListF, like any base structure in a recursion scheme, uses a type parameter in the place that lists would use actual recursion (meaning that Cons :: a -> b -> ListF a b instead of (:) :: a -> [a] -> [a]).

So that determines our types. Now defining fact is a rather fill-in-the-blanks exercise:

import Prelude hiding (product)
import Data.Functor.Foldable

product :: ListF Int Int -> Int
product Nil = 1
product (Cons a b) = a * b

countDown :: Int -> ListF Int Int
countDown 0 = Nil
countDown n = Cons n (n - 1)

fact :: Int -> Int
fact = hylo product countDown
user11228628
  • 1,526
  • 1
  • 6
  • 17