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.
