Headline

A type that contains type parameters

Illustration

Let's use Language:Haskell here for illustration here. Consider this type:

(b -> c) -> (a -> b) -> a -> c

This type contains three type parameters: a, b, and c. In fact, this is the type of function composition, which indeed is a polymorphic function. We can look at the function signature of function composition like this:

> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

(For what it matters, "." is a higher-order function).

Here are further examples of polymorphic types, again in the type system of Language:Haskell:

• Maybe a: a Maybe type
• Either a b: an Either type
• f a: a higher-kinded polymorphic type, as f is a type-constructor position

Headline

A Function of a polymorphic type

Headline

A description of a set of values

Headline

A Function that takes as an argument or returns a function

Illustration

A higher-order function is a function that takes functions as arguments or returns functions as results. Consider the following Language:Haskell function which applies a given argument function twice:

twice :: (x -> x) -> x -> x
twice f = f . f

For instance:

> twice (+1) 40
42

twice is clearly a higher-order function in that its first argument is of a function type "x -> x". twice is actually also a higher-order function in that it composes a function that it returns as result, namely "f . f". The function composition operator "." is another higher-order function, which is obvious from its type, again:

> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

For what it matters, the type itself already reveals that the second function is applied before the first function because of how type "a" of the third argument equals with the argument type of the second function, etc. Now it would be straightforward to define function composition (except that we do not need to do, as it is predefined evidently):

(.) f g x = f (g x)

See list processing functions such as map, fold, and filter for more examples of higher-order functions. See the concept of currying as well.

Headline

A polymorphic type for handling optional values and errors

Illustration

In Language:Haskell, maybe types are modeled by the following type constructor:

-- The Maybe type constructor
data Maybe a = Nothing | Just a
 deriving (Read, Show, Eq)

Nothing represents the lack of a value (or an error). Just represent the presence of a value. Functionality may use arbitrary pattern matching to process values of Maybe types, but there is a fold function for maybes:

-- A fold function for maybes
maybe :: b -> (a -> b) -> Maybe a -> b
maybe b _ Nothing = b
maybe _ f (Just a) = f a

Thus, maybe inspects the maybe value passed as the third and final argument and applies the first or the second argument for the cases Nothing or Just, respectively. Let us illustrate a maybe-like fold by means of looking up entries in a map. Let's say that we maintain a map of abbreviations from which to lookup abbreviations for expansion. We would like to keep a term, as is, if it does not appear in the map. Thus:

> let abbreviations = [("FP","Functional programming"),("LP","Logic programming")]
> lookup "FP" abbreviations 
Just "Functional programming"
> lookup "OOP" abbreviations 
Nothing
> let lookup' x m = maybe x id (lookup x m)
> lookup' "FP" abbreviations 
"Functional programming"
> lookup' "OOP" abbreviations 
"OOP"

Headline

The functional programming language Haskell

Details

101wiki hosts plenty of Haskell-based contributions. This is evident from corresponding back-links. More selective sets of Haskell-based contributions are organized in themes: Theme:Haskell data, Theme:Haskell potpourri, and Theme:Haskell genericity. Haskell is also the language of choice for a course supported by 101wiki: Course:Lambdas_in_Koblenz.

Illustration

The following expression takes the first 42 elements of the infinite list of natural numbers:

> take 42 [0..]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41]

In this example, we leverage Haskell's lazy evaluation.

Headline

A type for disjoint (indexed) sums over types

Illustration

We illustrate here the Haskell approach to either types.

The corresponding polymorphic type type constructor is defined as follows:

data Either a b = Left a | Right b

Thus, a value of an either type is either of one type or another and the choice is also conveyed by the constructors Left versus Right. One typical application scenario is error handling where one argument type models error messages (e.g., String) and the other argument type models successful results. In this instance, either types generalize maybe types.

Another typical application scenario is mixed-type computations. For instance, assume that we have some mathematical operations that may return both Int and Float. Here is a corresponding either type:

type IntOrFloat = Either Int Float

As an example of a function that needs to manipulate values of the either type, consider the following function that extracts a Float by applying the conversion fromIntegral if given an Int:

asFloat :: IntOrFloat -> Float
asFloat (Left x) = fromIntegral x
asFloat (Right x) = x

For instance:

> asFloat (Left 42)
42.0
> asFloat (Right 42.0)
42.0

Because case discrimination on an either type is so common, there is even (in Haskell) a standard higher-order function by which the same conversion can be expressed more concisely:

asFloat :: IntOrFloat -> Float
asFloat = either fromIntegral id

Specific either types can also be expressed by other means than a designated type constructor for such types. For instance, in functional programming with algebraic data types, a specific type can be declared for a given sum. For instance, the sum over Int and Float could also be declared like this:

data IntOrFloat = Int Int | Float Float

(We reuse type names as constructor symbols here, which is possible in Haskell, as these are separate namespaces.) The earlier conversion function is now to be defined by ordinary case discrimination over a (non-polymorphic) algebraic data type:

asFloat :: IntOrFloat -> Float
asFloat (Int x) = fromIntegral x
asFloat (Float x) = x

The advantage of the either type constructor is that it captures universally (polymorphically) the notion of disjoint (labeled) sum. Clearly, sums with more than two cases can be expressed by nested applications of the type constructor.