[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))))