haskellrecursionfoldrecursion-schemescatamorphism# How to define the fibonacci sequence using a fold for natural numbers?

I am currently learning folds in the sense of structural recursion/catamorphisms. I implemented power and factorial using a fold for natural numbers. Please note that I barely know Haskell, so the code is probably awkward:

```
foldNat zero succ = go
where
go n = if (n <= 0) then zero else succ (go (n - 1))
pow n = foldNat 1 (n*)
fact n = foldNat 1 (n*) n
```

Next I wanted to adapt the fibonacci sequence:

```
fib n = go n (0,1)
where
go !n (!a, !b) | n==0 = a
| otherwise = go (n-1) (b, a+b)
```

With `fib`

I have a pair as second argument whose fields are swapped at each recursive call. I am stuck at this point, because I don't understand the mechanics of the conversion process.

[EDIT]

As noted in the comments my `fact`

function is wrong. Here is a new implementation based on a paramorphism (hopefully):

```
paraNat zero succ = go
where
go n = if (n <= 0) then zero else succ (go (n - 1), n)
fact = paraNat 1 (\(r, n) -> n * r)
```

Solution

Let the types guide you. Here is your `foldNat`

, but with a type signature:

```
import Numeric.Natural
foldNat :: b -> (b -> b) -> Natural -> b
foldNat zero succ = go
where
go n = if (n <= 0) then zero else succ (go (n - 1))
```

Having another look at the `go`

helper in your implementation of `fib`

, we can note the recursive case takes and returns a `(Natural, Natural)`

pair. Comparing that with the successor argument to `foldNat`

suggests we want `b`

to be `(Natural, Natural)`

. That is a nice hint on how the pieces of `go`

should fit:

```
fibAux = foldNat (0, 1) (\(a, b) -> (b, a + b))
```

(I am ignoring the matter of strictness for now, but I will get back to that.)

This is not quite `fib`

yet, as can be seen by looking at the result type. Fixing that, though, is no problem, as Robin Zigmond notes:

```
fib :: Natural -> Natural
fib = fst . foldNat (0, 1) (\(a, b) -> (b, a + b))
```

At this point, you might want to work backwards and substitute the definition of `foldNat`

to picture how this corresponds to an explicitly recursive solution.

While this is a perfectly good implementation of `fib`

, there is one major difference between it and the one you had written: this one is a lazy right fold (as is the norm for Haskell catamorphisms), while yours was clearly meant as a strict left fold. (And yes, it does make sense to use a strict left fold here: in general, if what you are doing looks like arithmetic, you ideally want strict left, while if it looks like building a data structure, you want lazy right). The good news, though, is that we can use catamorphisms to define pretty much anything that consumes a value recursively... including strict left folds! Here I will use an adapted version of the foldl-from-foldr trick (see this question for a detailed explanation of that in the case of lists), which relies on a function like this:

```
lise :: (b -> b) -> ((b -> b) -> (b -> b))
lise suc = \g -> \n -> g (suc n)
```

The idea is that we take advantage of function composition (`\n -> g (suc n)`

is the same as `g . suc`

) to do things in the opposite order -- it is as if we swapped `succ`

and `go`

in the right hand side of your definition of `go`

. `lise suc`

can be used as the successor argument to `foldNat`

. That means we will get a `b -> b`

function in the end rather than a `b`

, but that is not a problem because we can apply it to the zero value ourselves.

Since we want a *strict* left fold, we have to sneak in a `($!)`

to make sure `suc n`

is eagerly evaluated:

```
lise' :: (b -> b) -> ((b -> b) -> (b -> b))
lise' suc = \g -> \n -> g $! suc n
```

Now we can define a strict left fold (it is to `foldNat`

what `foldl'`

from `Data.List`

is to `foldr`

):

```
foldNatL' :: b -> (b -> b) -> Natural -> b
foldNatL' zero suc n = foldNat id (lise' suc) n zero
```

There is a final, important detail to deal with: making the fold strict is of little use if we are lazily building a pair along the way, as the pair components will remain being built lazily. We could deal with that by using `($!)`

along with `(,)`

for building the pair in the successor function. However, I believe it is nicer to use a strict pair type instead so that we don't have to worry with that:

```
data SP a b = SP !a !b
deriving (Eq, Ord, Show)
fstSP :: SP a b -> a
fstSP (SP a _) = a
sndSP :: SP a b -> b
sndSP (SP _ b) = b
```

The `!`

mark the fields as strict (note that you don't need to enable `BangPatterns`

to use them).

With everything in place, we can at last have `fib`

as a strict left fold:

```
fib' :: Natural -> Natural
fib' = fstSP . foldNatL' (SP 0 1) (\(SP a b) -> SP b (a + b))
```

P.S.: As amalloy notes, your `fac`

calculates *n^n* rather than *n!*. That is probably a matter better left for a separate question; in any case, the gist of it is that factorial is more naturally expressed as a paramorphism on naturals, rather than as a plain catamorphism. (For more on that, see, for instance, the *Practical Recursion Schemes* blog post by Jared Tobin, more specifically the section about paramorphisms.)

- 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