Re: Constructed types

From: Markus Mottl (
Date: Thu Jan 21 1999 - 02:22:38 MET

From: Markus Mottl <>
Message-Id: <>
Subject: Re: Constructed types
To: (Chris Keane)
Date: Thu, 21 Jan 1999 02:22:38 +0100 (MET)
In-Reply-To: <199901201042.KAA01535@msc2.comlab> from "Chris Keane" at Jan 20, 99 10:42:18 am


> then why doesn't this?
> > # let myfun2 x =
> > let m = if x = 0 then (0,0) else (1,1) in
> > Bar m;;
> > The constructor Bar expects 2 argument(s),
> > but is here applied to 1 argument(s)

I have also come across this problem when porting Okasaki's sources from
SML to OCAML - obviously, this restriction does not apply to SML.

E.g. (taken from a pattern match in function "balance" in the
      implementation of red-black trees):

  | ...
  | body = T body

body should actually be of type tree:

type tree = E | T of color * tree * elem * tree

But although the preceding patterns already indicate the only possible
type, one cannot just simply match the tuple with one identifier and
place it after the non-constant constructor. One would have to write
something like

  | ...
  | a,b,c,d -> T (a,b,c,d)

I have tried to find something about that in the reference manual, but
found only this (I hope it's relevant):

  The expression ncconstr expr evaluates to the variant value whose
  constructor is ncconstr, and whose argument is the value of expr.

If I interpret this right, a non-constant constructor should work with
any expression (that matches, of course). I don't know, why this does
not apply here. Since it is possible to do this in SML, I really wonder,
whether there is some special reason to it.

Because it somehow fits into this question, here another problem I have
come across in the same function.

The working version looks like this:

  let balance = function
      B,T (R,T (R,a,x,b),y,c),z,d -> T (R,T (B,a,x,b),y,T (B,c,z,d))
    | B,T (R,a,x,T (R,b,y,c)),z,d -> T (R,T (B,a,x,b),y,T (B,c,z,d))
    | B,a,x,T (R,T (R,b,y,c),z,d) -> T (R,T (B,a,x,b),y,T (B,c,z,d))
    | B,a,x,T (R,b,y,T (R,c,z,d)) -> T (R,T (B,a,x,b),y,T (B,c,z,d))
    | a,b,c,d -> T (a,b,c,d)

Now, Okasaki claims that in Standard ML of New Jersey it is possible
to rewrite this as (I use OCAML syntax otherwise and do as if the first
problem presented here did not exist):

  let balance = function
      B,T (R,T (R,a,x,b),y,c),z,d
    | B,T (R,a,x,T (R,b,y,c)),z,d
    | B,a,x,T (R,T (R,b,y,c),z,d)
    | B,a,x,T (R,b,y,T (R,c,z,d)) -> T (R,T (B,a,x,b),y,T (B,c,z,d))
    | body -> T body

This looks really readable now. But if I do this in OCAML, the compiler
will complain that variables are bound several times in this matching -
they are obviously already bound *before* the multiple match (which is
otherwise possible) is over.

I am not sure whether this feature found in SML/New Jersey creates more
problems than it solves (e.g. what if values bound to the same identifier
have different types in the pattern?). But in this specific function
it comes really handy. At least there doesn't seem to be a good reason,
why names should be bound in other patterns before they can be used on
the right-hand side.

Best regards,

Markus Mottl,,

This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:18 MET