© Stefania Loredana Nita and Marius Mihailescu 2019
Stefania Loredana Nita and Marius MihailescuHaskell Quick Syntax Referencehttps://doi.org/10.1007/978-1-4842-4507-1_15

15. Folds

Stefania Loredana Nita1  and Marius Mihailescu1
(1)
Bucharest, Romania
 

An important element in functional programming is the fold (also known as reduce ). A fold represents a set of higher-order functions that operate on recursive data structures and take a combining operation as one of the parameters, recombining the results of recursive operations in order to build a return value. In this chapter, you will learn to use fold functions.

The fold family contains the following functions:

  • fold takes as one of the parameters a function and folds it onto a list.

  • foldr takes as one of the parameters a function and folds it from right to left onto a list.

  • foldl takes as one of the parameters a function and folds it from right to left onto a list.

  • foldr1 is similar to foldr.

  • foldl1 is similar to foldl.

To better understand these functions, let’s examine the following example:
Prelude> foldl (+) 5 [1..6]
26
In the first step, you have a list.
  

1

 

2

 

3

 

4

 

5

 

6

Then the function that is the first argument is folded into the elements.
 

+

1

+

2

+

3

+

4

+

5

+

6

Next, foldl needs a starting point, which is taken from the second argument (note there is nothing in the leftmost piece).

5

+

1

+

2

+

3

+

4

+

5

+

6

Indeed, 5+1+2+3+4+5+6=26; therefore, you get the result 26.

Note that you used the left fold, which is the reason why you started folding from the left. Another important note is that the fold functions are not limited to infix functions as the first argument.

Further, let’s take a look at foldr and foldr1. The definition of foldr is as follows:
foldr  :: (a -> b -> b) -> b -> [a] -> b
The definition of foldr1 is as follows:
foldr1 :: (a -> a -> a) ->      [a] -> a
From here, you can see that both of them have as the first argument a function that takes two arguments. The differences are as follows:

  • For foldr, the two arguments may have different types, resulting in output with the same type as the second argument.

  • For foldr1, the two arguments must have the same type, resulting in output of the same type as the arguments. Another aspect is that it does not need the starting point (it will choose the rightmost element to start with).

Similar to the fold functions are scan functions , which contain the following: scanl, scanr, sccanl1, and scanr1. Basically, these are analogous to foldl, foldr, foldl1, and foldl2, but they show the intermediate results. Returning to the example, if you apply scanl instead of foldl, you will get the following:
Prelude> scanl (+) 5 [1..6]
[5,6,8,11,15,20,26]
The opposite function of foldr is unfoldr. While foldr reduces a list to just one value, unfoldr builds a list based on a seed. Its definition is as follows:
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
Observe that unfoldr returns Nothing if it finished building or Just(a,b) otherwise, where a represents the list and b represents the next element. Let’s see an example1:
Prelude Data.List> unfoldr ( -> if b == 0 then Nothing else Just (b, b-1)) 10
[10,9,8,7,6,5,4,3,2,1]

Summary

In this chapter, you learned the following:

  • What fold family functions are and how to work with them

  • What the opposite of folding is

Reference

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.142.35.54