From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by sympa.inria.fr (Postfix) with ESMTPS id 26F8B7EC41 for ; Sun, 21 Oct 2012 09:54:31 +0200 (CEST) Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.210.182; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail1-smtp-roc.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.210.182 as permitted sender) identity=mailfrom; client-ip=209.85.210.182; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ia0-f182.google.com) identity=helo; client-ip=209.85.210.182; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-ia0-f182.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AhQCAFSpg1DRVdK2m2dsb2JhbABFrw+ReAgjAQEBAQEICQsJFCeCIAEBAQQSAhMZARsSDAMMBgULDQ0hIQEBEQEFAQoSBhMSCAiHTwEDDwudCgkDjCiCdoNwChknAwpZiHUBBQyKammGbwOSP4FdgVWBF4oSgy8WKYQT X-IronPort-AV: E=Sophos;i="4.80,625,1344204000"; d="scan'208";a="178181084" Received: from mail-ia0-f182.google.com ([209.85.210.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 21 Oct 2012 09:54:30 +0200 Received: by mail-ia0-f182.google.com with SMTP id k10so2368913iag.27 for ; Sun, 21 Oct 2012 00:54:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=dYobFedlO0e0B8ngNQQGU5BE/IpKmqhnL2vUKPWn3ow=; b=GXCV30CWpASQS3g2qTsqntIpSMaFPs5jh9YHm799P4VSLwJbMj5jcP+s2xW0gLwFO8 gqxl36nuoJe+JipSgc5eWhA43On3G5wfjz0MSV1hzZ6sL9bgEskfsmD3WSAQ/x63pi4H BTUQtAr5jVn6Ld8JnVotg6IlHH6IrBEBjTrgI95cUwxxDBy6RgPKqtmlnyfFxI+Ipg+9 FEFuM7rpjPjRSr10bK0MrITKomgx8ShVomjRhNo7F43wImtWinmdvtd5YMd9vafSWjGp mpxM71RWs0JWWRK6u0J+f5Ud20LDKFH58w1FTDZXvBbj93B/oa5aYlSkvzHLgKxqhriX 3XiQ== Received: by 10.50.1.170 with SMTP id 10mr6049429ign.2.1350806068801; Sun, 21 Oct 2012 00:54:28 -0700 (PDT) MIME-Version: 1.0 Received: by 10.50.65.9 with HTTP; Sun, 21 Oct 2012 00:53:48 -0700 (PDT) In-Reply-To: <20121021043317.GA10985@romildo.no-ip.org> References: <20121021043317.GA10985@romildo.no-ip.org> From: Gabriel Scherer Date: Sun, 21 Oct 2012 09:53:48 +0200 Message-ID: To: Caml List Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Subject: Re: [Caml-list] How to write the fix data type There is a difficulty here because OCaml doesn't support higher-ranked type variables. In this declaration, f is not a "type", but a "type operator" (kind * -> *). To do the same in OCaml, you can use a functor (not a Haskell functor; in OCaml the word "functor" denotes a higher-order module that may depend on other modules/functors); functors are higher-kinded. module type ParamType =3D sig type ('a, 'b) t end module Fix (M : ParamType) =3D struct type 'b fix =3D In of ('b fix, 'b) M.t end module List =3D struct module Param =3D struct type ('a, 'b) t =3D Nil | Cons of 'b * 'a end include Fix(Param) end open List.Param open List let rec to_usual_list =3D function | In Nil -> [] | In (Cons (x, xs)) -> x :: to_usual_list xs The good news is that OCaml also supports equi-recursive rather than iso-recursive types, which allows you to remove the "In" wrapper at each recursion layer. For that you must compile the incumbing module (and all the modules that also see this equirecursion through an interface) with the "-rectypes" option. Then you can write: module type ParamType =3D sig type ('a, 'b) t end module EqFix (M : ParamType) =3D struct type 'b fix =3D ('b fix, 'b) M.t end module EqList =3D struct module Param =3D struct type ('a, 'b) t =3D Nil | Cons of 'b * 'a end include EqFix(Param) end open EqList.Param let rec to_usual_list =3D function | Nil -> [] | (Cons (x, xs)) -> x :: to_usual_list xs The syntax of modules is quite heavy and could appear frightening. If you insist you can use first-class modules to move some of these uses from functors to simple functions. I choose to begin with the "simple" way to do it first. Higher-kinded variables envy is probably the most severe illness about OCaml type worshippers (or Haskellers that for some (good!) reason come to wander in these parts of Functional County). In practice we do without it with not too much problems, but heavy use of monad transformers would be complicated indeed by this functor step, which is one of the reason it's not a very popular style around here. You may also distract yourself by thinking about the imperfections of higher-kinded variables in the languages that do support them; the limitation to constructor polymorphism rather than arbitrary type-level functions make them less expressive than you would like. The day we work out the details of the absolutely perfect higher-order type abstraction, maybe OCaml will jump to it? On Sun, Oct 21, 2012 at 6:33 AM, Jos=E9 Romildo Malaquias wrote: > Hello. > > How can I translate the following data type declaration from Haskell to > OCaml? > > newtype Fix f =3D In (f (Fix f)) > > > Romildo > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs