caml-list - the Caml user's mailing list
 help / Atom feed
From: Ivan Gotovchits <ivg@ieee.org>
To: rixed@happyleptic.org
Cc: caml-list <caml-list@inria.fr>
Subject: Re: [Caml-list] Calling a single function on every member of a GADT?
Date: Tue, 7 Jan 2020 15:21:03 -0500
Message-ID: <CALdWJ+yTGigM=jjhnuk6VNOg+0Reo5UneJyVFWna5LG=3VMk2Q@mail.gmail.com> (raw)
In-Reply-To: <4d2b5367-a869-42bc-9547-b58864c10cf8@www.fastmail.com>

[-- Attachment #1: Type: text/plain, Size: 2097 bytes --]

On Tue, Jan 7, 2020 at 2:25 PM <rixed@happyleptic.org> wrote:

> ... but using a GADT:
>
> ---
> module Gadt =
> struct
>   type _ term =
>      | Int : int -> int term
>      | Add : (int -> int -> int) term
>      | App : ('b -> 'a) term * 'b term -> 'a term
>
>   let rec fold : type a. 'r -> ('r -> _ term -> 'r) -> 'r = fun i f ->
> function
>     | Int _ as t -> f i t
>     | Add -> f i Add
> (*
>      ^ Error: This pattern matches values of type (int -> int -> int) term
>         but a pattern was expected which matches values of type int term
>         Type int -> int -> int is not compatible with type int
> *)
>     | App (x, y) as t -> f (fold (fold i f x) f y) t
> end
> ---
>
> I've tried other variants of the syntax and got many encouragements but no
> green flag from the type-checker.
> Why is the compiler expecting an int term in there? I though the whole
> point of the `type a. ...` syntax was to allow the matched type to vary
> from one pattern to the next?
> Is there a way to do this?
>

It is the limitation of the let-bound polymorphism. A parameter of a
function is monomorphic in its body. The classical example doesn't even
reference any GADT,

    let example f  = f "hello", f 42

It won't compile even though we can provide a polymorphic function that can
applied both to integers and to strings, e.g., `exampe (fun x -> x)` should
be possible, but not, because of the let-bounded polymorphism. There are a
few solutions available in OCaml, the simplest is to use records, e.g.,

    type app = {apply : 'a. 'a -> 'a}

    let example {apply} = apply "hello", apply 42;;

    val example : app -> string * int = <fun>

Now we have `app` that is polymorphic.
In your case, I would define a visitor type, e.g.,

  type 'r visitor = {visit : 'a. 'a term -> 'r -> 'r}

  let rec fold : type a. 'r -> 'r visitor -> a term -> 'r =
    fun i f t -> match t with
      | Int _ as t -> f.visit i t
      | Add as t -> f.visit i t
      | App (x,y) as t ->
          let i = fold i f x in
          let i = fold i f y in
          f.visit i t


Cheers,
Ivan Gotovchits

[-- Attachment #2: Type: text/html, Size: 3077 bytes --]

  reply index

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-01-07 19:25 rixed
2020-01-07 20:20 ` Ivan Gotovchits [this message]
2020-01-08  6:55   ` rixed
2020-01-08  9:44     ` Jacques Garrigue
2020-01-08 20:32     ` Ivan Gotovchits
2020-01-10  9:50       ` Malcolm Matalka
2020-01-10 19:51         ` Ivan Gotovchits

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CALdWJ+yTGigM=jjhnuk6VNOg+0Reo5UneJyVFWna5LG=3VMk2Q@mail.gmail.com' \
    --to=ivg@ieee.org \
    --cc=caml-list@inria.fr \
    --cc=rixed@happyleptic.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

caml-list - the Caml user's mailing list

Archives are clonable: git clone --mirror https://inbox.ocaml.org/caml-list

AGPL code for this site: git clone https://public-inbox.org/ public-inbox