We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

# Login or registerto boost this post!

Show some love to the author of this blog by giving their post some rocket fuel ðŸš€.

# Login to see the application

Engineers who find a new job through Functional Works average a 15% increase in salary ðŸš€

# Folding Nonempty Structures In Haskell

Marty Stumpf 7 May, 2021 | 3 min read

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
``````

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"
``````
Join over 111,000 others and get access to exclusive content, job opportunities and more!

## 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!

Marty Stumpf
Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.

## Related Issues

cosmos / gaia
• Started
• 0
• 6
• Intermediate
• Go
cosmos / gaia
• Started
• 0
• 3
• Intermediate
• Go
cosmos / ibc
• Started
• 0
• 2
• Intermediate
• TeX
cosmos / ibc
• Open
• 0
• 0
• Intermediate
• TeX

### Get hired!

#### 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.