Folding lists

For loops

Hashing

The functions foldr, foldMap, and 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.

folding-lists.hs

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.

commaList xs = foldr commaSep "" xs
  where
    commaSep x "" = x
    commaSep x phrase = 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

Here 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 String type.

bulletList xs = foldMap bulletItem xs
  where
    bulletItem x = "  - " ++ x ++ "\n"

For the simplest situations where we only need to concatenate all of the list elements without doing anything to them first, we have the fold function.

smashTogether :: [String] -> String
smashTogether xs = fold xs

Now let’s demonstrate using the functions we wrote above.

main =
  do

Let 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]-to-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”

OneTwoThreeFourFive

Next: Hashing