[clean-list] List Comprehensions...

[Fabien Todescato]

Dear Cleaners,

In their famous paper "Efficient Parser Combinators", Pieter Koopmann and
Rinus Plasmeijer demonstrate the use of continuations instead of lists of
successes to implement backtracking in their parser combinators.

As a matter of fact, it is possible to extract from their parser combinators
the logic for continuation-based backtracking and implement a
continuation-based backtracking monad, instead of the standard list monad.

It turns out that using such backtracking combinators provide in some cases
an elegant alternative when writing list functions. Consider the following
examples.

The selections function below computes for a given list all the possible
pairs of one element selected from the list, with the list of remaining
elements in the same order as they were in the original list.

	selections   :: [ x ] -> [ ( x , [ x ] )  ]
	selections [x:xs] = [(x,xs):(map (\(x1,xs1)->(x1,[x:xs1]))
(selections xs))]
	selections []     = []

Based on that selections function we can write the permutations function
below that computes the permutations of a list :

	permutations :: [ x ] -> [ [ x ] ]
	permutations [] = [[]]
	permutations xs = flatten
	                  ( map
	                    ( \ ( x , xs ) -> map
	                                      ( \ xs -> [ x : xs ] )
	                                      ( permutations xs )
	                    )
	                    ( selections xs )
	                  )
That code is probably not optimal as combinations of flatten and map can be
rewritten using foldr.

Now, using continuation-based monadic backtracking combinators we can write
Prolog-like code as follows :

	member [        ] = null
	member [ x : xl ] = unit x plus member xl

	selection [        ] = null
	selection [ x : xl ] = unit ( x , xl ) plus ( selection xl bind \ (
x_ , xl ) -> unit ( x_ , [ x : xl ] ) )

	permutation [ ] = [ ]
	permutation xl  = selection xl bind \ ( x , xl ) -> permutation xl
bind \ xl -> unit [ x : xl ]

And we get :

	selections :: [ x ] -> [ ( x , [ x ] ) ]
	selections xl = findAll ( selection xl )

	permutations :: [ x ] -> [ [ x ] ]
	permutations xl = findAll ( permutation xl )

Not only is the code better looking, is is probably - I didn't check that -
more efficient as, as Koopmann and Plasmeijer explain, it avoids creating
intermediate data structures by using continuations instead.

Now, my question is about the compilation of list comprehension notation.
Are list comprehensions compiled using flatten, map, filter, ... functions,
or are they compiled using a continuation-based logic ?

Thanks a lot for your answers, and forgive my ingenuousness...

Fabien TODESCATO