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
*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
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
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
[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
foldr1 :: (a -> a -> a) -> t a -> a
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
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 (
foldl1) and their advantages. In the next post, we'll move on to another recursion scheme: anamorphisms, also referred to as unfolds. Stay tuned!
Sign up now and apply for roles at companies that interest you.
Engineers who find a new job through Functional Works average a 15% increase in salary.Start with GitHubStart with TwitterStart with Stack OverflowStart with Email