haskellfoldrecursion-schemesfoldablecatamorphism# Can I write `foldr` (or `foldMap`) in terms of 'recursion schemes' `cata`?

I recently read about recursion schemes where catamorphisms are described as analogous to generalized `foldr`

.

Is is possible to write an instance of `Foldable`

(via either `foldr`

or `foldMap`

) in terms of `cata`

in all cases?

Solution

You often can, but not universally. All it takes is a single counter-example. Several exist, but consider the simplest one that comes to (my) mind.

While completely unnecessary, you can define Boolean values with an F-algebra:

```
data BoolF a = TrueF | FalseF deriving (Show, Eq, Read)
instance Functor BoolF where
fmap _ TrueF = TrueF
fmap _ FalseF = FalseF
```

From this (as the linked article explains) you can derive the catamorphism:

```
boolF :: a -> a -> Fix BoolF -> a
boolF x y = cata alg
where alg TrueF = x
alg FalseF = y
```

The type `Fix BoolF`

is isomorphic to `Bool`

, which isn't parametrically polymorphic (i.e. it doesn't have a type parameter), yet a catamorphism exists.

The `Foldable`

type class, on the other hand, is defined for a parametrically polymorphic container `t`

, e.g.

```
foldr :: (a -> b -> b) -> b -> t a -> b
```

Since `Bool`

isn't parametrically polymorphic, it can't be `Foldable`

, yet a catamorphism exists. The same is true for Peano numbers.

For parametrically polymorphic types, on the other hand, you often (perhaps always?) can. Here's a `Foldable`

instance for a tree defined with its catamorphism:

```
instance Foldable TreeFix where
foldMap f = treeF (\x xs -> f x <> fold xs)
```

Here's one for `Maybe`

:

```
instance Foldable MaybeFix where
foldMap = maybeF mempty
```

and one for linked lists:

```
instance Foldable ListFix where
foldr = listF
```

- 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