Polymorphism in OCaml - ad hoc, parametric, inclusion / subtyping

Question

I have a problem understanding different types of polymorphism, especially regarding OCaml. I understand that polymorphism allows several types in OCaml, denoted as "a", but I do not understand what different types of polymorphism are. If someone can give me an explanation with a relatively low level of language, that would be awesome! ad hoc, parametric, inclusion / subtyping

Answer 1

Here is an approximation.

Ad-hoc polymorphism usually refers to the fact that it can declare the same name (usually a function) with different types, for example. + : int -> int -> int and + : float -> float -> float in SML. These are different functions, and they can act very differently, but the compiler or interpreter chooses the appropriate one depending on the context. I cannot think of any cases of ad-hoc polymorphism in OCaml. However, this is common in C ++ and Java.

Parametric polymorphism is when one function can work with an argument of any type due to the fact that it does not try to look into this structure of arguments. For example, cons : 'a -> 'a list -> 'a list can add a value of v any type to a list of values ​​of the same type, since for cons does not matter what structure (layout) v or what operations it supports . In terms of C cons don't need to “dereference” a pointer or perform any operation on v that is specific to the actual type of v . Note that unlike ad-hoc polymorphism, cons should act the same for all types. Thus, parametric and ad-hoc polymorphism are natural "opposites" of each other. Parametric polymorphism is responsible for the vast majority of cases of polymorphism in OCaml.

Subtype politicism is when you can use values ​​of type t where values ​​of type u are expected. This may be due to the fact that type t supports all operations of type u or because the structure t can be used where u is expected. Examples of this can be subclasses (perhaps a bus can be used wherever a Vehicle can be) or polymorphic options (you can use 'A | 'B where 'A | 'B | 'C is expected).

EDIT for comment

Note, however, that subtyping must be requested explicitly in OCaml. If you have, for example, the function f : u -> int , and you want to apply it to v : t , where t is a subtype of u , you should write f (v :> u) . Syntax (v :> u) is a type of coercion.

OCaml also supports string polymorphism, which is a form of constrained parametric polymorphism. If f instead of f : #u -> int (for object types) or f : [< u] -> int (for polymorphic options), the syntax #u / [< u] is a type variable similar to 'a , but which can only be replaced with the corresponding "subtypes" of u (in the limited sense that they can support more fields / fewer constructors, respectively). Then you can do fv without coercion. OCaml automatically introduces types that use string polymorphism for many expressions containing polymorphic variants and objects, but you must explicitly write types if you are creating a signature.

There are more customs and considerations for grouping polymorphism. I neglected the actual string variables and optional syntax and described only something that looks like limited quantification (like in Java generics). A more detailed and accurate discussion of line polymorphism, its name and / or its formalism is perhaps best preserved for individual issues.

Answer 2

In fact, I do not think this question is particularly suitable for strengths. There are whole books written about types. In fact, I would recommend Pierce to write Types and programming languages that I consider extremely enlightening and delightful.

As a quick answer (based mainly on what I remember from Pierce :-), here I take on these terms.

Parametric polymorphism refers to types with free variables in them, where variables can be replaced with any type. The List.length function is of this type because it can find the length of any list (regardless of the type of elements).

 # List.length;; - : 'a list -> int = <fun> 

One of the fantastic features of OCaml is that it not only supports types like this, it reveals them. To define a function, OCaml provides the most general parametrically polymorphic type for a function.

Subtyping is the relationship between types. A type T is a subtype of type U if all instances of T are also instances of U (but not necessarily vice versa). OCaml supports subtyping, i.e. Allows a program to process a value of type T as the value of its supertype U. However, the programmer must ask for it explicitly.

 # type ab = [ `A | `B ];; type ab = [ `A | `B ] # type abc = [`A | `B | `C ];; type abc = [ `A | `B | `C ] # let x : ab = `A;; val x : ab = `A # let y : abc = x;; Error: This expression has type ab but an expression was expected of type abc. The first variant type does not allow tag(s) `C # let y : abc = (x :> abc);; val y : abc = `A 

In this example, a type of type ab is a subtype of type abc , and x is of type ab . You can use x as a value of type abc , but you must explicitly convert using a type operator :> .

Ad-hoc polymorphism refers to polymorphism, which is determined by the programmer for specific cases, and not based on fundamental principles. (Or at least what I mean by this, maybe other people use this term differently.) A possible example of this is the OO inheritance hierarchy, where the actual state types of an object should not be related in any way while methods have the right relationship.

A key note about special polymorphism (IMHO) is that it allows the programmer to make it work. Therefore, this does not always work. Other types of polymorphism here, based on fundamental principles, actually cannot fail to work. This is a calming feeling when working with complex systems.

Answer 3

Eden is polymorphic:

 # let ident x = x;; val ident : 'a -> 'a = <fun> # ident 1;; - : int = 1 # ident "ok";; - : string = "ok" # ident [];; - : 'a list = [] # ident List.length;; - : '_a list -> int = <fun> # ident ident;; - : '_a -> '_a = <fun> 

fold also:

 # open List;; # fold_left (+) 0 [1;2;3];; - : int = 6 # fold_left (^) "" ["1";"2";"3"];; - : string = "123" # fold_left (fun a (x,y) -> a+x*y) 0 [(1,2);(3,4);(5,6)];; - : int = 44