As we mentioned before, NML picked up a lot of neat ideas from other languages. One of the really neat ideas picked up from Haskell, and several others, is the notion of “List Comprehensions”.
A List Comprehension is a specification for the production of a list based on set-theoretic notation of elements and constraints.
A classic example is the generation of Pythagorean triples -- collections of 3 integers, (a, b, c), that satisfy the Pythagorean identity c^2 = a^2 + b^2.
In NML the solution to this, for integers from 1 to 100, without repetition, would be written as:
# {(a,b,c) | a <- [1 .. 100], b <- [a+1 .. 100],
c <- [b+1 .. 100], c^2 = a^2 + b^2};;
val it : list = [(3., 4., 5.), (5., 12., 13.), (6., 8., 10.), (7., 24., 25.), (8., 15., 17.), (9., 12., 15.), (9., 40., 41.), (10., 24., 26.), (11., 60., 61.), (12., 16., 20.), ...]
This specification, enclosed in curly-braces, indicates that we want to make a list of triples (tuples of 3 elements), where (or-bar), a comes from the list of integers from 1 to 100, b comes from the list of integers beginning above a and extending to 100, and c comes from the list of integers starting above b and extending to 100, and where the constraint is the Pythagorean identity between these three integers.
The output, as you can see is an ordered list of Pythagorean triples.
That’s real cute... but List Comprehensions find many uses of practical concern. We might wish to collect a subset of files that satisfy some constraint regarding size or last modification time, or any number of other possibilities.
One of my biggest frustrations in the past with RSI/IDL and PVWave was their total ignorance of the concept of lists of items and indefinite iteration -- not to mention the total lack of the concept of recursion. Programs in IDL and PVWave are peppered with FOR-LOOPS in which one is iterating over some collection of items (not array arithmetic).
But to do so, you always have to know the size of the collection -- both for the limit of iteration, and worse, for the construction of the collection. We don’t always know in advance how big the collection will be.
I got very tired of this situation, overcommitting memory for the possibility that the collection may become very large -- and still not being sure that we committed enough memory. This situation is a disaster in waiting, and I cannot understand why the producers of IDL and PVWave insist on maintaining ignorance of lists. I don’t know if MatLab suffers from the same brain-kinks....
(And yes, I did solve this problem for myself by implementing the notion of Lists via record structures and OOP in IDL. It worked. It was cumbersome, messy, and an enormous overhead in the system. Sheesh!)
NML rectified this situation for me by implementing lists with map, iter, and fold operators. Currying and partial evaluation of curried functions is another boon. I can write in one or two lines of NML code what it used to take half a page of idiotic detail to specify in IDL or PVWave.
List Comprehensions shrink that effort by even more, using a near-mathematical set-theoretic notation for what we want as a result. No iteration is explicitly needed in the coding.
-------------------
Here is another more terse description of List Comprehensions that I must have written about 7 years ago...
A list comprehension, written abstractly as,
{fn(a,b,...) | a <- <list>, b <- <list>, ...}
is formally equivalent to the following NML code:
foldr
(fun a rslt ->
foldr
(fun b rslt ->
...
)
<list> rslt
)
<list> []
where the innermost function conses values onto the rslt list
to accumulate the values of the comprehension. A list compre-
hension with more than one source list computes the cartesian
product of those lists.
The forms "a <- <list>" and so forth are known as "generators"
and the left of the assignment can be any pattern. Only the
list elements matching the pattern are taken (refutable
patterns).
Example:
{ a | (_,(a,_)) <- [(1,(2,3)),(4,5)] } -> [2]
--------------------
It should be pointed out that any number of generators and constraints can be specified, and in any order, even intermixed. The only requirement, as in all of NML and OCaml, is that any expressions referred to in a constraint must be defined by a generator to the left of the constraint. That is, the expression named must be previously defined before it can be used.
Sunday, February 4, 2007
