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
> 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" (
y) onto a list of zip of "tails" (
> zip ['a','b','c'] [1,2,3,4] [('a',1),('b',2),('c',3)]
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
> sorted [1,2,3,4,5,6] True > sorted [1,2,4,3,5,6] False
Note: we could change
<= 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
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)))
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
> (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]
filter with uses given predicate procedure as a guard expression
filter p xs = [x | x <- xs, p x]
so elegant and concise.
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]).