fold are convenient ways to combine all of the elements of a list. This kind of operation is sometimes described as reducing (although the outcome is not necessarily any “smaller” than the original list). We often use folds instead of for loops when we work with lists in a “functional” programming style.
The three functions we’ll be using all come from the Data.Foldable module.
import Data.Foldable (foldr, foldMap, fold)
One of the examples in this program will be a function named
sum. Since the standard prelude provides a function with the same name, we hide the one that comes from
Prelude to remove it from scope in this module.
import Prelude hiding (sum)
The sum of a list of integers is an integer.
sum :: [Integer] -> Integer
We calculate a sum by adding each list element to the total, starting from zero.
sum xs = foldr (+) 0 xs
Suppose we have a list of words, and we want to combine them all into a single
String that contains the words separated by commas.
commaList :: [String] -> String
This is a somewhat different task than summing numbers, but it can also be expressed using
foldr because it follows the same pattern. This time the “total” is a
String instead of an
Integer. The iteration begins with an empty string, and proceeds by concatenating each element along with a comma. We do not add a comma the first time, because the overall result should contain one fewer comma than the number of items in the list.
= foldr commaSep "" xs commaList xs where "" = x commaSep x = x ++ ", " ++ phrase commaSep x phrase
What are some other ways we could join together a list of strings into one? Maybe we want to display them vertically as a bulleted list.
bulletList :: [String] -> String
foldMap does two things: first applies the
bulletItem function to each list item, then concatenates all the results together.
We could have used
foldr for this as well, but it’s slightly easier to use
foldMap for tasks that have this particular map-then-concatenate pattern.
Notice that although this fold also starts from the empty string and proceeds by concatenating to it, this time we have not explicitly written either the starting value or the combining function. Instead the foldMap function relies on the monoid which gives a default starting value and combining function for the
= foldMap bulletItem xs bulletList xs where = " - " ++ x ++ "\n" bulletItem x
For the simplest situations where we only need to concatenate all of the list elements without doing anything to them first, we have the
smashTogether :: [String] -> String = fold xssmashTogether xs
Now let’s demonstrate using the functions we wrote above.
= main do
numbers be a list of the integers from 1 to 5. We’ll print the list, and then print the sum of the list.
let numbers = enumFromTo 1 5 putStrLn (show numbers) putStrLn (show (sum numbers))
Then we define a list of strings, apply each of the
String functions to the list, and print the results.
let words = ["One", "Two", "Three", "Four", "Five"] putStrLn (commaList words) putStr (bulletList words) putStrLn (smashTogether words)
$ runhaskell folding-lists.hs[1,2,3,4,5]
1 + (2 + (3 + (4 + (5 + 0))) = 15
15 One, Two, Three, Four, Five - One - Two - Three - Four - Five
“One” ++ (“Two” ++ (“Three” ++ (“Four” ++ (“Five” ++ “”)))) = “OneTwoThreeFourFive”