Haskell - List comprehension

Haskell 3

Propose:

To examine lists in greater details.
Infinite Data Structures in Haskell.

Notes.lhs has codes presented in these notes as well as other examples.

List comprehension

[<expr> | <generators>, <filters>]

...> [(n,n) | n <- [2,4..10]]
[(2,2),(4,4),(6,6),(8,8),(10,10)]

The symbol "<-" reads as "belongs to" "x <- xs" is called the generator.

...> [n*n | n <- [1,4..]]
[1,16,49,100,169,256,361...
<interrupted>

Example

...>[(x,y) |x<-[1..3],y<-[3,7]]
[(1,3),(1,7),(2,3),(2,7),(3,3),(3,7)]

...>[(+) x y |x<-[1..3],y<-[3,7]]
[4,8,5,9,6,10]

The second example would be more complicated without list comprehensions

>   addLists::[Int]->[Int]->[Int]

>   addLists list1 [] = []
>   addLists list1 (a:x) = addListElem list1 a ++ addLists list1 x

>   addListElem [] a = []
>   addListElem (b:x) a = (b+a):addListElem x a

A third example illustrating two generators and a filter:

> [(x,y)| x <- [1 .. 5], y <- [1 .. x], x+y < 10]

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

Refutable patterns in generators

> [x | (x:xs)<-[[3],[1,2],[],[4,5,6],[],[10]]]
[3,1,4,10]

List Comprehension is "syntactic sugar" for a combination of applications of the functions, concat, map and filter (HOF will be covered later). The above can be expressed as:

> filter p ( concat (map (\ x -> map (\ y -> (x,y))
>                       [1..x]) [1..5]))
>            where
>            p (x,y) = x+y < 10

( Reference: Use web.archive.org to find the archived pages from FOLDOC and the Haskell Companion )

Two-line wonders

Making a list of prime numbers

>   primes :: [Int]
>   primes = sieve [2..]
>   sieve (a:x) = a:sieve[y| y<-x, y`mod`a > 0]
>   sieve [] = []

How does this work?

> sieve (a:x) = a : sieve[y | y<-x, y`mod`a > 0]

sieve [2,3,4,5,6,7,8,..]
~> 2:sieve[y| y<-[3,4,5,...], y `mod` 2 > 0] 
~> 2:sieve[3,5,7,9,11,13,15,...]
~> 2:3:sieve[y| y<-[5,7,11,13,17,19,...] y `mod` 3 > 0]
~> 2:3:sieve[5,7,11,13,17,19,...]
...
~> 2:3:5:sieve[7,11,13,17,19,...]

Values are generated only as needed.
You should execute "primes" in Haskell. Since it produces an unbounded list, you will have to STOP the execution using the "Stop" icon.
OR use "take 10 primes" which generates the first 10 primes.

Mersenne primes

To get a few primes:

...> sieve [2..200]

To find Mersenne primes (those of the form 2ⁿ - 1):

...> [p|p <- primes, powerOf2 (p+1)]

>   powerOf2 1 = False
>   powerOf2 2 = True
>   powerOf2 n = even n && powerOf2 (n `div` 2)

List examples

Note that

[6..12] is [6,7,8,9,10,11,12]

['d'..'h'] is "defgh"

[6,9..20] is [6,9,12,15,18]

['d','g'..'p'] is "dgjmp"

[2..] is [2,3,4,5,6,7,8,9,10...

['d','q'..] is "dq~\139\152\165\178\191\204\217\230\243"

Permutations

>   perms :: Eq t => [t] -> [[t]]
>   perms [] = [[]]
>   perms x = [a:p | a <- x, p <- perms(x\\[a])]

Try executing the permutation function

...> perms [1,2,3,4,5]
[[1,2,3,4,5],[1,2,3,5,4],[1,2,4,3,5],[1,2,4,5,3], ... [5,4,3,2,1]]

List module

Notice that we are importing a function from the List module
The example file ( ExampleL.lhs) can be copied
It begins

>   module ExampleL where
>   import Data.List
>   ...

Using a function in List

Please note that you cannot use \\ to remove elements from a list unless you import the module Data.List
Otherwise, define it:

>   (\\) :: Eq a => [a]->[a]->[a]
>   (\\) (a:x) [] = a:x
>   (\\) x (b:y) = (rmvAux b x)\\y
>         where  rmvAux _ [] = []
>         rmvAux b (a:x) = 
>                        if a == b then x 
>                                  else a:rmvAux b x

Member

Member:

>   member a [] = False
>   member a (b:x) = (a==b) || member a x

alternatively

>   member a [] = False
>   member a (b:x)
>      | a == b    = True
>      | otherwise = member a x

...> member 3 [1,2,3,4]
True

Fibonacci:

> fib 0 = 1
> fib 1 = 1
> fib n
> | n > 1 = fib(n-1) + fib(n-2)
> |otherwise = error "n>0 pls."

> slowFibSeq = [fib n | n <- [1..]]

Using infinite data structures to define the Fibonacci series. This is more efficient computation.

> fibSeq = 1 : 1 : [ f | f <- zipWith (+) fibSeq (tail fibSeq)]
> nFib n = fibSeq

!! n

See Gentle Tutorial for a discussion on circular list.

Use this idea to generate factorial

> factseq = 1 : 1 : [ f | f <- zipWith (*) (tail factseq) [2 ..] ]

This can be with just function application and infinite data structures

> factseq = 1 : 1 : zipWith (*) (tail factseq) [2 ..]

Alternative to above

> fibSeq2 = 1 : 1 : [ x+y | (x,y) <- zip fibSeq2 (tail fibSeq2) ]

Using the switch -98 on the hugs command runs an extended version of Haskell which allows the following:

> fibSeq3 = 1 : 1 : [ x+y | x <- fibSeq3 | y<- (tail fibSeq3)]

If the Fibonacci sequence starts with 0:1:. then the following property holds

gcd (fib !! m) (fib !! n) == fib !! (gcd m n)

One Last Neat example: Quicksort using list comprehension

> quicksort []     = []
> quicksort (x:xs) = quicksort [y | y <- xs, y<x ]
                     ++ [x]
                     ++ quicksort [y | y <- xs, y>=x]

Python

Lazy evaluation:

Using iterators

def iteratorC():
    yield 1
    yield 2
    yield 3

def fib():
     fn2 = 1
     fn1 = 1
     while True:
       (fn1,fn2,oldfn2) = (fn1+fn2,fn1,fn2)
        yield oldfn2

Using objects

class fibnum:
      def __init__(self):
         self.fn2 = 1 # "f_{n-2}"
         self.fn1 = 1 # "f_{n-1}"
      def next(self):
         (self.fn1,self.fn2,oldfn2) = (self.fn1+self.fn2,self.fn1,self.fn2)
         return oldfn2
      def __iter__(self):
         return self

List comprehension:

...> s = [x**2
      for x in range(10)]

      ...> s

      [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

      ...> [x for x in s if x % 2 == 0]

           [0, 4, 16, 36, 64]

def iteratorC():
    yield 1
    yield 2
    yield 3

...> [x for x in iteratorC()]
[1,2,3]

PythonVsHaskell
Python Cookbook -- Constructing Lists with List Comprehensions

Note: Ther term conprehension comes from the axiom of comprehension in set theory, which makes precise the idea of constructing a set by selecting all values that satisfy a particular property. (Pg 56: Programming in Haskell by Graham Hutton, 2016)