and Functional Programming

Chapter 18

**16 October 2018**

Copyright (C) 2016, 2017, 2018, H. Conrad Cunningham

Professor of Computer and Information Science

University of Mississippi

211 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-5358

Professor of Computer and Information Science

University of Mississippi

211 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-5358

**Browser Advisory:** The HTML version of this textbook requires a browser that supports the display of MathML. A good choice as of October 2018 is a recent version of Firefox from Mozilla.

Previous chapters examined first-order and higher-order list programming. In particular, Chapter 15 explored the standard higher order functions such as `map`

, `filter`

, and `concatMap`

and Chapter 16 explored function concepts such as function composition.

This chapter examines list comprehensions. This feature does not add new power to the language; the computations can be expressed with combinations of features from the previous chapters. But list comprehensions are often easier to write and to understand than equivalent compositions of `map`

, `filter`

, `concatMap`

, etc.

The source file for the code in this chapter is in `MoreLists.hs`

.

Haskell provides a compact notation for expressing arithmetic sequences.

An arithmetic sequence (or progression) is a sequence of elements from an enumerated type (i.e. a member of class `Enum`

) such that consecutive elements have a fixed difference. `Int`

, `Integer`

, `Float`

, `Double`

, and `Char`

are all predefined members of this class.

`[m..n]`

produces the list of elements from`m`

up to`n`

in steps of one if`m <= n`

. It produces the nil list otherwise.Examples:

`[1..5]`

$\Longrightarrow$`[1,2,3,4,5]`

`[5..1]`

$\Longrightarrow$`[]`

This feature is implemented with Prelude function

`enumFromTo`

applied as`enumFromTo m n`

.`[m,m’..n]`

produces the list of elements from`m`

in steps of`m’-m`

. If`m’ > m`

then the list is increasing up to`n`

. If`m’ < m`

, then it is decreasing.Examples:

`[1,3..9]`

$\Longrightarrow$`[1,3,5,7,9]`

`[9,8..5]`

$\Longrightarrow$`[9,8,7,6,5]`

`[9,8..11]`

$\Longrightarrow$`[]`

This feature is implemented with Prelude function

`enumFromThenTo`

applied as`enumFromThenTo m’ m n`

.`[m..]`

and`[m,m’..]`

produce potentially infinite lists beginning with`m`

and having steps 1 and`m’-m`

respectively.These features are implemented with Prelude functions

`enumFrom`

applied as`enumFrom m`

and`enumFromThen`

applied as`enumFromThen m m’`

.

Of course, we can provide our own functions for sequences. Consider the following function to generate a geometric sequence.

A geometric sequence (or progression) is a sequence of elements from an ordered, numeric type (i.e. a member of both classes `Ord`

and `Num`

) such that consecutive elements have a fixed ratio.

```
geometric :: (Ord a, Num a) => a -> a -> a -> [a]
geometric r m n | m > n = []
| otherwise = m : geometric r (m*r) n
```

Example: `geometric 2 1 10`

$\Longrightarrow$ `[1,2,4,8]`

The *list comprehension* is another powerful and compact notation for describing lists. A list comprehension has the form

`[`

expression`|`

qualifiers`]`

where *expression* is any Haskell expression.

The *expression* and the *qualifiers* in a comprehension may contain variables that are local to the comprehension. The values of these variables are bound by the *qualifiers*.

For each group of values bound by the qualifiers, the comprehension generates an element of the list whose value is the *expression* with the values substituted for the local variables.

There are three kinds of *qualifiers* that can be used in Haskell: generators, filters, and local definitions.

A

*generator*is a qualifier of the form*pat*`<-`

*exp*where

Example:*exp*is a list-valued expression. The generator extracts each element of*exp*that matches the pattern*pat*in the order that the elements appear in the list; elements that do not match the pattern are skipped.`[ n*n | n <- [1..5]]`

$\Longrightarrow$`[1,4,9,16,25]`

A

Example:*filter*is a Boolean-valued expression used as a*qualifier*in a list comprehension. These expressions work like the`filter`

function; only values that make the expression`True`

are used to form elements of the list comprehension.`[ n*n | even n ]`

$\Longrightarrow$`(if even n then [n*n] else [])`

Above variable

`n`

is global to this expression, not local to the comprehension.A

*local definition*is a qualifier of the form`let`

*pat*`=`

*expr*introduces a local definition into the list comprehension.

Example:`[ n*n | let n = 2 ]`

$\Longrightarrow$`[4]`

The real power of list comprehensions come from using several qualifiers separated by commas on the right side of the vertical bar `|`

.

Generators appearing later in the list of qualifiers vary more quickly than those that appear earlier. Speaking operationally, the generation “loop” for the later generator is nested within the “loop” for the earlier.

Example:

`[ (m,n) | m<-[1..3], n<-[4,5] ]`

$\Longrightarrow$

`[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]`

Qualifiers appearing later in the list of qualifiers may use values generated by qualifiers appearing earlier, but not vice versa.

Examples:

`[ n*n | n<-[1..10], even n ]`

$\Longrightarrow$`[4,16,36,64,100]`

`[ (m,n) | m<-[1..3], n<-[1..m] ]`

$\Longrightarrow$

`[ (1,1), (2,1), (2,2), (3,1), (3,2), (3,3)]`

The generated values may or may not be used in the

*expression*.Examples:

`[ 27 | n<-[1..3]]`

$\Longrightarrow$`[27,27,27]`

`[ x | x<-[1..3], y<-[1..2]]`

$\Longrightarrow$`[1,1,2,2,3,3]`

List comprehensions are syntactic sugar. We can translate them into core Haskell features by applying the following identities.

For any expression

`e`

,is equivalent to:

For any expression

`e`

and qualifier`q`

,is equivalent to:

For any expression

`e`

, boolean`b`

, and sequence of qualifiers`Q`

,is equivalent to:

For any expression

`e`

, pattern`p`

, list-valued expression`l`

, sequence of qualifiers`Q`

, and fresh variable`ok`

,is equivalent to:

For any expression

`e`

, declaration list`D`

, and sequence of qualifiers`Q`

,is equivalent to:

Function `concatMap`

and boolean value `True`

are as defined in the Prelude.

As we saw in a previous chapter, `concatMap`

applies a list-returning function to each element of an input list and then concatenates the resulting list of lists into a single list. Both `map`

and `filter`

can be defined in terms of `concatMap`

.

Consider the list comprehension:

Apply identity 4:

Apply identity 2:

Apply identity 3:

Apply identity 1:

This section gives several examples where list comprehensions can be used to solve problems and express the solutions conveniently.

Consider a function `spaces`

that takes a number and generates a string with that many spaces.

Note that when `n < 1`

the result is the empty string.

Consider a Boolean function `isPrime`

that takes a nonzero natural number and determines whether the number is *prime*. (Remember that a prime number is a natural number whose only natural number factors are 1 and itself.)

```
isPrime :: Int -> Bool
isPrime n | n > 1 = (factors n == [])
where factors m = [ x | x<-[2..(m-1)], m `mod` x == 0 ]
isPrime _ = False
```

Consider a function `sqPrimes`

that takes two natural numbers and returns the list of squares of the prime numbers in the inclusive range from the first up to the second.

Alternatively, this function could be defined using `map`

and `filter`

as follows:

We can use a list comprehension to define (our, by now, old and dear friend) the function `doublePos`

, which doubles the positive integers in a list.

Consider a program `superConcat`

that takes a list of lists of lists and concatenates the elements into a single list.

Alternatively, this function could be defined using Prelude functions `concat`

and `map`

and functional composition as follows:

Consider a function `position`

that takes a list and a value of the same type. If the value occurs in the list, `position`

returns the position of the value’s first occurrence; if the value does not occur in the list, `position`

returns 0.

**Strategy**:*Solve a more general problem first, then use it to get the specific solution desired.*

In this problem, we generalize the problem to finding *all* occurrences of a value in a list. This more general problem is actually easier to solve.

Function `zip`

is useful in pairing an element of the list with its position within the list. The subsequent filter removes those pairs not involving the value `x`

. The “zipper” functions can be very useful within list comprehensions.

Now that we have the positions of all the occurrences, we can use `head`

to get the first occurrence. Of course, we need to be careful that we return 0 when there are no occurrences of `x`

in `xs`

.

Because of lazy evaluation, this implementation of `position`

is not as inefficient as it first appears. The function `positions`

will, in actuality, only generate the head element of its output list.

Also because of lazy evaluation, the upper bound `length xs`

can be left off the generator in `positions`

. In fact, the function is more efficient to do so.

This chapter examined list comprehensions. Although they do not add new power to the language, programs involving comprehensions are often easier to write and to understand than equivalent compositions of other functions.

The next two chapters discuss problem solving techniques. Chapter 19 discusses systematic generalization of functions. Chapter 20 surveys various problem-solving techniques uses in this textbook and other sources.

Show the list (or string) yielded by each of the following Haskell list expressions. Display it using fully specified list bracket notation, e.g. expression

`[1..5]`

yields`[1,2,3,4,5]`

.`[7..11]`

`[11..7]`

`[3,6..12]`

`[12,9..2]`

`[ n*n | n <- [1..10], even n ]`

`[ 7 | n <- [1..4] ]`

`[ x | (x:xs) <- [Did, you, study?] ]`

`[ (x,y) | x <- [1..3], y <- [4,7] ]`

`[ (m,n) | m <- [1..3], n <- [1..m] ]`

`take 3 [ [1..n] | n <- [1..] ]`

Translate the following expressions into expressions that use list comprehensions. For example,

`map (*2) xs`

could be translated to`[ x*2 | x <- xs ]`

.`map (\x -> 2*x-1) xs`

`filter p xs`

`map (^2) (filter even [1..5])`

`foldr (++) [] xss`

`map snd (filter (p . fst) (zip xs [1..]))`

In 2016 and 2017, I adapted and revised my previous notes to form Chapter 7, More List Processing and Problem Solving, in the 2017 version of this textbook. In particular, I drew the information on More List Processing from:

- chapter 7 of my
*Notes on Functional Programming with Haskell*[Cunningham 2014]

In Summer 2018, I divided the 2017 More List Processing and Problem Solving chapter back into two chapters in the 2018 version of the textbook, now titled *Exploring Languages with Interpreters and Functional Programming*. Previous sections 7.2-7.3 (essentially chapter 7 of [Cunningham 2014]) became the basis for new Chapter 18, More List Processing (this chapter), and the Problem Solving discussion became the basis for new Chapter 20, Problem Solving.

I maintain this chapter as text in Pandoc’s dialect of Markdown using embedded LaTeX markup for the mathematical formulas and then translate the document to HTML, PDF, and other forms as needed.

- [Bird 1988]:
- Richard Bird and Philip Wadler.
*Introduction to Functional Programming*, First Edition, Prentice Hall, 1988. - [Bird 1998]:
- Richard Bird.
*Introduction to Functional Programming using Haskell*, Second Edition, Prentice Hall, 1998. - [Bird 2015]:
- Richard Bird.
*Thinking Functionally with Haskell*, Second Edition, Cambridge University Press, 2015. - [Cunningham 2014]:
- H. Conrad Cunningham.
*Notes on Functional Programming with Haskell*, 1993-2014. - [Thompson 2011]:
- Simon Thompson.
*Haskell: The Craft of Programming*, First Edition, Addison Wesley, 1996; Second Edition, 1999; Third Edition, Pearson, 2011.

Sequence (arithmetic, geometric), list comprehension (generator, filter, local definition, multiple generators and filters), syntactic sugar, translating list comprehensions to function calls, prime numbers, solve a harder problem first.