Le lambda‑calcul, purement et en général

Source SML : 

structure Fold = struct

  (*
    u is the starting value.

    f is passed from fold through steps to finish, where it is used.

    h is the first curried argument to step (see note [1]), returning
    a function to be used in chain. The evaluation of the latter returns a
    function whose argument will be the next step function (the one appearing
    on its right side).

    finish is a function whose argument structure is the same as that of the
    step function returned by step (see [2]), except it returns a non‑function
    value.

    There may be two arguments to step: if it is, the first is passed directly,
    the second is passed by the previous step. Ex. given “val step = fn u =>
    Fold.step (fn v => u + v)”, and “(step 1) (step 2)”, in “(step 2)”, 2
    is passed as the first argument, u, and the second argument, v, is passed
    by “(step 1)” to “(step 2)”. There may be just a single argument, v, as in
    “val step = Fold.step (fn y => …)” and “step step step”.

    The type of a step, is not required to be the same as the next or previous
    one. It is only required that a step, has a second (or single) argument of
    a type matching the one passed to it by the previous step. A step1 may
    passes an argument of type t1, step2 will be required to have an argument
    of that t1 type, while being free to pass an argument of type t2 to its
    right sibling step. This is the reason why the structure use type variables.
    The argument to finish, needs to be of the type of the one passed to it by
    the last step.

    A steps sequence is started with fold, which is also (internally) used to
    link a step to its next step. It is finished by finish or a conveniently
    shorter alias of it.

    Example use (a practically useless one):

      val $ = Fold.finish
      val a0 = 3.14
      val f = Fold.fold (a0, fn a => ())
      val s = fn a => Fold.step (fn b => b)
      val () = f (s 1) (s "abc") (s #"x") $

    [1]: “f = E” may be rewritten as “f = fn x => E x”, if ever E needs to
    see x. For the same purpose, “f = E; g = fn x => f x” may be rewritten as
    “g = fn x => E x”.

    [2]: “('v * ('y -> 'z))” and “('y * ('y -> 'z))”.
  *)

  val fold: ('u * ('y -> 'z)) -> (('u * ('y -> 'z)) -> 'v) -> 'v =
    fn (u, f) =>
    fn g =>
      g (u, f)

  val step: ('v -> 'w) -> ('v * ('y -> 'z)) -> (('w * ('y -> 'z)) -> 'x) -> 'x =
    fn h =>
    fn (v, f) =>
      fold (h v, f)

  val finish: ('y * ('y -> 'z)) -> 'z =
    fn (y, f) =>
      f y

end (* structure Fold *)