Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.functional > #111

Re: Converting list comprehensions to Standard ML

Show all headers | View raw

Brian Adkins <lojicdotcom@gmail.com> writes:

> 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.

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

Back to comp.lang.functional | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Converting list comprehensions to Standard ML Brian Adkins <lojicdotcom@gmail.com> - 2011-05-21 18:21 -0400
  Re: Converting list comprehensions to Standard ML Brian Adkins <lojicdotcom@gmail.com> - 2011-05-22 12:56 -0400
    Re: Converting list comprehensions to Standard ML torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-05-23 10:46 +0200
    Re: Converting list comprehensions to Standard ML Thomas Thiel <thomas.thiel13@freenet.de> - 2011-05-28 23:31 +0200
      Re: Converting list comprehensions to Standard ML Brian Adkins <lojicdotcom@gmail.com> - 2011-06-04 19:54 -0400
  Re: Converting list comprehensions to Standard ML torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-05-23 14:33 +0200
    Re: Converting list comprehensions to Standard ML torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-05-23 17:48 +0200
      Re: Converting list comprehensions to Standard ML Brian Adkins <lojicdotcom@gmail.com> - 2011-05-25 17:08 -0400

csiph-web