Description
Support syntax for list comprehensions along the lines of
[ x + 1 | x <- somelist, x < 10]
which would draw x values from list somelist, throw out those not less than 10, and then add one to the result.
The code should be generic enough to allow similar syntax (perhaps with [[ and ]]) for lazy lists.
The above would translate to
MAP (λx. x + 1) (FILTER (λx. x < 10) somelist)
and the pretty-printer would have to spot terms like the above and print the list-comprehension form. Note that even
MAP (λx. x + 1) list
is shorter (count the characters) when you write it as a list comprehension:
[ x + 1 | x <- list ]
(Note that the pretty-printer wouldn't attack something like MAP f list because there isn't an abstraction as the first argument to MAP.)
If two lists are drawn from, then you need some sort of MAP_FLAT constant, of type :(α -> β list) -> α list -> β list. This would then allow
[ x + y | x <- list1, y <- list2, x < 10, y <> x ]
to turn into
MAP_FLAT (λx. MAP (λy. x + y) (FILTER (λy. x < 10) (FILTER (λy. y <> x) list2))) list1
Note the weirdness of the FILTER (λy. x < 10); this will filter the list list2 by something that is either true or false in the context of a particular x.
If list1 = [11;2;5;6] and list2 = [2;3;4] the result of the above is [5; 6; 7; 8; 9; 8; 9; 10].
The similar comprehension
[ x + y | x <- list1, x < 10, y <- list2, y <> x ]
gives the translation
MAP_FLAT (λx. MAP (λy. x + y) (FILTER (λy. y <> x) list2)) (FILTER (λx. x < 10) list1)
which has the same semantics.
(See the Scala book (Odersky, Spoon and Venners) for discussion of this translation.)
As Scott pointed out in Nijmegen, it would be nice to be able have patterns on the lhs of the binding <-. This would allow something like
[ f x | SOME x <- list ]
so that only particular types of values need to be considered. I'm not so sure how this should be translated.
Want to back this issue? Post a bounty on it! We accept bounties via Bountysource.