Geek Answers Handbook

Coding versus using the existential type when coding as universal

I try to better understand the nuances of coding and use the existential type after we turn it into a universal one. In short, it seems to me that using the existential type is much simpler than coding, and I will explain what this means to me below. To better explain this, let's start with two rules from logic.

  • ∀xP (x) ⇒ ¬ (∃x.¬P (x))
  • ∃xP (x) ⇒ ¬ (∀x.¬P (x))

It follows that

  • ∀x. (P (x) ⇒ Q)
  • ∀x. (¬P (x) ⩖ Q)
  • (∀x.¬P (x)) ⩖ Q
  • (¬¬ (∀x.¬P (x))) ⩖ Q
  • (¬ (¬ (∀x.¬P (x)))) ⩖ Q
  • (¬ (∃xP (x))) ⩖ Q
  • (∃xP (x)) ⇒ Q

Hence,

(∃xP (x)) ⇒ Q = ∀x. (P (x) ⇒ Q).

, , . , . , ,

∃x.P(x) = ∀y. (∀x.P(x) ⇒ y) ⇒ y.

, . ,

  • ∀y. (∀x.P(x) ⇒ y) ⇒ y
  • ∀y. ((∃x.P(x)) ⇒ y) ⇒ y
  • ∀y.¬ ((∃x.P(x)) ⇒ y) ⩖ y
  • ∀y.¬ (¬ (∃x.P(x)) ⩖ y) ⩖ y
  • ∀y. ((∃x.P(x)) ⩕ ¬y) ⩖ y
  • ∀y. ((∃x.P(x)) ⩖ y) ⩕ (y v ¬y)
  • ∀y. (∃x.P(x)) ⩖ y
  • (∃x.P(x)) ⩖ ∀y.y
  • ∃x.P()

, , - , , P (x) y y.

, . , OCaml,

type 't mypackage = {
    add : 't * 't -> 't;
    fromInt : int -> 't;
    toString : 't -> string};;

let int_package  = {
    add  = (fun (x,y) -> x+y) ;
    fromInt = (fun x->x) ;
    toString = (fun x->string_of_int x)};;

let str_package  = {
    add  = (fun (x,y) -> x^y) ;
    fromInt = (fun x->string_of_int x) ;
    toString = (fun x-> x)};;

let simpleProg fns =
   let exp01 = fns.fromInt 1 in
   let exp02 = fns.fromInt 2 in
   let exp03 = fns.add (exp01,exp02) in
   fns.toString exp03

let _ = simpleProg int_package;;
let _ = simpleProg str_package;;

. ,

val int_package : int mypackage
val str_package : string mypackage
val simpleProg : 'a mypackage -> string = <fun>

, simpleProg: (∃x.mypackage(x)) ⇒ . ∀x.mypackage(x) ⇒ , . , int_package str_package , , ,

type 't mypackage = {
    add : 't * 't -> 't;
    fromInt : int -> 't;
    toString : 't -> string};;

let apply (arg : 't mypackage) (f : 't mypackage -> 'u) : 'u =
    f arg;;

let int_package_ = {
    add  = (fun (x,y) -> x+y) ;
    fromInt = (fun x->x) ;
    toString = (fun x->string_of_int x)};; 

let int_package = apply int_package_;;

let str_package_  = {
    add  = (fun (x,y) -> x^y) ;
    fromInt = (fun x->string_of_int x) ;
    toString = (fun x-> x)};; 

let str_package = apply str_package_;;

let simpleProg_ fns =
   let exp01 = fns.fromInt 1 in
   let exp02 = fns.fromInt 2 in
   let exp03 = fns.add (exp01,exp02) in
   fns.toString exp03

(* Notice that we have inverted how we use the existentials here.  We give the
existential the program and don't give the program the existential *)
let _ = int_package simpleProg_;;
let _ = str_package simpleProg_;;

(* This flips things *)
let simpleProg fns =
    fns simpleProg_;;

let _ = simpleProg int_package;;
let _ = simpleProg str_package;;

,

val int_package : (int mypackage -> '_a) -> '_a = <fun>
val str_package : (string mypackage -> '_a) -> '_a = <fun>

. int string . ,

val simpleProg : (('a mypackage -> string) -> 'b) -> 'b = <fun>

, . ,

val simpleProg : (('a mypackage -> 'b) -> 'b) -> string = <fun>

( . .)

, , , . , , , , , .

, :

  • , , , ? , , , , ( mypackage .)
  • , ? , , mypackage .

1

camlspotter , , .

(* Creates the type forall t.P(t) *)
type 't mypackage = {
    add : 't * 't -> 't;
    fromInt : int -> 't;
    toString : 't -> string};;

(* Creates the type forall u.(forall t.P(t) -> u) *)
type 'u program_that_takes_open_package_and_returns_u = {
    code : 't. 't mypackage -> 'u};;
(* Creates the type forall u.(forall t.P(t) -> u) -> u *)
type 'u applies_program_to_specified_packaged_and_produces_u =
    'u program_that_takes_open_package_and_returns_u -> 'u;;

(* Has type P(int) *)
let int_package = {
    add  = (fun (x,y) -> x+y) ;
    fromInt = (fun x->x) ;
    toString = (fun x->string_of_int x)};; 
(* Has type forall u.(forall.t P(t) -> u) -> u. *)
let (applies_prog_to_int_package :
        'u applies_program_to_specified_packaged_and_produces_u) =
    (* Has type forall u.(forall.t P(t) -> u) *)
    (* Even though we specify an int_package, the program must accept all
    packages *)
    fun (program:'u program_that_takes_open_package_and_returns_u) ->
        program.code int_package;;

(* Has type P(string) *)
let str_package  = {
    add  = (fun (x,y) -> x^y) ;
    fromInt = (fun x->string_of_int x) ;
    toString = (fun x-> x)};;
(* Has type forall u.(forall.t P(t) -> u) -> u. *)
let (applies_prog_to_str_package :
        'u applies_program_to_specified_packaged_and_produces_u) =
    (* Has type forall u.(forall.t P(t) -> u) *)
    (* Even though we specify an str_package, the program must accept all
    packages *)
    fun (program:'u program_that_takes_open_package_and_returns_u) ->
        program.code str_package_;;

(* The code of a program that takes a package called fns and produces a string *)
let simpleProg = { code = fun fns -> 
   let exp01 = fns.fromInt 1 in
   let exp02 = fns.fromInt 2 in
   let exp03 = fns.add (exp01,exp02) in
   fns.toString exp03}

(* Apply the program to each of the packages *)
let _ = applies_prog_to_int_package simpleProg;;
let _ = applies_prog_to_str_package simpleProg;;

(* Show that we can, in fact, keep all of the packages in a list *)
let _ = [applies_prog_to_int_package;applies_prog_to_str_package];;

, , , - , , reencoding . , , , . , . , , , , " ".

  • , . , , , . , , , , , .
  • , , - . , , . , , .

, - . int_package str_package , . , .

+4
3

, .

, ∃'t. 't mypackage,

∀'y. (∀'t. 't mypackage -> 'y) -> 'y

OCaml ('t mypackage -> 'y) -> 'y, ,

∀'y. ∀'t. ('t mypackage -> 'y) -> 'y

.

OCaml ∀'y. (∀'t. 't mypackage -> 'y) -> 'y, :

type 'y packed = { unpacked : 't. 't mypackage -> 'y }  
(* mimicing ∀'t. 't mypackage -> 'y *)

,

type 'y closed_package = 'y packed -> 'y 
(* mimicing a higher ranked type ∀'y. (∀'t. 't mypackage -> 'y) -> 'y,
   which is equivalent with ∃'t. 't mypackage *)

, 'y, :

type really_closed_package = { l : 'y. 'y closed_package }

:

let closed_int_package = { l = fun packed -> packed.unpacked int_package }
let closed_str_package = { l = fun packed -> packed.unpacked str_package }

, :

let closed_packages = [ closed_int_package; closed_str_package ]

, .

. , :

let doubled_int_string p x =
  let x = p.fromInt x in
  p.toString (p.add (x,x))

doubled_int_string , . :

let () =
  (* Using "universal" packages *)
  print_endline (double_int_string int_package 3);
  print_endline (double_int_string str_package 3);

  (* Equivalents using "existential" packages *)
  print_endline (closed_int_package.l { unpacked = doubled_int_string } 3);
  print_endline (closed_str_package.l { unpacked = doubled_int_string } 3)
+4

camlspotter, , :

type 'k mypackage_cont = { p: 't. 't mypackage -> 'k }

:

val int_package1 : 'k mypackage_cont -> 'k
val str_package1 : 'k mypackage_cont -> 'k

:

val int_package2 : int mypackage
val str_package2 : string mypackage

, , (int string) . .

, , . :

# [ int_package1; str_package1; ];;
- : ('a mypackage_cont -> 'a) list = [<fun>; <fun>]

:

# [ int_package2; str_package2 ];;
Characters 16-28:
  [ int_package2; str_package2 ];;
                  ^^^^^^^^^^^^
Error: This expression has type string mypackage
       but an expression was expected of type int mypackage
       Type string is not compatible with type int
+2

, , , . , Haskell - .

:

val int_package : (int mypackage -> '_a) -> '_a = <fun>

, _a . . , . , int, , . , .

, , .

( : -)

0

More articles:


All Articles