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.

Lecture Goals

• Introduce sequences and list comprehensions (sweet syntactic sugar)

• Explore list comprehensions as a programming technique

• Examine “solve a more general problem” solution strategy

Arithmetic Sequences (1)

• [m..n] list of elements from m up to n in steps of 1 if m <= n; nil otherwise

  Sugar for Prelude enumFromTo m n

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

Arithmetic Sequences (2)

• [m,m’..n] list of elements from m in steps of m’-m

  m’ > m increasing up to n
m’ < m decreasing

  Sugar 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$ []

Arithmetic Sequences (3)

• [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 Sequence

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]

List Comprehension

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

Qualifier: Generator

Syntax: pat <- exp

• exp is list-valued expression

• Extracts each element of exp matching pattern pat, in order

• [ n*n | n <- [1..5]] yields [1,4,9,16,25]

Qualifier: Filter

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

Qualifier: Local Definition

Syntax: let pat = expr

• Introduces variable local to comprehension

• [ n*n | let n = 2 ] yields [4]

Multiple Qualifiers (1)

• 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)]

Multiple Qualifiers (2)

• 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)]

Multiple Qualifiers (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]

Translating Comprehensions

Translated to regular functions calls — see section 18.3.2

Underlying higher-order function concatMap — which can represent both map and filter

Strings of Spaces

spaces :: Int -> String
spaces n = [ ' ' | i<-[1..n] ]

When n < 1 yields empty string

Prime Number Test

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

Squares of Primes

sqPrimes :: Int -> Int -> [Int]
sqPrimes m n = [ x*x | x<-[m..n], isPrime x ]

sqPrimes' :: Int -> Int -> [Int]
sqPrimes' m n = map (\x -> x*x) (filter isPrime [m..n])

Doubling Positive Elements

doublePos5 :: [Int] -> [Int]
doublePos5 xs = [ 2*x | x <- xs, 0 < x ]

Concatenating List of Lists of Lists

superConcat :: [[[a]]] -> [a]
superConcat xsss = [ x | xss<-xsss, xs<-xss, x<-xs ]

superConcat' :: [[[a]]] -> [a]
superConcat' = concat . map concat

First Occurrence (1)

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

First Occurrence (2)

Generalize to finding all occurrences

    positions :: Eq a => [a] -> a -> [Int]
    positions xs x = [ i | (i,y)<-zip [1..length xs] xs, x == y]

    position :: Eq a => [a] -> a -> Int 
    position xs x = head ( positions xs x ++ [0] )

Lazy evaluation only generates head element!

First Occurrence (3)

Lazy evaluation allows upper bound to be removed

    positions :: Eq a => [a] -> a -> [Int]
    positions xs x = [ i | (i,y)<-zip [1..] xs, x == y]

Key Ideas

• List comprehensions (generators, filters, local defitions)

• Translating list comprehensions to regular functions

• Solve a more general problem strategy

Source Code

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