# List Comprehensions

Let's take a look at some beautiful procedures

First, we define "a-la cross-product for lists" in a *declarative way* - by describing a transformation.

f xs ys = [(x,y) |x <- xs, y <- ys]

Now we must realize how it works. The syntactic construct `x <- xs`

is called "generator". When we write one we could assume that the expression is *wrapped in an implicit lambda*. The second "generator" `y <- ys`

is *nested* or "inner", which means it "runs in the body" of the first one. Think of two nested `for-each`

loops or two nested `lambda`

procedures.

> f ['a','b','c'] [1,2,3,4] [('a',1),('a',2),('a',3),('a',4),('b',1),('b',2),('b',3),('b',4),('c',1),('c',2),('c',3),('c',4)]

Like in the case of nested loops, the second "generator" runs faster,

There is another, more "imperative" definition, we describe *how to compute*.

zip :: [a] -> [b] -> [(a,b)] zip _ [] = [] zip [] _ = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys

This is absolutely beautiful procedure. In last line it literally says "cons a *touple* of "heads" (`x`

and `y`

) onto a list of zip of "tails" (`xs`

and `ys`

).

> zip ['a','b','c'] [1,2,3,4] [('a',1),('b',2),('c',3)]

Having `zip`

we could define `pairs`

which "transforms" a "flat" list into a list of adjacent "pairs" (touples).

pairs :: [a] -> [(a,a)] pairs xs = zip xs (tail xs)

this is an example of a declarative, functional definition.

> pairs [1,2,3,4,5,6] [(1,2),(2,3),(3,4),(4,5),(5,6)]

Beautiful, but here comes a real gem.

sorted :: Ord a => [a] -> Bool sorted xs = and [x < y | (x, y) <- pairs xs]

Let's see how it works. First, transform it into list of "adjacent pairs" and compare the elements of each "pair". If in each pair its left side is less than its right side, then the pair is "sorted". If all the pairs are "in order" then the whole list is sorted (`and [True,True,True]`

yields `True`

)

> sorted [1,2,3,4,5,6] True > sorted [1,2,4,3,5,6] False

Note: we could change `<`

to `<=`

to deal with duplicates.

One more piece of beauty - a way to "index" elements of a list. It works because of *lazy* (on-demand) evaluation strategy in Haskell, so we could have "infinite lists". Think of a list being "generated on demand" element by element.

> zip "abcdef" [0..] [('a',0),('b',1),('c',2),('d',3),('e',4),('f',5)]

In Scheme we could have some simple ADT which is represented as `(cons x (delay expr))`

and then use `(force (cdr xs)`

to produce a value, instead of just `cdr`

.

Now, let's look how the same procedures would look like in Scheme.

(define (zip xs ys) (if (or (null? xs) (null? ys)) '() (cons (cons (car xs) (car ys)) (zip (cdr xs) (cdr ys)))))

Here we are using conditional and predicates instead of Haskell's pattern-marching, and same non-tail recursion.

> (zip '(a b c) '(1 2 3 4)) ((a . 1)(b . 2)(c . 3))

`pairs`

is the same *functional composition* - "what to do", instead of "how to do"

(define (pairs xs) (zip xs (cdr xs)))

and `sorted`

could be analogous...

(define (sorted xs) (and (map (lambda (p) (< (car p) (cdr p))) (pairs xs))))

but no. In Haskell `and`

is an ordinary procedure of type `and :: Foldable t => t Bool -> Bool`

while in Scheme it is a *special form* with takes variable number of arguments of type `Bool`

.

> (sorted '(1 2 3 4 5 6)) (#t #t #t #t #t)

So, we need something like this *macro* taken from Arc.

(mac and args "Stops at the first argument to fail (return nil). Returns the last argument before stopping." (if args (if (cdr args) `(if ,(car args) (and ,@(cdr args))) (car args)) t))

Finally, this beautiful, "declarative" `map`

procedure using *List Comprehensions*.

map f xs = [f x |x <- xs]

and `filter`

with uses given predicate procedure as a *guard expression*

filter p xs = [x | x <- xs, p x]

so elegant and concise.

This is `quicksort`

procedure in Haskell

qsort [] = [] qsort (x:xs) = qsort ys ++ [x] ++ qsort zs where ys = [y | y <- xs, y <= x] zs = [z | z <- xs, z > x]

and Erlang (using same kind of list comprehensions)

-module( quicksort ). -export( [qsort/1] ). qsort([]) -> []; qsort([X|Xs]) -> qsort([ Y || Y <- Xs, Y < X]) ++ [X] ++ qsort([ Y || Y <- Xs, Y >= X]).

Beautiful!

**Note:**See TracWiki for help on using the wiki.