Folding Nonempty Structures In Haskell

This is the fifth of a series of articles that illustrates functional programming (FP) concepts. As you go through these articles with code examples in Haskell (a very popular FP language), you gain the grounding for picking up any FP language quickly. Why should you care about FP? See this post.

In the last post, we learned about catamorphism/folds with an example function using foldr in Haskell. In this post, we'll learn about the variants for folding nonempty structures and some of their advantages.

Recall the signature of foldr:

*Main> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

It takes a function, the base case, and a foldable structure as inputs. Because the base case is the output for 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:

Prelude> sumn = foldr1 (+)      
Prelude> :t sumn     
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 certain mispecifications. For example, when you want to sum all elements of a list, 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 a list:

findMinFold :: [Int] -> Int
findMinFold = foldr min maxBound

Recall that the base case is maxBound, of type:

Prelude> :t maxBound
maxBound :: Bounded a => a

This restricts a to be an instance of the Bounded typeclass. That is, findMinFold only works on any type that are bounded. For example,

-- it works on Char
Prelude> findMinFold ['a','b','c']
'a'

It does not work on String, because String or [Char] is not bounded:

Prelude> findMinFold ["string","works","too"]

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

Using nonempty structures folds makes the function polymorphic to any type. Looking at foldr1's signature, you can see that there are no requirement for a:

foldr1 :: (a -> a -> a) -> t a -> a

Using foldr1, findMin1 is more polymorphic, because it works for even types that are not bounded:

findMin1 = foldr1 min

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

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

Making Use of the NonEmpty Type to Avoid Exceptions

foldr1 and foldl1 seem really useful, but getting an exception when the list is empty is not ideal. Statically typed languages (including Haskell) can help with this. Statically typed languages type check (verify all functions have the correct input types passed to them) at compile-time as opposed to run-time. We can thus specify that the input type is a nonempty type.

The nonempty list type is already defined for you in Data.List.NonEmpty:

data NonEmpty a
  a :| [a]

The advantage of using it is that Haskell treats it like lists, and thus you can use all the list operations on NonEmpty lists.

-- Import the library that supports NonEmpty
Prelude> import Data.List.NonEmpty

--Define findMin1 such that its input type is NonEmpty
Prelude Data.List.NonEmpty> findMin1 = foldr1 min :: (Ord a) => NonEmpty a -> a
Prelude Data.List.NonEmpty> findMin1 (1:|[2,3,0])
0
Prelude Data.List.NonEmpty> findMin1 ("strings":|["works","too"])
"strings"

--Type error occurs when the input list is empty.
Prelude Data.List.NonEmpty> findMin1 []

<interactive>:5:10: error:
    • Couldn't match expected type ‘NonEmpty a’ with actual type ‘[a0]’
    • In the first argument of ‘findMin1’, namely ‘[]’
      In the expression: findMin1 []
      In an equation for ‘it’: it = findMin1 []
    • Relevant bindings include it :: a (bound at <interactive>:5:1)

Okay! You've learned Haskell's many methods for folds (foldr, foldl, foldr1, foldl1) and their advantages. In the next post, we'll move on to another recursion scheme: anamorphisms, also referred to as unfolds. Stay tuned!