Converting list comprehensions to Standard ML

[Brian Adkins]

I've been translating a simple Haskell program I wrote to Standard ML,
and I just bumped up agains this list comprehension:

[ (r,c) | r <- [0..4], c <- [0..r], predicate (r,c) ]

I don't think I appreciated the brevity of list comprehensions that much
until I attempted to convert this :)

What would be the most idiomatic way to implement this in Standard ML?
The fact that the second generator depends on the first complicates
things somewhat.

Thanks,
Brian

[Brian Adkins]

Post by Brian Adkins
I've been translating a simple Haskell program I wrote to Standard ML,
[ (r,c) | r <- [0..4], c <- [0..r], predicate (r,c) ]
I don't think I appreciated the brevity of list comprehensions that much
until I attempted to convert this :)
What would be the most idiomatic way to implement this in Standard ML?
The fact that the second generator depends on the first complicates
things somewhat.

This is my first draft (with a little help from "ML for the Working
Programmer" by Paulsen):

(List.filter
(fn (r,c) => predicate (r,c))
(foldr (fn (r,l) => foldr (fn (c,l) => (r,c)::l) l (upto(0,r)))
[] (upto(0,4))))

I'm hoping there's a much better way though, because this seems *much*
less clear than the list comprehension.

By the way, is there a way to not have to write List.filter by using an
include or similar statement?

Thanks,
Brian

[Torben Ægidius Mogensen]

Post by Brian Adkins
By the way, is there a way to not have to write List.filter by using an
include or similar statement?

You can write "open List" to avoid prefixing filter with List.

Torben

[Thomas Thiel]

Post by Brian Adkins

Post by Brian Adkins
I've been translating a simple Haskell program I wrote to Standard ML,
[ (r,c) | r <- [0..4], c <- [0..r], predicate (r,c) ]
I don't think I appreciated the brevity of list comprehensions that much
until I attempted to convert this :)
What would be the most idiomatic way to implement this in Standard ML?
The fact that the second generator depends on the first complicates
things somewhat.

This is my first draft (with a little help from "ML for the Working
(List.filter
(fn (r,c) => predicate (r,c))
(foldr (fn (r,l) => foldr (fn (c,l) => (r,c)::l) l (upto(0,r)))
[] (upto(0,4))))
I'm hoping there's a much better way though, because this seems *much*
less clear than the list comprehension.
By the way, is there a way to not have to write List.filter by using an
include or similar statement?
Thanks,
Brian

infix 1 >>=
infix 2 when

fun upTo n = List.tabulate (n+1, fn x => x)

fun xs >>= f = List.concat (map f xs)

fun a when b = if b then [a] else []


fun lc predicate =
upTo 4 >>= (fn r =>
upTo r >>= (fn c => (r,c) when (predicate (r, c))))

[Brian Adkins]

Post by Thomas Thiel
[...]
infix 1 >>=
infix 2 when
fun upTo n = List.tabulate (n+1, fn x => x)
fun xs >>= f = List.concat (map f xs)
fun a when b = if b then [a] else []
fun lc predicate =
upTo 4 >>= (fn r =>
upTo r >>= (fn c => (r,c) when (predicate (r, c))))

Thanks - I'll experiment with that.

[Torben Ægidius Mogensen]

Post by Brian Adkins
I've been translating a simple Haskell program I wrote to Standard ML,
[ (r,c) | r <- [0..4], c <- [0..r], predicate (r,c) ]
I don't think I appreciated the brevity of list comprehensions that much
until I attempted to convert this :)
What would be the most idiomatic way to implement this in Standard ML?
The fact that the second generator depends on the first complicates
things somewhat.

I will base the translation on the following grammar for list
comprehensions:

LC -> [ Exp | Gs ]
Gs ->
Gs -> Exp Gs
Gs -> Pat<-Exp Gs

Note that I allow an empty list of generators and, for simplicity, do
not have commas between them.

I use the following (untested) translation functions:

Tlc translates an LC into SML
Tgs translates a Gs into SML

These are defined by the equations

Tlc([ e | gs ]) = "("^ (Tgs(gs) "()" e) ^") []"

Tgs() p e = "(List.map (fn "^ p ^" => "^ e ^"))"

Tgs(e' gs) p e
= (Tgs(gs) p e)
^" o (List.filter (fn "^ p ^" => "^ e' ^" | _ => false))"

Tgs(p'<-e' gs) p e
= (Tgs(gs) ("("^ p ^","^ p' ^")") e)
^" o (List.concat o List.map (fn "^ p
^" => map (fn "^ p' ^" => (" ^ p ^","^ p' "))"^ e' ^"))"

The p argument to Tgs is a pattern for the elements of the generated
list and the e argument is the final expression that maps over these
elements.

A generator that is a predicate doesn't change p but filters according
to the predicate. A generator that is a selector p'<-e' adds p' to the
pattern and constructs pairs of the form (p,p') by mapping over e'.

The above assumes that p' in p'<-e' matches all elements in the list
constructed by e'. If you want the more general form, where the pattern
works as a selector as well, you can compose with a filter.

Your example [ (r,c) | r <- [0..4], c <- [0..r], predicate (r,c) ] will
be translated into

(
(List.map (fn (((),r),c) => (r,c)))
o (List.filter (fn (((),r),c) => predicate (r,c) | _ => false))
o (List.concat o List.map (fn ((),r) => map (fn c => (((),r),c) [0..r])))
o (List.concat o List.map (fn () => map (fn r => ((),r)) [0..4]))
) []

I haven't translated list builders of the form [x..y], but these are
relatively simple.

As can be seen, the result can be simplified by not using a map over the
empty list and dropping the initial () pattern. This can be achieved by
making a special case translation for the first generator or, even
better, applying deforestation to the result.

I have used strings for building the SML code. You might want to use
abstract syntax instead, especially if you want to deforest the result.

Torben

[Torben Ægidius Mogensen]

Post by Torben Ægidius Mogensen
Tgs(e' gs) p e
= (Tgs(gs) p e)
^" o (List.filter (fn "^ p ^" => "^ e' ^" | _ => false))"

On second thought, the alternative part is not needed if we assume the
pattern p always matches, so it can be simplified to

Tgs(e' gs) p e
= (Tgs(gs) p e)
^" o (List.filter (fn "^ p ^" => "^ e' ^"))"

If, on the other hand, the pattern is not always guaranteed to match,
the right place to put the test would be where the pattern is
introduced, i.e, rewriting

Post by Torben Ægidius Mogensen
Tgs(p'<-e' gs) p e
= (Tgs(gs) ("("^ p ^","^ p' ^")") e)
^" o (List.concat o List.map (fn "^ p
^" => map (fn "^ p' ^" => (" ^ p ^","^ p' "))"^ e' ^"))"

to

Post by Torben Ægidius Mogensen
Tgs(p'<-e' gs) p e
= (Tgs(gs) ("("^ p ^","^ p' ^")") e)
^" o (List.concat o List.map (fn "^ p
^" => map (fn "^ p' ^" => (" ^ p ^","^ p' "))"^ e' ^"))"

Tgs(p'<-e' gs) p e
= (Tgs(gs) ("("^ p ^","^ p' ^")") e)
^" o let val l' = List.filter (fn "^ p' ^" => true | _ => false)" ^ e'
^"in fn l => List.concat (List.map (fn "^ p
^" => List.map (fn "^ p' ^" => (" ^ p ^","^ p' ")) l') l) end"

Note that this also prevents recomputation of e' for every element in
the input list, which the previos version did.

This talk of list comprehensions reminds me of an idea I had way back
for a similar syntactic sugar. The idea was to emulate pseudocode of
the form

f [x1,...,xn] = [e1,...,en]

where e1 would use x1 and so on.

A new form of pattern and expression is introduced:

Pat -> [ Pat ... ]

Exp -> [ Exp ... ]

Note the three dots to distinguish from [e..] expressions.

The idea is that [p...] is translated into a variable pattern x, where x
is a fresh variable and [e...] is translated into

map (\p->e) x

(using Haskell notation) where p is the pattern on the left side of the
equation. Example:

pmap f g [(x,y)...] = [(f x, g y)...]

is translated into

pmap f g xs = map (\x -> (f x, g y)) xs

As long as there is only one [p...] pattern on the left-hand side of an
equation, this is unambiguous, but what about functions of the form

map2 f [x...] [y...] = [f x y ...] ?

We could translate this in two ways:

map2 f xs ys = zipWith f xs ys

or

map2 f xs ys = [f x y | x<-xs, y<-ys]

Both of these make sense, so the choice is not obvious. It becomes even
more muddled if the right hand side uses x and y in different lists, as
in

funny [x...] [y...] = [x+x ...] ++ [y*y ...]

Here, it would seem more natural to translate this into

funny xs ys = map (\x->x+x) xs ++ map (\y->y*y) ys

There is also the matter of nested patterns to consider:

cmap f [[x...]...] = concat [[f x...]...]

It should be fairly obvious that not all cases make sense, such as

bad1 [[x...]...] = [x+1...]

bad2 [x...] [y...] = [1...]

In the first case, the nesting level on the RHS differs from the nesting
level on the LHS, and in the second case there is no way to see which of
the two LHS lists are wanted on the RHS. The latter might be solved by
using the list-comprehension interpretation:

bad2 xs ys = [1 | x<-xs, y<-ys]

as this uses both lists and, thus, avoids ambiguity. This would,
however, translate

funny [x...] [y...] = [x+x ...] ++ [y*y ...]

into

funny xs ys = [x+x | x<-xs, y<-ys] ++ [y*y | x<-xs, y<-ys]

which is not what you would expect.

I would suggest the following rule:

In an expression [e...], e can contain only variables from [p...]
patterns that are on the same nesting level on the LHS as [e...] is on
the RHS. Given that e contains variables from [p_1...] ... [p_n...],
[e...] is translated into zipWith_n (\(p_1,...,p_n)->e) x_1 ... x_n,
where x_i is the variable that replaced p_i and zipWith_n is an n-way
zipWith function.

So funny would be translated into

funny xs ys = zipWith_1 (\(x)->x+x) xs ++ zipWith_1 (\(y)->y*y)

which is the same as the first suggestion.

map2 would be translated using zipWith_2, which is the same as zipWith.

zipWith_1 is the same as map, but there is not obvious choice for
zipWith_0 (which would be used in the [1...] list in bad2). The type of
zipWith_0 would be (()->l)->[l], which can produce either the empty list
or a list of constant length with identical elements, neither of which
seem useful (both can be done more easily than with a ... expression).
So I would suggest making this an error, so the expression e in [e...]
should contain variables from at least one ... pattern.

Torben

[Brian Adkins]

Post by Torben Ægidius Mogensen
[...]
Torben

Thanks - I'll have to save your posts and revisit when my SML-fu has
increased a bit :)