# Boolean catamorphism by Mark Seemann

*The catamorphism for Boolean values is just the common ternary operator.*

This article is part of an article series about catamorphisms. A catamorphism is a universal abstraction that describes how to digest a data structure into a potentially more compact value.

This article presents the catamorphism for Boolean values, as well as how you identify it. The beginning of this article presents the catamorphism in C#, with a simple example. The rest of the article describes how I deduced the catamorphism. That part of the article presents my work in Haskell. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix.

### C# catamorphism #

The catamorphism for Boolean values is the familiar ternary conditional operator:

> DateTime.Now.Day % 2 == 0 ? "Even date" : "Odd date" "Odd date"

Given a Boolean expression, you basically provide two values: one to use in case the Boolean expression is *true*, and one to use in case it's *false*.

For Church-encoded Boolean values, the catamorphism looks like this:

T Match<T>(T trueCase, T falseCase);

This is an instance method where you must, again, supply two alternatives. When the instance represents *true*, you'll get the left-most value `trueCase`

; otherwise, when the instance represents *false*, you'll get the right-most value `falseCase`

.

The catamorphism turns out to be the same as the Church encoding. This seems to be a recurring pattern.

### Alternatives #

To be accurate, there's more than one catamorphism for Boolean values. It's only by convention that the value corresponding to *true* goes on the left, and the *false* value goes to the right. You could flip the arguments, and it would still be a catamorphism. This is, in fact, what Haskell's `Data.Bool`

module does:

Prelude Data.Bool> bool "Odd date" "Even date" $ even date "Odd date"

The module documentation calls this the *"Case analysis for the Bool type"*, instead of a catamorphism, but the two representations are isomorphic:

```
"This is equivalent to
````if p then y else x`

; that is, one can think of it as an if-then-else construct with its arguments reordered."

This is another recurring result. There's typically more than one catamorphism, but the alternatives are isomorphic. In this article series, I'll mostly present the alternative that strikes me as the one you'll encounter most frequently.
### Fix #

In this and future articles, I'll derive the catamorphism from an F-Algebra. For an introduction to F-Algebras and fixed points, I'll refer you to Bartosz Milewski's excellent article on the topic. In it, he presents a generic data type for a fixed point, as well as polymorphic functions for catamorphisms and anamorphisms. While they're available in his article, I'll repeat them here for good measure:

newtype Fix f = Fix { unFix :: f (Fix f) } cata :: Functor f => (f a -> a) -> Fix f -> a cata alg = alg . fmap (cata alg) . unFix ana :: Functor f => (a -> f a) -> a -> Fix f ana coalg = Fix . fmap (ana coalg) . coalg

This should be recognisable from Bartosz Milewski's article. With one small exception, this is just a copy of the code shown there.

### Boolean F-Algebra #

While F-Algebras and fixed points are mostly used for recursive data structures, you can also define an F-Algebra for a non-recursive data structure. As data types go, they don't get much simpler than Boolean values, which are just two mutually exclusive cases. In order to make a `Functor`

out of the definition, though, you can equip it with a *carrier type:*

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

The `Functor`

instance simply ignores the carrier type and just returns `TrueF`

and `FalseF`

, respectively. It'd seem that nothing happens, but at the type level, this is still a translation from `BoolF a`

to `BoolF b`

. Not much of a function, perhaps, but definitely an *endofunctor*.

Another note that may be in order here, as well as for all future articles in this series, is that you'll notice that most types and custom functions come with the `F`

suffix. This is simply a suffix I've added to avoid conflicts with built-in types, values, and functions, such as `Bool`

, `True`

, `and`

, and so on. The `F`

is for *F-Algebra*.

You can lift these values into `Fix`

in order to make it fit with the `cata`

function:

trueF, falseF :: Fix BoolF trueF = Fix TrueF falseF = Fix FalseF

That's all you need to identify the catamorphism.

### Haskell catamorphism #

At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (`BoolF`

), and an object `a`

, but you still need to find a morphism `BoolF a -> a`

. At first glance, this seems impossible, because neither `TrueF`

nor `FalseF`

actually contain a value of the type `a`

. How, then, can you conjure an `a`

value out of thin air?

The `cata`

function has the answer.

What you can do is to start writing the function that will become the catamorphism, basing it on `cata`

:

boolF = cata alg where alg TrueF = undefined alg FalseF = undefined

While this compiles, with its `undefined`

implementations, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type `a`

from the `TrueF`

case? You could pass an argument to the `boolF`

function:

boolF x = cata alg where alg TrueF = x alg FalseF = undefined

That seems promising, so do that for the `FalseF`

case as well:

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

This works. Since `cata`

has the type `Functor f => (f a -> a) -> Fix f -> a`

, that means that `alg`

has the type `f a -> a`

. In the case of `BoolF`

, the compiler infers that the `alg`

function has the type `BoolF a -> a`

, which is just what you need!

The `boolF`

function identifies the Boolean catamorphism, which is equivalent to representations in the beginning of the article. I called the function `boolF`

, because there's a tendency in Haskell to name the 'case analysis' or catamorphism after the type, just with a lower-case initial letter.

You can use the `boolF`

function just like the above ternary operator:

Prelude Boolean Nat> boolF "Even date" "Odd date" $ evenF dateF "Odd date"

Here, I've also used `evenF`

from the `Nat`

module shown in the next article in the series.

From the above definition of `boolF`

, it should also be clear that you can arrive at the alternative catamorphism defined by `Data.Bool.bool`

by simply flipping `x`

and `y`

.

### Basis #

A catamorphism can be used to implement most (if not all) other useful functionality. For Boolean values, that would be the standard Boolean operations *and*, *or*, and *not:*

andF :: Fix BoolF -> Fix BoolF -> Fix BoolF andF x y = boolF y falseF x orF :: Fix BoolF -> Fix BoolF -> Fix BoolF orF x y = boolF trueF y x notF :: Fix BoolF -> Fix BoolF notF = boolF falseF trueF

They work as you'd expect them to work:

Prelude Boolean> andF trueF falseF Fix FalseF Prelude Boolean> orF trueF falseF Fix TrueF Prelude Boolean> orF (notF trueF) falseF Fix FalseF

You can also implement conversion to and from the built-in `Bool`

type:

toBool :: Fix BoolF -> Bool toBool = boolF True False fromBool :: Bool -> Fix BoolF fromBool = ana coalg where coalg True = TrueF coalg False = FalseF

This demonstrates that `Fix BoolF`

is isomorphic to `Bool`

.

### Summary #

The catamorphism for Boolean values is a function, method, or operator akin to the familiar ternary conditional operator. The most common descriptions of catamorphisms that I've found emphasise how a catamorphism is like a *fold;* an operation you can use to reduce a data structure like a list or a tree to a single value. In that light, it may be surprising that something as simple as Boolean values have an associated catamorphism.

Since `Fix BoolF`

is isomorphic to `Bool`

, you may wonder what the point is. Why define this data type, and implement functions like `andF`

, `orF`

, and `notF`

?

The code presented here is nothing but an analysis tool. It's a way to identify the catamorphism for Boolean values.

**Next:** Peano catamorphism.