Either catamorphism by Mark Seemann
The catamorphism for Either is a generalisation of its fold. The catamorphism enables operations not available via fold.
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 Either (also known as Result), as well as how to identify it. The beginning of this article presents the catamorphism in C#, with examples. The rest of the article describes how to deduce the catamorphism. This 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.
Either is a data container that models two mutually exclusive results. It's often used to return values that may be either correct (right), or incorrect (left). In statically typed functional programming with a preference for total functions, Either offers a saner, more reasonable way to model success and error results than throwing exceptions.
C# catamorphism #
This article uses the Church encoding of Either. The catamorphism for Either is the Match method:
T Match<T>(Func<L, T> onLeft, Func<R, T> onRight);
Until this article, all previous catamorphisms have been a pair made from an initial value and a function. The Either catamorphism is a generalisation, since it's a pair of functions. One function handles the case where there's a left value, and the other function handles the case where there's a right value. Both functions must return the same, unifying type, which is often a string or something similar that can be shown in a user interface:
> IEither<TimeSpan, int> e = new Left<TimeSpan, int>(TimeSpan.FromMinutes(3)); > e.Match(ts => ts.ToString(), i => i.ToString()) "00:03:00" > IEither<TimeSpan, int> e = new Right<TimeSpan, int>(42); > e.Match(ts => ts.ToString(), i => i.ToString()) "42"
You'll often see examples like the above that turns both left and right cases into strings or something that can be represented as a unifying response type, but this is in no way required. If you can come up with a unifying type, you can convert both cases to that type:
> IEither<Guid, string> e = new Left<Guid, string>(Guid.NewGuid()); > e.Match(g => g.ToString().Count(c => 'a' <= c), s => s.Length) 12 > IEither<Guid, string> e = new Right<Guid, string>("foo"); > e.Match(g => g.ToString().Count(c => 'a' <= c), s => s.Length) 3
In the two above examples, you use two different functions that both reduce respectively Guid and string values to a number. The function that turns Guid values into a number counts how many of the hexadecimal digits that are greater than or equal to A (10). The other function simply returns the length of the string, if it's there. That example makes little sense, but the Match method doesn't care about that.
In practical use, Either is often used for error handling. The article on the Church encoding of Either contains an example.
Either F-Algebra #
As in the previous article, I'll use Fix and cata as explained in Bartosz Milewski's excellent article on F-Algebras.
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. You already saw an example of that in the articles about Boolean catamorphism and Maybe catamorphism. The difference between e.g. Maybe values and Either is that both cases of Either carry a value. You can model this as a Functor with both a carrier type and two type arguments for the data that Either may contain:
data EitherF l r c = LeftF l | RightF r deriving (Show, Eq, Read) instance Functor (EitherF l r) where fmap _ (LeftF l) = LeftF l fmap _ (RightF r) = RightF r
I chose to call the 'data types' l (for left) and r (for right), and the carrier type c (for carrier). As was also the case with BoolF and MaybeF, the Functor instance ignores the map function because the carrier type is missing from both the LeftF case and the RightF case. Like the Functor instances for BoolF and MaybeF, it'd seem that nothing happens, but at the type level, this is still a translation from EitherF l r c to EitherF l r c1. Not much of a function, perhaps, but definitely an endofunctor.
As was also the case when deducing the Maybe and List catamorphisms, Haskell isn't too happy about defining instances for a type like Fix (EitherF l r). To address that problem, you can introduce a newtype wrapper:
newtype EitherFix l r = EitherFix { unEitherFix :: Fix (EitherF l r) } deriving (Show, Eq, Read)
You can define Functor, Applicative, Monad, etc. instances for this type without resorting to any funky GHC extensions. Keep in mind that ultimately, the purpose of all this code is just to figure out what the catamorphism looks like. This code isn't intended for actual use.
A pair of helper functions make it easier to define EitherFix values:
leftF :: l -> EitherFix l r leftF = EitherFix . Fix . LeftF rightF :: r -> EitherFix l r rightF = EitherFix . Fix . RightF
With those functions, you can create EitherFix values:
Prelude Data.UUID Data.UUID.V4 Fix Either> leftF <$> nextRandom
EitherFix {unEitherFix = Fix (LeftF e65378c2-0d6e-47e0-8bcb-7cc29d185fad)}
Prelude Data.UUID Data.UUID.V4 Fix Either> rightF "foo"
EitherFix {unEitherFix = Fix (RightF "foo")}
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 (EitherF l r), and an object c, but you still need to find a morphism EitherF l r c -> c. Notice that the algebra you have to find is the function that reduces the functor to its carrier type c, not the 'data types' l and r. This takes some time to get used to, but that's how catamorphisms work. This doesn't mean, however, that you get to ignore l and r, as you'll see.
As in the previous articles, start by writing a function that will become the catamorphism, based on cata:
eitherF = cata alg . unEitherFix where alg (LeftF l) = undefined alg (RightF r) = 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 c from the LeftF case? You could pass an argument to the eitherF function:
eitherF fl = cata alg . unEitherFix where alg (LeftF l) = fl l alg (RightF r) = undefined
While you could, technically, pass an argument of the type c to eitherF and then return that value from the LeftF case, that would mean that you would ignore the l value. This would be incorrect, so instead, make the argument a function and call it with l. Likewise, you can deal with the RightF case in the same way:
eitherF :: (l -> c) -> (r -> c) -> EitherFix l r -> c eitherF fl fr = cata alg . unEitherFix where alg (LeftF l) = fl l alg (RightF r) = fr r
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 EitherF, the compiler infers that the alg function has the type EitherF l r c -> c, which is just what you need!
You can now see what the carrier type c is for. It's the type that the algebra extracts, and thus the type that the catamorphism returns.
This, then, is the catamorphism for Either. As has been consistent so far, it's a pair, but now made from two functions. As you've seen repeatedly, this isn't the only possible catamorphism, since you can, for example, trivially flip the arguments to eitherF.
I've chosen the representation shown here because it's isomorphic to the either function from Haskell's built-in Data.Either module, which calls the function the "Case analysis for the Either type". Both of these functions (eitherF and either) are equivalent to the above C# Match method.
Basis #
You can implement most other useful functionality with eitherF. Here's the Bifunctor instance:
instance Bifunctor EitherFix where bimap f s = eitherF (leftF . f) (rightF . s)
From that instance, the Functor instance trivially follows:
instance Functor (EitherFix l) where fmap = second
On top of Functor you can add Applicative:
instance Applicative (EitherFix l) where pure = rightF f <*> x = eitherF leftF (<$> x) f
Notice that the <*> implementation is similar to to the <*> implementation for MaybeFix. The same is the case for the Monad instance:
instance Monad (EitherFix l) where x >>= f = eitherF leftF f x
Not only is EitherFix Foldable, it's Bifoldable:
instance Bifoldable EitherFix where bifoldMap = eitherF
Notice, interestingly, that bifoldMap is identical to eitherF.
The Bifoldable instance enables you to trivially implement the Foldable instance:
instance Foldable (EitherFix l) where foldMap = bifoldMap mempty
You may find the presence of mempty puzzling, since bifoldMap (or eitherF; they're identical) takes as arguments two functions. Is mempty a function?
Yes, mempty can be a function. Here, it is. There's a Monoid instance for any function a -> m, where m is a Monoid instance, and mempty is the identity for that monoid. That's the instance in use here.
Just as EitherFix is Bifoldable, it's also Bitraversable:
instance Bitraversable EitherFix where bitraverse fl fr = eitherF (fmap leftF . fl) (fmap rightF . fr)
You can comfortably implement the Traversable instance based on the Bitraversable instance:
instance Traversable (EitherFix l) where sequenceA = bisequenceA . first pure
Finally, you can implement conversions to and from the standard Either type, using ana as the dual of cata:
toEither :: EitherFix l r -> Either l r toEither = eitherF Left Right fromEither :: Either a b -> EitherFix a b fromEither = EitherFix . ana coalg where coalg (Left l) = LeftF l coalg (Right r) = RightF r
This demonstrates that EitherFix is isomorphic to Either, which again establishes that eitherF and either are equivalent.
Relationships #
In this series, you've seen various examples of catamorphisms of structures that have no folds, catamorphisms that coincide with folds, and now a catamorphism that is more general than the fold. The introduction to the series included this diagram:
This shows that Boolean values and Peano numbers have catamorphisms, but no folds, whereas for Maybe and List, the fold and the catamorphism is the same. For Either, however, the fold is a special case of the catamorphism. The fold for Either 'pretends' that the left side doesn't exist. Instead, the left value is interpreted as a missing right value. Thus, in order to fold Either values, you must supply a 'fallback' value that will be used in case an Either value isn't a right value:
Prelude Fix Either> e = rightF LT :: EitherFix Integer Ordering Prelude Fix Either> foldr (const . show) "" e "LT" Prelude Fix Either> e = leftF 42 :: EitherFix Integer Ordering Prelude Fix Either> foldr (const . show) "" e ""
In a GHCi session like the above, you can create two Either values of the same type. The right case is an Ordering value, while the left case is an Integer value.
With foldr, there's no way to access the left case. While you can access and transform the right Ordering value, the number 42 is simply ignored during the fold. Instead, the default value "" is returned.
Contrast this with the catamorphism, which can access both cases:
Prelude Fix Either> e = rightF LT :: EitherFix Integer Ordering Prelude Fix Either> eitherF show show e "LT" Prelude Fix Either> e = leftF 42 :: EitherFix Integer Ordering Prelude Fix Either> eitherF show show e "42"
In a session like this, you recreate the same values, but using the catamorphism eitherF, you can now access and transform both the left and the right cases. In other words, the catamorphism enables you to perform operations not possible with the fold.
It's interesting, however, to note that while the fold is a specialisation of the catamorphism, the bifold is identical to the catamorphism.
Summary #
The catamorphism for Either is a pair of functions. One function transforms the left case, while the other function transforms the right case. For any Either value, only one of those functions will be used.
When I originally encountered the concept of a catamorphism, I found it difficult to distinguish between catamorphism and fold. My problem was, I think, that the tutorials I ran into mostly used linked lists to demonstrate how, in that case, the fold is the catamorphism. It turns out, however, that this isn't always the case. A catamorphism is a general abstraction. A fold, on the other hand, seems to me to be mostly related to collections.
In this article you saw the first example of a catamorphism that can do more than the fold. For Either, the fold is just a special case of the catamorphism. You also saw, however, how the catamorphism was identical to the bifold. Thus, it's still not entirely clear how these concepts relate. Therefore, in the next article, you'll get an example of a container where there's no bifold, and where the catamorphism is, indeed, a generalisation of the fold.
Next: Tree catamorphism.
