wiki:ListComprehensions2

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!

Last modified 5 years ago Last modified on Nov 21, 2014, 10:00:08 PM
Note: See TracWiki for help on using the wiki.