5.3.7  List Comprehensions

You may be familiar from mathematics with notations such as { i² | 0 < i < 100, i є Primes } for the set containing the squares of all primes less than one hundred. This notation is technically termed a set comprehension.

A similar notation inspired by set comprehensions has recently become popular in programming languages ranging from Python to Ocaml. They define ordered lists rather than unordered sets, and are consequently termed list comprehensions.

Here is the Mythryl list comprehension corresponding to the above set comprehension:

    linux$ my

    eval:  [ i*i for i in (1..99) where isprime i ];

    [1, 4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 
     1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 
     6889, 7921, 9409]

List comprehensions provide a compact, convenient way of generating lists of interesting values. Without list comprehensions, we would instead have had to write something like

    loop (1..99, [])
    where
        fun loop ([], results)
                =>
                reverse results;

            loop (i ! rest, results)
                =>
                loop
                  ( rest,

                    isprime i   ??   i*i ! results
                                ::         results
                  );
        end;                
    end;                

The underlying list comprehension syntax used above is

    [ result-expression for pattern in list-expression where condition ];

where

• list-expression is any Mythryl expression yielding a list;
• pattern is any Mythryl pattern which will match the members of that list;
• condition is any Mythryl Boolean expression selecting list elements;
• result-expression is any Mythryl expression over the values in pattern.

In general there may be multiple for clauses, and the where clause is optional:

    linux$ my

    eval:  [ (i,j)  for i in (0..4)  for j in (5..9) ];

    [ (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 5), 
      (1, 6), (1, 7), (1, 8), (1, 9), (2, 5), (2, 6), 
      (2, 7), (2, 8), (2, 9), (3, 5), (3, 6), (3, 7), 
      (3, 8), (3, 9), (4, 5), (4, 6), (4, 7), (4, 8), 
      (4, 9) ]

Here is an example of finding Pythagorean triples — sets of three integers which could be the lengths of the sides of a right triangle:

    linux$ my

    eval:  [ (x,y,z) for x in 1..20 for y in x..20 for z in y..20 where x*x + y*y == z*z ];

    [ (3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]

To show that list comprehensions are useful for more than just playing with numbers, here is an example more relevant to system administration. This one creates a list of (filename, filesize) pairs for all .pkg files under the current directory:

    linux$ my

    eval:  [ (filename, (stat filename).size) for filename in dir_tree::files "." where filename =~ ./\\.pkg$/ ];

    [ ("/pub/home/cynbe/a/foo.pkg", 451), 
      ("/pub/home/cynbe/a/bar.pkg", 910) ]

(For the curious, Mythryl list comprehensions are implemented primarily by src/lib/compiler/front/parser/raw-syntax/expand-list-comprehension-syntax.pkg.)