# 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!