Penguin
Recent Changes
Blame: PolymorphicTypes
EditPageHistoryDiffInfoLikePages
Annotated edit history of PolymorphicTypes version 9, including all changes. View license author blame.
Rev Author # Line
7 AristotlePagaltzis 1 [ProgrammingLanguage]s with PolymorphicTypes allow you to write great range of generic functions, yet preserve StrongTypeChecking. With polymorphic typing you don't have to specify the exact type of everything in your program, you may use blank ''type variables''.
1 GlynWebster 2
9 TimCareySmith 3 This function type in [OCaml] is not polymorphic:
1 GlynWebster 4
5 __val__ zip_ints : int list -> int list -> (int * int) list
6
9 TimCareySmith 7 That says __zip_ints__ will take two lists of integers and return a list of pairs of integers. It's useful, but only for one thing. This function in OCaml is polymorphic:
1 GlynWebster 8
9 __val__ zip : 'a list -> 'b list -> ('a * 'b) list
10
11 This __zip__ takes two lists of items of types __'a__ and __'b__ (which may or may not be the same type) and returns a list of __'a__ and __'b__ pairs. When the compiler sees this function call:
12
13 zip [[1; 2; 3] [["orange"; "apple"; "banana"]
14
15 It will know that the result should be a list of integer/string pairs and type check the rest of the program accordingly.
16
17 [ML] and [Haskell] have polymorphic typing.
18
19 In [C] you can approximate polymophic typing with __void__ pointer arguments, which will take pointers to any type. In [Java] and [C++] approximate polymorphic typing by using Object classes, which all objects belong to. But in both cases you lose strong type checking, so the quality of your code suffers.
4 DavidHallett 20
6 AristotlePagaltzis 21 ''It should be noted here that this page is talking about what is sometimes known as __parametric polymorphism__. [C++] has templates, which satisfy the definition above, but are known to be syntactic; each instantiation creates a specialised version of the code. In a "true polymorphic system" only one version of the generated code would be used. There are other ways to have polymorphic types, they often come up in ObjectOrientation. Oh, and parametric polymorphism is also often referred to as generics. -- SamJansen''
4 DavidHallett 22
23 ''Beginning with version 1.5 of the [Java] SDK, [Java] now also supports the concept of generics. -- DavidHallett''
7 AristotlePagaltzis 24
8 DavidHallett 25 !!!Java Syntax
4 DavidHallett 26 __Paramaterized Type__
27 Vector<String> stringVector = new Vector<String>
28 List<Integer> integerList = new List<Integer>
29
30 __Interface__
31 interface List<Element> implements !MyInterface{...}
32
33 __Class__
34 class !MyList<Element> {...}
35 class !MyList<Element> implements List<Element> {...}
36
37 __Method__
38 boolean containsBoth(Element a, Element b);
39 static <Element> boolean swap(List<Element> list, int i, int j);
40
7 AristotlePagaltzis 41 [Java Generics on developer.java.sun.com | http://developer.java.sun.com/developer/technicalArticles/releases/generics/]
1 GlynWebster 42
43 !!!An Example
44
7 AristotlePagaltzis 45 This is Glyn defining a binary tree type on his [OCaml] interpreter:
1 GlynWebster 46
47 # __type__ 'a tree = Leaf __of__ 'a | Node __of__ 'a tree * 'a tree ;;
48 ''type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree''
49
7 AristotlePagaltzis 50 (That's Glyn typing at the [OCaml] interpreter prompt and [OCaml] responding.) The type __tree__ is polymorphic: __'a__ is a place holder for any type. For example you might want a __string tree__:
1 GlynWebster 51
52 # __let__ my_tree = Node (Node (Leaf "Cow", Leaf "Pig"), Leaf "Cat") ;;
53 ''val my_tree : string tree = Node (Node (Leaf "Cow", Leaf "Pig"), Leaf "Cat")''
54
7 AristotlePagaltzis 55 The [OCaml] interpreter worked that was a string tree for itself. From his tree type he can make __int trees__, __char trees__, __string tree trees__, whatever. These would all be incompatible types, because __ints__, __chars__ and __strings__ are incompatible. However, functions he writes for __'a tree__s can be used on any type of tree:
1 GlynWebster 56
57 # __let rec__ count_leaves (t : 'a tree) : int =
58 __match__ t __with__
59 | Leaf _ -> 1
60 | Node (left,right) -> count_leaves left + count_leaves right ;;
61 ''val count_leaves : 'a tree -> int = <fun>''
62
63 # count_leaves my_tree ;;
64 ''- : int = 3''
65
66 # count_leaves (Node (Leaf 1, Leaf 2)) ;;
67 ''- : int = 2''