*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