**Introduction**

Couple of weeks ago, I read a well known paper on expressiveness of fold (Hutton, 1999). The paper is a very interesting paper that explains how fold is a very powerful construct.

The codes in the paper are written in Haskell and therefore assumes laziness. This means that the execution of function in Haskell is delayed until it is really needed. This is not the case for Scala, where the operation is executed eagerly, or in other word, it's strict instead of lazy.

Stream is the implementation of lazy list in Scala. Using Stream, the elements are only evaluated when they are needed. So, we may expect that Stream is close to Haskell's list.

The use of scala Stream and fold right are the topic of this post.

**Fold Right**

Let's back to fold. The paper I mentioned above (Hutton, 1999) showed how expressive fold construct, especially foldRight. The objective of this post is to show the same things as the paper, but in Scala.

Let's see the problem we may encounter. The following Haskell code works:

` 1 Prelude`**>** foldr **(****|****|****)** **False ****(**repeat True**)**
2 True

But not the following Scala code:

` 1 `**Stream**.continually**(**true**)**.foldRight**(**false**)****(**_ **|****|** _**)**

because the code above throws StackOverflowError.

The reason of the error is because Stream.foldRight is not actually lazy. When I read the article and wondered how the non-laziness of Stream.foldRight could be solved, I received Tony Morris' tweet telling that scalaz fixes the non-laziness. The following is the reimplementation of lazy foldRight for Stream inspired by Foldr scalaz implementation:

```
1
2
```**def** foldr[A, B]**(** combine: **(**A, **=****>**B**)** **=****>** B, base: B **)****(**xs: **Stream**[A]**)**: B **=** **{**
3 **if** **(**xs.isEmpty**)**
4 base
5 **else**
6 combine**(**xs.head, foldr**(**combine, base**)****(**xs.tail**)****)**
7 **}**

The following code works without StackOverflowError:

` 1 `**def** combine**(**x: **Boolean**, y: **=****>****Boolean****)** **=** x **|****|** y
2 foldr**(**combine, false**)****(****Stream**.continually**(**true**)****)**

The key of the foldr implementation above is in thetype definition of combine parameter: (A, =>B) instead of (A,B). This makes the second parameter evaluated lazily.

**Some Fold Right Uses**

The following shows some familiar functions implemented using foldr.

` 1 `**def** sum**(**xs: **Stream**[Int]**)** **=** **{**
2 **def** combine**(**x: **Int**, y: **=****>****Int****)** **=** x **+** y
3 foldr**(**combine, 0**)****(**xs**)**
4 **}**
5 **def** product**(**xs: **Stream**[Int]**)** **=** **{**
6 **def** combine**(**x: **Int**, y: **=****>****Int****)** **=** x ***** y
7 foldr**(**combine, 1**)****(**xs**)**
8 **}**
9 **def** and**(**xs: **Stream**[Boolean]**)** **=** **{**
10 **def** combine**(**x: **Boolean**, y: **=****>****Boolean****)** **=** x **&****&** y
11 foldr**(**combine, true**)****(**xs**)**
12 **}**
13 **def** or**(**xs: **Stream**[Boolean]**)** **=** **{**
14 **def** combine**(**x: **Boolean**, y: **=****>****Boolean****)** **=** x **|****|** y
15 foldr**(**combine, false**)****(**xs**)**
16 **}**

**Using Fold Right to Implement Scala Collection Functions**

As in (Hutton, 1999), the following section shows how Fold Right can be used to implement some functions. At the first time, let's see length, filter, reverse, flatten, and map implementations.

` 1 `**def** map[A,B]**(**f:A**=****>**B, xs:**Stream**[A]**)** **=** **{**
2 **def** combine**(**x:A, xs: **=****>****Stream**[B]**)** **=** f**(**x**)** #:: xs
3 **val** base:**Stream**[B] **=** **Stream**.empty
4 foldr**(**combine, base**)****(**xs**)**
5 **}**
6 **def** length[A]**(**xs: **Stream**[A]**)** **=** **{**
7 **def** combine**(**x: A, len: **=****>****Int****)** **=** len **+** 1
8 foldr**(**combine, 0**)****(**xs**)**
9 **}**
10 **def** reverse[A]**(**xs: **Stream**[A]**)** **=** **{**
11 **def** combine**(**x: A, xs: **=****>****Stream**[A]**)** **=** **Stream**.concat**(**xs, **Stream****(**x**)****)**
12 **val** base:**Stream**[A] **=** **Stream**.empty
13 foldr**(**combine, base**)****(**xs**)**
14 **}**
15 **def** filter[A]**(**p:A**=****>****Boolean**, xs: **Stream**[A]**)** **=** **{**
16 **def** combine**(**x: A, xs: **=****>****Stream**[A]**)** **=** **if** **(**p**(**x**)****)** x #:: xs **else** xs
17 foldr**(**combine , **Stream**.empty**)****(**xs**)**
18 **}**
19 **def** filterNot[A]**(**p:A**=****>****Boolean**, xs: **Stream**[A]**)** **=** **{**
20 **def** combine**(**x: A, xs: **=****>****Stream**[A]**)** **=** **if** **(**p**(**x**)****)** xs **else** x #:: xs
21 **val** base:**Stream**[A] **=** **Stream**.empty
22 foldr**(**combine, base**)****(**xs**)**
23 **}**
24 **def** flatten[A]**(**xss: **Stream**[Stream[A]]**)** **=** **{**
25 **def** combine**(**xs: **Stream**[A], ys: **=****>****Stream**[A]**)** **=** xs #::: ys
26 **val** base: **Stream**[A] **=** **Stream**.empty
27 foldr**(**combine, base**)****(**xss**)**
28 **}**
29 **def** partition[A]**(**p:A**=****>****Boolean**, xs:**Stream**[A]**)** **=** **{**
30 **(**filter**(**p, xs**)**, filterNot**(**p, xs**)****)**
31 **}**
32

Note that, the functions like flatten, filter, and map, work with infinite Streams. See the following examples:

` 1 scala`**>** map**(** **(**_:**Int****)****+**1, **Stream**.from**(**1**)****)**
2 res2: **Stream**[Int] **=** **Stream****(**2, ?**)**
3
4 scala**>** res2.take**(**4**)**.toList
5 res3: **List**[Int] **=** **List****(**2, 3, 4, 5**)**
6
7 scala**>** filter**(** **(**_:**Int****)** **%** 2 **=****=**0, **Stream**.from**(**10**)****)**.take**(**5**)**.toList
8 res5: **List**[Int] **=** **List****(**10, 12, 14, 16, 18**)**
9
10 scala**>** partition**(** **(**_:**Int****)** **%** 2 **=****=** 0, **Stream**.from**(**20**)****)**
11 res6: **(**scala.collection.immutable.**Stream**[Int], **Stream**[Int]**)** **=** **(****Stream****(**20, ?**)**,**Stream****(**21, ?**)****)**
12
13 scala**>** flatten**(****Stream**.continually**(****Stream****(**1, 3, 4**)****)****)**.take**(**10**)**.toList
14 res13: **List**[Int] **=** **List****(**1, 3, 4, 1, 3, 4, 1, 3, 4, 1**)**

**Implementing dropWhile and break**

One of the most interesting part of (Hutton, 1999) is the dropWhile implementation using foldr. The implementation is shown in the following code:

` 1 `**def** dropWhile[A]**(**pred: A **=****>** **Boolean**, xs: **Stream**[A]**)****=** **{**
2 **def** combine**(**x: A, xs: **=****>****(****Stream**[A], **Stream**[A]**)****)** **=**
3 **if** **(**pred**(**x**)****)**
4 **(**xs._1, x #:: xs._2**)**
5 **else**
6 **(**x #:: xs._2, x #:: xs._2**)**
7 **val** base:**(****Stream**[A], **Stream**[A]**)** **=** **(****Stream**.empty, **Stream**.empty**)**
8 foldr**(**combine, base**)****(**xs**)** _1
9 **}**

Instead of directly producing the result, a tuple of Streams is returned. The first Stream is the result and the second one is used for bookkeeping purpose.

The following illustrates an execution of dropWhile:

` 1 dropWhile`**(** **(**_:**Int****)****<**5, **Stream****(**1,2,7,3,4,5,6,7,8,9,10**)****)**
2 10 **=****>** **(** **(**10**)**, **(**10**)****)**
3 9 **=****>** **(** **(**9,10**)**, **(**9,10**)****)**
4 8 **=****>** **(** **(**8,9,10**)**, **(**8,9,10**)****)**
5 7 **=****>** **(** **(**7,8,9,10**)**, **(**7,8,9,10**)****)**
6 6 **=****>** **(** **(**6,7,8,9,10**)**, **(**6,7,8,9,10**)****)**
7 5 **=****>** **(** **(**5,6,7,8,9,10**)**, **(**5,6,7,8,9,10**)****)**
8 4 **=****>** **(** **(**5,6,7,8,9,10**)**, **(**4,5,6,7,8,9,10**)****)**
9 3 **=****>** **(** **(**5,6,7,8,9,10**)**, **(**3,4,5,6,7,8,9,10**)****)**
10 7 **=****>** **(** **(**7, 3,4,5,6,7,8,9,10**)**, **(**7,3,4,5,6,7,8,9,10**)****)**
11 2 **=****>** **(** **(**7, 3,4,5,6,7,8,9,10**)**, **(**2, 7,3,4,5,6,7,8,9,10**)****)**
12 1 **=****>** **(** **(**7, 3,4,5,6,7,8,9,10**)**, **(**1, 2, 7,3,4,5,6,7,8,9,10**)****)**

What surprising is that the solution actually works for infinite Stream too as illustrated in the following code:

` 1 scala`**>** dropWhile**(** **(**_:**Int****)****<**5, **Stream**.from**(**1**)****)**.take**(**10**)**.toList
2 res17: **List**[Int] **=** **List****(**5, 6, 7, 8, 9, 10, 11, 12, 13, 14**)**

The last interesting function implemented here is break. The equivalent of Haskell's break in Scala collection is called span (Update, Oct 24 thanks to oxbow). The break function creates a tuple of two lists separated at condition boundary. Example:

` 1 scala`**>** **val** **(**a,b**)** **=** break**(** **(**_:**Int****)****<**5, **Stream**.from**(**1**)****)**
2 a: **Stream**[Int] **=** **Stream****(**1, ?**)**
3 b: **Stream**[Int] **=** **Stream****(**5, ?**)**
4
5 scala**>** a.toList
6 res22: **List**[Int] **=** **List****(**1, 2, 3, 4**)**
7
8 scala**>** b.take**(**5**)**.toList
9 res23: **List**[Int] **=** **List****(**5, 6, 7, 8, 9**)**
10

The implementation of break here, of course, highly inspired from dropWhile one:

` 1 `**def** break[A]**(**pred: A**=****>****Boolean**, xs: **Stream**[A]**)** **=** **{**
2 **def** combine**(**x: A, xs: **=****>****(****Stream**[A], **Stream**[A], **Stream**[A]**)****)** **=**
3 **if** **(**pred**(**x**)****)**
4 **(**xs._1, x #:: xs._2, x #:: xs._3**)**
5 **else**
6 **(**x #:: xs._3, **Stream**.empty, x #:: xs._3**)**
7
8 **val** base:**(****Stream**[A], **Stream**[A], **Stream**[A]**)** **=** **(****Stream**.empty, **Stream**.empty, **Stream**.empty**)**
9
10 **val** result **=** foldr**(**combine, base**)****(**xs**)**
11 **(**result._2, result._1**)**
12 **}**

**Summary**

In this blog post, I showed the result of playing around with Stream and fold right. First, I rewrote the implementation of foldRight, showed the use of foldRight, expressed some collection functions using foldRight, and finally provided dropWhile and break.

The blog post does not have intention to overcome the non-laziness of Scala language. Scala is not a lazy language, and I think it's not appropriate to use lazy evaluation as the main stream of the codes.

Pope (Pope, 2010 ?) in Monad Reader 6 discussed further the implementation of dropWhile. He presented two further solutions based on higher order function composition. He also presented the fold implementation using what is so called fix function. See http://en.wikibooks.org/wiki/Haskell/Fix_and_recursion to have an idea of what Fix function is.

**References**

- Hutton G (1999) A tutorial on the universality and expressiveness of fold. Available from http://www.cs.nott.ac.uk/~gmh/fold.pdf

- Pope B (2010 ?) Getting a Fix from the Right Fold. Available from: http://www.haskell.org/wikiupload/1/14/TMR-Issue6.pdf

## 4 comments:

scala does have Haskell's "break" - it is called "span"

@oxbow thanks for the information. The blog is updated accordingly.

what is the reason of currying stream here:

def foldr[A, B]( combine: (A, =>B) => B, base: B )(xs: Stream[A]): B ...

vs.

def foldr[A, B]( combine: (A, =>B) => B, base: B, xs: Stream[A]): B

Thank you,

walter

walter: I don't think there's any good reason for that. What would be better would be:

def foldr[A, B](xs: Stream[A], base: B)( combine: (A, =>B) => B): B

This allows Scala type inference to figure out what A is from the value of xs, and what B is from the value of base, so that you don't need to specify those types when writing combine. But that requires currying: to infer type parameters, Scala takes the types of all arguments in a parameter list; the results of type inference can be used then only in *next* parameter list.

This way, you could just write all the function arguments of foldr as anonymous functions, without any type declaration for them.

Post a Comment