Computer Dictionary Online

Medical Dictionary   Law Dictionary   Legal Dictionary   Website Design

0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z 


generic type variable

<programming> (Also known as a "schematic type variable"). Different occurrences of a generic type variable in a type expression may be instantiated to different types. Thus, in the expression

		let id x = x in
		(id True, id 1)


id's type is (for all a: a -> a). The universal quantifier "for all a:" means that a is a generic type variable. For the two uses of id, a is instantiated to Bool and Int. Compare this with

		let id x = x in
		let f g = (g True, g 1) in
		f id


This looks similar but f has no legal Hindley-Milner type. If we say

		f :: (a -> b) -> (b, b)


this would permit g's type to be any instance of (a -> b) rather than requiring it to be at least as general as (a -> b). Furthermore, it constrains both instances of g to have the same result type whereas they do not. The type variables a and b in the above are implicitly quantified at the top level:

		f :: for all a: for all b: (a -> b) -> (b, b)


so instantiating them (removing the quantifiers) can only be done once, at the top level. To correctly describe the type of f requires that they be locally quantified:

		f :: ((for all a: a) -> (for all b: b)) -> (c, d)


which means that each time g is applied, a and b may be instantiated differently. f's actual argument must have a type at least as general as ((for all a: a) -> (for all b: b)), and may not be some less general instance of this type. Type variables c and d are still implicitly quantified at the top level and, now that g's result type is a generic type variable, any types chosen for c and d are guaranteed to be instances of it.

This type for f does not express the fact that b only needs to be at least as general as the types c and d. For example, if c and d were both Bool then any function of type (for all a: a -> Bool) would be a suitable argument to f but it would not match the above type for f.


Contact the Computer Dictionary Online  ::  Link to the Computer Dictionary Online  ::  Disclaimer for Computer Dictionary Online

Computer Dictionary Online
Copyright © 2017