[MLton] Fold: stepN == step T ... T $

[Vesa Karvonen]

The original Fold formulation contains functions of types of the form

  val step0 : ... ('a -> 'b) ...
  val step1 : ... ('a * 'b -> 'c) ...
  val step2 : ... ('a * 'b * 'c -> 'd) ...
  ...

Although you'll probably never need a huge number of such functions, it
would nevertheless be nice to avoid such indexed functions. As usual, we
can get a fairly convenient alternative with a constant number of
functions (two in this case) using infix products and CPS:

  datatype ('a, 'b) product = & of 'a * 'b
  infix &
  fun id x = x
  fun pass x f = f x
  fun $ (x, f) = f x

  structure FoldC =
     struct
        val fold = pass
        fun step h (s, f) = fold (h s, f)
        fun take k (s, f) x = fold (s & x, f) k
     end

Now, instead of writing

  Fold.stepN
    (fn (s, p1, ..., pN) => ...)

you would write

   _________ n times _________
  /                           \
 (FoldC.take o ... o FoldC.take o FoldC.step)
    (fn s & p1 & ... & pN => ...)

We can also apply the technique to itself to reduce the syntactic
overhead:

  structure FoldV =
     struct
        val fold = FoldC.fold
        fun step $ = FoldC.fold (FoldC.step, id) $
        fun T $ = FoldC.step (fn step => FoldC.take o step) $
     end

Now you would write

              ____ n times ____
             /                 \
  FoldV.step FoldV.T ... FoldV.T $
    (fn s & p1 & ... & pN => ...)

I think that the optional arguments formulation could also use a similar
reform. I prefer having a "closed" interface rather than an interface that
has some arbitrary limit even if it incurs some syntactic overhed. When
you have a closed interface, you can always introduce shorthand definitions
outside the implementation.

-Vesa Karvonen