[MLton] sequences of products
Stephen Weeks
MLton@mlton.org
Tue, 20 Sep 2005 15:40:23 -0700
> > This representation of products has a couple of advantages over &.
> > First, it supports products of length 1.
>
> I'm not sure what you mean here. The ListProduct module that I have in my
> utility library allows you to operate on one or more lists at a time. For
> example,
...
> The simpler version I published earlier should also allow you to operate on
> just one list at a time (unless I made a mistake).
Good point. I was referring to the fact that & (obviously) can't
express products of length one, since it takes two arguments. But I
had missed your point, which is much more important, since one can
simply encode the product of length one as itself, without using &,
and everything works out.
I had been a bit thrown off by the absence of unary products in your
examples, as well as by your Scanf code, which seemed to always have
an extra dummy argument, e.g.
let open Scanf in
scanf (fromString "An int 25 and a real 3.141\n")
`"An int "D`" and a real "G`"\n" >> end
let open Printf in
fn i & r & _ =>
printf `"Got an int "D`" and a real "G`".\n"$ i r end
I now don't understand why the "& _" is there. I suspect that the
same trick that allows one to get rid of the superfluous & in list
products could be made to work with Scanf too.
> > Second, there is a simple associative operator for appending two
> > products.
...
> I agree that these properties are not as easily available using the
> ListProduct approach,
I don't see how associativity is available at all with &, since the
type expresses how the product was built.
> but I'm not sure how useful it is to be able to pass products (of
> streams) around as first class entities. The point of the
> ListProduct module is to make it convenient to perform ad hoc
> operations on products of lists. The function that you pass to a
> ListProduct iterator usually performs some ad hoc operation that
> considers all the elements of the product.
I agree with respect to products of sequences; however, one case that
may be useful is feeding the result of a map that returns a product to
another product-taking function. Perhaps the associativity will be
useful in some other scenario, possibly with just products (not
products of sequences). In any case, I found it interesting that one
can have associativity even at the type level.
> Here is how you could translate the examples to use the ListProduct module
> from my utility library:
...
> Below is a copy-paste of just the signature and structure of the current
> ListProduct module library without other modules from my utility lib.
Makes sense. I implore you to consider using the MLton-library
argument ordering in your library. There are a number of reasons why
it is superior to the basis-library ordering
* consistency: the object(s) being operated on comes first. Types
in signatures are easier to read and understand because of this
consistency too.
* readability: values come near the variables that bind them.
Compare
app (fn x => ...) l vs foreach (l, fn x => ...)
The latter is much easier to read as "foreach x in l" because x is
close to l.
* consistency: arguments come in the same order as the variables
that bind them. Compare
foldl (fn (a, b) => ...) b l vs fold (l, b, fn (a, b) => ...)
In the latter, the "l" and "b" are in the same order as "a" and
"b", which are the corresponding elements of the folder.
* readability: anonymous functions come last. Since these often
tend to be the longest argument, this saves a lot of eyeball
scanning to find arguments. It also makes nested uses much easier
to read and to indent. Compare
foreach (fn x =>
fold (fn (a, b) => ...)
b l2)
l1
vs
foreach
(l1, fn x =>
fold (l2, fn (a, b) =>
...))
In any case, since I now understand how to use & better, I've
re-implemented my sequence-of-products module to use & for the
underlying product. I still think the use of streams of products is
conceptually much simpler than the approach you use, as it doesn't
require a huge record of functions and one can simply use standard
stream operations. I did decide to go ahead and combine the
product-fold with each of the functions (foreach/forall/map/...) as
you did, as it does make client code cleaner.
--------------------------------------------------------------------------------
datatype ('a, 'b) product = & of 'a * 'b
infix &
fun const c _ = c
fun curry f x y = f (x, y)
fun pass x f = f x
fun id x = x
fun $ (a, f) = f a
structure Fold =
struct
val fold = pass
fun step0 h (a1, f) = fold (h a1, f)
fun step1 h $ x = step0 (curry h x) $
fun step2 h $ a1 a2 = step0 (fn x => h (a1, a2, x)) $
end
structure Option =
struct
fun map (opt, f) =
case opt of
NONE => NONE
| SOME x => SOME (f x)
end
structure Stream =
struct
datatype 'a t = T of unit -> ('a * 'a t) option
val empty = T (fn () => NONE)
fun cons (x, s) = T (fn () => SOME (x, s))
fun get (T f) = f ()
fun delay f = T (get o f)
fun unfold (b, f) =
let
fun loop b = T (fn () => Option.map (f b, fn (a, b) => (a, loop b)))
in
loop b
end
fun forever x = unfold ((), fn () => SOME (x, ()))
fun fold (s, b, f) =
let
fun loop (s, b) =
case get s of
NONE => b
| SOME (a, s) => loop (s, f (a, b))
in
loop (s, b)
end
fun fromList l = unfold (l, fn [] => NONE | a :: l => SOME (a, l))
fun toList s = List.rev (fold (s, [], op ::))
local
fun make (size, sub) s =
unfold (0, fn i =>
if i = size s then NONE else SOME (sub (s, i), i + 1))
in
fun fromArray a = make (Array.length, Array.sub) a
fun fromString s = make (String.size, String.sub) s
fun fromVector v = make (Vector.length, Vector.sub) v
end
fun map (s, f) =
let
fun loop s =
T (fn () => Option.map (get s, fn (a, s) => (f a, loop s)))
in
loop s
end
end
structure Prods =
struct
fun append (s, s') =
Stream.unfold
((s, s'), fn (s, s') =>
case (Stream.get s, Stream.get s') of
(NONE, NONE) => NONE
| (SOME (p, s), SOME (p', s')) => SOME (p & p', (s, s'))
| _ => raise Fail "length mismatch")
local
fun make c =
Fold.step1 (fn (x, (_, f)) =>
(fn () => f (c x),
fn s => append (f (c x), s)))
in
val ` = fn $ => make id $
val A = fn $ => make Stream.fromArray $
val L = fn $ => make Stream.fromList $
val S = fn $ => make Stream.fromString $
val V = fn $ => make Stream.fromVector $
end
local
fun make f =
Fold.fold
((fn () => raise Fail "empty product", id),
fn (p, _) =>
f (fn (b, done, step) =>
let
fun loop (s, b) =
case Stream.get s of
NONE => done b
| SOME (p, ls) => step (p, b, fn b => loop (ls, b))
in
loop (p (), b)
end))
in
fun fold $ =
make (fn go => fn (b, f) =>
go (b, id, fn (p, b, k) => k (f (p, b)))) $
fun forall $ =
make (fn go => fn f =>
go ((), const true, fn (p, (), k) => f p andalso k ())) $
fun foreach $ =
make (fn go => fn f => go ((), id, fn (p, (), k) => (f p; k ()))) $
fun map $ =
make (fn go => fn f =>
go ((), const Stream.empty,
fn (p, (), k) =>
Stream.delay (fn () => Stream.cons (f p, k ())))) $
end
end
open Prods
val a = Array.fromList [1.0, 2.0, 3.0]
val l = [1, 2, 3]
val s = "abc"
val v = Vector.fromList ["foo", "bar", "baz"]
local
fun make ts x = (print (ts x); print "\n")
in
val pb = make Bool.toString
val pc = make Char.toString
val pi = make Int.toString
val pr = make Real.toString
end
val () = foreach L l $ pi
val () = foreach L l A a $ (fn i & r => (pi i; pr r))
val _ = map A a L l S s V v $ id
val () =
print
(concat
(rev ("\n" :: fold S s V v $ ([], fn (c & s, ac) => str c :: s :: ac))))