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

**. They are equivalent to**

*foldr*to fold lists*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***of all elements of a list with just the function and the base case:**

*or*--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. The`Bounded 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!

## Leave a Reply