caml-list - the Caml user's mailing list
 help / color / Atom feed
From: Oleg <oleg@okmij.org>
To: mmatalka@gmail.com
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] How is this type inferred (GADTs)
Date: Fri, 20 Sep 2019 23:25:25 +0900
Message-ID: <20190920142525.GA1829@Melchior.localnet> (raw)
In-Reply-To: <86o8zfpra2.fsf@gmail.com>


Gabriel has given an excellent explanation, it is hard to add
anything. Yet I will still try.

> module F : sig
>   type ('f, 'r) t
>   val z : ('r, 'r) t
>   val (//) : ('f, 'a -> 'r) t -> (unit -> 'a) -> ('f, 'r) t
> end = struct
>   type ('f, 'r) t =
>     | Z : ('r, 'r) t
>     | S : (('f, 'a -> 'r) t * (unit -> 'a)) -> ('f, 'r) t
>   let z = Z
>   let (//) t f = S (t, f)
> end

Perhaps it will be easier to work out the types if we don't use
GADTs. They are not necessary in your example (and not needed for
the typed printf either).

Here is the adjusted code

module F : sig
  type ('f, 'r) t

  val z : ('r, 'r) t
  val (//) : ('f, 'a -> 'r) t -> (unit -> 'a) -> ('f, 'r) t

  val bind : 'f -> ('f, 'r) t -> 'r
 end = struct
  type ('f, 'r) t = 'f -> 'r

  let z = fun x -> x
  (* the type annotations are all optional. They are given to show
     which subexpressions have which types, and let the compiler confirm
     that.
     Alas, attaching type annotations requires too many parentheses
  *)  
  let (//) : type a r f. (f, a -> r) t -> (unit -> a) -> (f, r) t =
    fun t th ->
      fun (f:f) -> ((((t f):(a->r)) (th () : a)) : r)

  let bind f t = t f
end


let exp1 = F.(z // (fun () -> Int32.zero) // (fun () -> ""));;
(*
  val exp1 : (int32 -> string -> '_weak1, '_weak1) F.t = <abstr>
*)

Just for reference, here is the implementation for the opposite order,
suggested by Gabriel.

module G : sig
  type ('f, 'r) t

  val z : ('r, 'r) t
  val (//) : ('f, 'r) t -> (unit -> 'a) -> ('a -> 'f, 'r) t

  val bind : 'f -> ('f, 'r) t -> 'r
 end = struct
  type ('f, 'r) t = {e: 'w. ('r -> 'w) -> ('f -> 'w)}

  let z = {e = fun x -> x}
  (* the type annotations are all optional. They are given to show
     which subexpressions have which types, and let the compiler confirm
     that
     Alas, attaching type annotations requires too many parentheses
  *)  
  let (//) : type a r f. (f, r) t -> (unit -> a) -> (a->f, r) t =
    fun t th ->
      {e = fun (type w) (k:(r->w)) -> fun (af:a->f) ->
        ((((t.e k):(f -> w)) ((af (th ())):f)):w)}

  let bind f t = t.e (fun x -> x) f
end

let test = G.(z // (fun () -> 3l) // (fun () -> "foo"));;
(* val test : (string -> int32 -> '_weak2, '_weak2) G.t = <abstr> *)

;;


      parent reply index

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-09-20  3:42 Malcolm Matalka
2019-09-20  6:35 ` Gabriel Scherer
2019-09-20  8:11   ` Malcolm Matalka
2019-09-20  8:35     ` Gabriel Scherer
2019-09-20  8:56       ` Gabriel Scherer
2019-09-20 14:25 ` Oleg [this message]

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=20190920142525.GA1829@Melchior.localnet \
    --to=oleg@okmij.org \
    --cc=caml-list@inria.fr \
    --cc=mmatalka@gmail.com \
    /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 http://inbox.vuxu.org/caml-list
	git clone --mirror https://inbox.ocaml.org/caml-list

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://inbox.vuxu.org/vuxu.archive.caml-list


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