We're planting a tree for every job application! Click here to learn more

Folding Nonempty Structures In Haskell

Marty Stumpf

7 Apr 2022

•

3 min read

Folding Nonempty Structures In Haskell
  • 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!

Did you like this article?

Marty Stumpf

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

See other articles by Marty

Related jobs

See all

Title

The company

  • Remote

Title

The company

  • Remote

Title

The company

  • Remote

Title

The company

  • Remote

Related articles

JavaScript Functional Style Made Simple

JavaScript Functional Style Made Simple

Daniel Boros

•

12 Sep 2021

JavaScript Functional Style Made Simple

JavaScript Functional Style Made Simple

Daniel Boros

•

12 Sep 2021

WorksHub

CareersCompaniesSitemapFunctional WorksBlockchain WorksJavaScript WorksAI WorksGolang WorksJava WorksPython WorksRemote Works
hello@works-hub.com

Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ

108 E 16th Street, New York, NY 10003

Subscribe to our newsletter

Join over 111,000 others and get access to exclusive content, job opportunities and more!

© 2024 WorksHub

Privacy PolicyDeveloped by WorksHub