with Interpreters

and Functional Programming

Chapter 18

More List Processing

**H. Conrad Cunningham**

**19 October 2018**

Copyright (C) 2018, H. Conrad Cunningham

**Acknowledgements**: I originally created these slides in Fall 2018 to accompany what is now Chapter 18, More List Processing, in the 2018 version of the textbook *Exploring Languages with Interpreters and Functional Programming*.

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

**Source Code**: The Haskell module for this chapter is in `MoreLists.hs`

.

Introduce sequences and list comprehensions (sweet syntactic sugar)

Explore list comprehensions as a programming technique

Examine “solve a more general problem” solution strategy

`[m..n]`

list of elements from`m`

up to`n`

in steps of 1 if`m <= n`

; nil otherwiseSugar for Prelude

`enumFromTo m n`

`[1..5]`

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

`[5..1]`

$\Longrightarrow$`[]`

`[m,m’..n]`

list of elements from`m`

in steps of`m’-m`

`m’ > m`

increasing up to`n`

`m’ < m`

decreasingSugar for Prelude

`enumFromThenTo m’ m n`

`[1,3..9]`

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

`[9,8..5]`

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

`[9,8..11]`

$\Longrightarrow$`[]`

`[m..]`

and`[m,m’..]`

produce potentially infinite lists beginning with`m`

and having steps 1 and`m’-m`

Sugar for Prelude

`enumFrom m`

and`enumFromThen m m’`

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

`geometric 2 1 10`

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

Syntax: `[`

*expression* `|`

*qualifiers* `]`

*expression*any Haskell expression*expression*and*qualifiers*may contain local variables bound by*qualifiers*generates list element by substituting values for variables in

*expression*

Syntax: *pat* `<-`

*exp*

*exp*is list-valued expressionExtracts each element of

*exp*matching pattern*pat*,*in order*`[ n*n | n <- [1..5]]`

yields`[1,4,9,16,25]`

Syntax: Any Boolean expression

Only values that make expression

`True`

used to form elements`[ n*n | even n ]`

yields`(if even n then [n*n] else [])`

`n`

global to comprehension expression

Syntax: `let`

*pat* `=`

*expr*

Introduces variable local to comprehension

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

yields`[4]`

Generators to right vary more quickly (inner loop)

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

yields

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

Qualifiers to right may use values generated by qualifiers to left

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

yields

`[4,16,36,64,100]`

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

yields

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

Generated values may or may not be used

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

yields`[27,27,27]`

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

yields

`[1,1,2,2,3,3]`

Translated to regular functions calls — see section 18.3.2

Underlying higher-order function `concatMap`

— which can represent both `map`

and `filter`

When `n < 1`

yields empty string

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

`n`

prime if `n > 1`

and has no factors other than 1 and `n`

Lazy evaluation, so `factors`

never generates more than 1 element

Consider: `position`

takes list and value, returns position of first occurrence; 0 if not in list

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

Generalize to finding *all* occurrences

Generalize to finding *all* occurrences

Lazy evaluation only generates head element!

Lazy evaluation allows upper bound to be removed

List comprehensions (generators, filters, local defitions)

Translating list comprehensions to regular functions

Solve a more general problem strategy

The Haskell module for this chapter is in `MoreLists.hs`

.