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 register
to publish this job!

Login or register
to save this job!

Login or register
to save interesting jobs!

Login or register
to get access to all your job applications!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel 🚀.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Login or register
to save articles!

Login to see the application

Engineers who find a new job through Functional Works average a 15% increase in salary 🚀

You will be redirected back to this page right after signin

Blog hero image

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

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"
Join our newsletter
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!

Author's avatar
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
  • 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.

Start with GitHubStart with Stack OverflowStart with Email