value level module packing and functors in OCaml

I wonder why one example fails and not the other.

  (* this fails  *)
  (* (l fails to type check)
     This expression has type 'a but an expression was expected of type
     (module M.TFixU)
     The module type M.TFixU would escape its scope
  *)
  let foldList1 (type ar) algr l =
    let module M = FixT (ListIntF) in
    let (module LU : M.TFixU) = l in
    assert false

  (* but this works  *)
  let foldList2 (type ar) algr l =
    let (module LU : FixT(ListIntF).TFixU) = l in
    assert false

complete code

module Higher = struct
  type ('a, 't) app

  module type NewType1 = sig
    type 'a s
    type t

    val inj : 'a s -> ('a, t) app
    val prj : ('a, t) app -> 'a s
  end

  module NewType1 (X : sig
    type 'a t
  end) =
  struct
    type 'a s = 'a X.t
    type t

    external inj : 'a s -> ('a, t) app = "%identity"
    external prj : ('a, t) app -> 'a s = "%identity"
  end
end

module Fix = struct
  open Higher

  module FixT (T : NewType1) = struct
    module type T_Alg = sig
      type a

      val alg : (a, T.t) app -> a
    end

    module type TFixU = sig
      module App : functor (A : T_Alg) -> sig
        val res : A.a
      end
    end

    type tFixU = (module TFixU)
  end
end

module Pb = struct
  open Higher
  open Fix

  (* intro *)
  type 'r listIntF = Empty | Succ of (int * 'r)

  module ListIntF = NewType1 (struct
    type 'r t = 'r listIntF
  end)

  (* this fails  *)
  let foldList1 (type ar) algr l =
    let module M = FixT (ListIntF) in
    let (module LU : M.TFixU) = l in
    (* (l fails to type check)
       This expression has type 'a but an expression was expected of type
       (module M.TFixU)
       The module type M.TFixU would escape its scope
    *)
    let module T = LU.App (struct
      type a = ar

      let alg = algr
    end) in
    T.res

  (* but this doesn't  *)
  let foldList2 (type ar) algr l =
    let (module LU : FixT(ListIntF).TFixU) = l in
    let module T = LU.App (struct
      type a = ar

      let alg = algr
    end) in
    T.res
end

Solution 1:

In the first case, the type of l is unified with the type defined in the module M, which defines the module type. Since the type is introduced after the value l, which is a parameter in an eager language so it already exists, the value l receives a type that doesn't yet exist at the time of its creation. It is the soundness requirement of the OCaml type system that the value lifetime has to be enclosed with its type lifetime, or more simply each value must have a type. The simplest example is,

let x = ref None  (* here `x` doesn't have a type since it is defined later *)
type foo = Foo;;  (* the `foo` scope starts here *)
x := Some Foo (* foo escapes the scope as it is assigned to `x` via `foo option` *)

Another simplified example, that involves a function parameter is the following,

let foo x =
  let open struct
    type foo = Foo
  end in
  match x with
  | Some Foo -> true (* again, type foo escapes the scope as it binds to `x` *)
  | None -> false

A very good article that will help you understand in-depth scopes and generalization is Oleg Kiselyov's How OCaml type checker works -- or what polymorphism and garbage collection have in common.

Concerning the second case, you clearly specified the type of l using the applicative nature of OCaml functors. And since the typechecker knows that the lifetime of FixT(ListIntF).TFixU is greater than the lifetime of l it is happy.