From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <garrigue@math.nagoya-u.ac.jp>
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104])
	by yquem.inria.fr (Postfix) with ESMTP id 98250BC37
	for <caml-list@yquem.inria.fr>; Fri, 11 Dec 2009 01:18:06 +0100 (CET)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AmwBAP8eIUuFBoIFmWdsb2JhbACbOgEBAQEBCAsKBxOseo4qAQWEK4MB
X-IronPort-AV: E=Sophos;i="4.47,377,1257116400"; 
   d="scan'208";a="39671250"
Received: from rabbit.math.nagoya-u.ac.jp (HELO mailhost.math.nagoya-u.ac.jp) ([133.6.130.5])
  by mail3-smtp-sop.national.inria.fr with ESMTP; 11 Dec 2009 01:17:38 +0100
Received: from mailhost.math.nagoya-u.ac.jp (localhost [127.0.0.1])
	by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTP id 35CCFB639;
	Fri, 11 Dec 2009 09:17:34 +0900 (JST)
Received: from mailhost.math.nagoya-u.ac.jp (camel-172 [172.16.254.4])
	by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTP id E8D6C88A9;
	Fri, 11 Dec 2009 09:17:33 +0900 (JST)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=math.nagoya-u.ac.jp; h=
	date:message-id:to:cc:subject:from:in-reply-to:references
	:mime-version:content-type:content-transfer-encoding; s=alpha;
	 bh=1xa4rdVBaW4A8uU0a8XPVNx2wqI=; b=ATdbC0JzzHvHQLVNlM2e171ismph
	zAG/YVNSLBG+H8pMDc7cHsA+DDc67cCd9onx3TiliqE7o2JPrwImKXS9gxRgHH4F
	lSPbal6nc1fgauvFRTrVh9U8jv+RTqM8gw1QHKbyzXvvlzQMc5TnwVKgao9CMN+W
	iL7HHCnD8ISUqnI=
DomainKey-Signature: a=rsa-sha1; h=Received:Date:Message-Id:To:Cc:Subject:From:In-Reply-To:References:X-Mailer:Mime-Version:Content-Type:Content-Transfer-Encoding; b=C2ONwyjJsrQDfrONZ9VI2ec3ZnHJk2gAsRRD6MIQNMMf/6OR3O1FGXFL2qs367+s3fN1JlUcAUDpwoIlOaTWSYeY3QLU4AiC3aQVcE8RlUKzag++So7h56MsPmKw+vr8+TS1aYZH9S+wJO5pcM0DTMMkptp0MgzOcGzgvkGnfEI=; c=nofws; d=math.nagoya-u.ac.jp; q=dns; s=alpha
Received: from localhost (bsdserver02 [172.16.249.2])
	by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTP id BEF51889F;
	Fri, 11 Dec 2009 09:17:33 +0900 (JST)
Date: Fri, 11 Dec 2009 09:14:56 +0900 (JST)
Message-Id: <20091211.091456.04442319.garrigue@math.nagoya-u.ac.jp>
To: serge.leblanc@orange.fr
Cc: nicolas.pouillard@gmail.com, caml-list@yquem.inria.fr
Subject: Re: [Caml-list] revised syntax for abstract types ?
From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
In-Reply-To: <1260468628.22959.510.camel@serge2.localnet>
References: <1260446204.22959.298.camel@serge2.localnet>
	<1260452934-sup-6342@peray>
	<1260468628.22959.510.camel@serge2.localnet>
X-Mailer: Mew version 6.2.51 on Emacs 22.3 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Spam: no; 0.00; syntax:01 arcs:01 arcs:01 syntax:01 semantics:01 translating:01 elt:01 elt:01 polymorphism:01 checker:01 functors:01 sig:01 struct:01 struct:01 trie:98 

From: Serge Leblanc <serge.leblanc@orange.fr>
> In the following types definitions,
> 
> type trie 'a = [ Trie of arcs 'a ]
> and arcs 'a = list ('a * trie 'a);
> 
> type zipper 'a = [ Top | Zip of (arcs 'a * 'a * arcs 'a * zipper 'a) ]
> and edit_state 'a = (zipper 'a * trie 'a);
> 
> why is it not possible to describe them thus ?
> 
> type letter = 'a;
> type trie = [ Trie of arcs ]
> and arcs = list (letter * trie);
> 
> type zipper = [ Top | Zip of (arcs * letter * arcs * zipper) ]
> and edit_state = (zipper * trie);

Note first that revised syntax is just syntax, it does not change the
semantics. So, translating your question on a simpler example in
standard syntax, how does

  type 'a list = Nil | Cons of 'a * 'a list

relate to

  type elt
  type list = Nil | Cons of elt * list

The answer is that they describe the same data, but in an incompatible
way. The first approach uses ML polymorphism, so that you can build a
list of any given type, letting the type checker choose the element
type.

The second is a signature, and should be used in combination with
functors, the type being chosen explicitly. For instance, you can
write a map function in the following way:

module type List = sig
  type elt
  type list = Nil | Cons of elt * list
end
module F(T:List) = struct
  open T
  let rec map f = function
      Nil -> Nil
    | Cons (h,t) -> Cons (f h, map f t)
end

module IntList = struct
  type elt = int
  type list = Nil | Cons of elt * list
end
module IntM = F(IntList);;

IntM.map succ (IntList.Cons (1, IntList.Nil));;

Again, these two definitions of list, while representing the same data,
are incompatible.

Hope this helps.

Jacques Garrigue