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

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.

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.

### Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

#### Published

Monday, 06 May 2019 12:30:00 UTC

#### Tags

"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 06 May 2019 12:30:00 UTC