In the last post I talked about catamorphisms in OCaml.  In this post I compare that with Haskell.  We’ll see that Haskell gives you more options when implementing catamorphisms.  You don’t need to know Haskell to understand this post, I’ll introduce the required Haskell syntax along the way.

Catamorphisms in Haskell

As mentioned in the last post, the famous paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire” by Meijer et al.  shows that we can treat recursions as separate higher order functions known as recursion schemes.  One type of recursion schemes is catamorphisms (or fold in Richard Bird and Philip Wadler’s ‘Introduction to Functional Programming’) .

In Haskell, we use foldl and foldr to fold lists.  They are equivalent to fold_left and fold_right in OCaml (see the last post).  E.g., to sum all the elements of a list in Haskell using foldr (of course the standard sum function does exactly that):

Prelude> foldr (+) 0 [1,2,3]
6

Similar to OCaml, foldr takes the function as the first argument, then the base case, and finally the list.  We can eta reduce away the list and define the sum, product, and, and or of all elements of a list with just the function and the base case:

--In Haskell, we don't need to write 'let' to define a variable.
sum = foldr (+) 0
product = foldr (*) 1
and = foldr (&&) True
or = foldr (||) False

Folding Nonempty Lists In Haskell

One advantage of Haskell over OCaml is that Haskell provides a way to fold nonempty lists.  Because the base cases are there to safeguard an empty list input, when the input list is nonempty, we can omit the base case.  We use foldr1 or foldl1 to tell Haskell that the input list is nonempty:

--Define sumn to be the result of foldr1 (+).
Prelude> sumn = foldr1 (+)      
--Ask Haskell sumn's type.
Prelude> :t sumn     
--Haskell's output of sumn's type: 
sumn :: (Foldable t, Num a) => t a -> a

However, if the input list is empty, Haskell throws an exception:

Prelude> sumn []
*** Exception: Prelude.foldr1: empty list

Not needing to specify the base case avoids mistakes.  Remember that the base case has to not alter the result of the function, unless, of course, you intend for it to.  E.g., the compiler cannot catch the typo of this base case:

Prelude> sum = foldr (+) 1
--sum is the sum of all elements in the list plus 1.
Prelude> sum [1,2,3]
7

Preserving Polymorphism in Haskell

In my last post, I use the example of finding the minimum of an array in OCaml:

let find_min = Array.fold_left min max_int;;

find_min is not polymorphic because the base case max_int is of type int, implying that the result of find_min has to be an int.

Haskell provide a couple options that preserve polymorphisms:

Using the Bounded Class

You can preserve the polymorphism by using maxBound as the base case.  TheBounded class is used to name the upper and lower limits of any type that can be bounded.  That is, using maxBound, you are telling Haskell the base case is the maximum of any type:

find_min = foldr min maxBound

--Inputting an empty list to find_min returns the unit, not an exception. 
Prelude> find_min []
()

--There are multiple number types in Haskell, so without annotations Haskell gives an error.
Prelude> find_min [1,2,3,0]

<interactive>:5:1: error:
• Ambiguous type variable ‘a0’ arising from a use of ‘print’
prevents the constraint ‘(Show a0)’ from being solved.
Probable fix: use a type annotation to specify what ‘a0’ should be.
...

--Telling Haskell it's an Int list solves the problem.
Prelude> find_min [1,2,3,0::Int]
0

--It works on Char
Prelude> find_min ['a','b','c']
'a'

--It does not work on String, because String is not bounded.
Prelude> find_min ["string","works","too"]

<interactive>:6:1: error:
    • No instance for (Bounded [Char]) arising from a use of ‘find_min’
    • In the expression: find_min ["string", "works", "too"]
      In an equation for ‘it’: it = find_min ["string", "works", "too"]

Using the Bounded class only works for types that can be bounded though.  What about types that can’t be bounded?

Using Nonempty List Folds

Because the nonempty list folds in Haskell do not require base cases, find_min in Haskell can be polymorphic, even to types that are not bounded:

find_min = foldr1 min

--find_min works on Int lists.
Prelude> find_min [1,2,3,0]
0

--find_min also works on String lists.
Prelude> find_min ["string","works","too"]
"string"

Cool right?  In the next post, I show how one can mimic foldr1 or foldl1 in OCaml and get all these advantages in OCaml as well!