Headline

A function for datatype-generic programming

Definition

Diverse and even conflicting definitions of "generic function" have been used in the past. The present ontology assumes the notion of generic function in the sense of datatype-generic programming. Thus, a generic function is a polymorphic function (because it can be applied to many types) that is also able to observe structure of (some of the) types in which it is parameterized.

Illustration

For instance, the "Scrap your boilerplate" style of generic programming supports the definition of generic functions. See corresponding illustrations.

Headline

The central abstraction in functional programming

Description

In programming, a function is an abstraction for computation. In functional programming, a function is typically close to what we call a function in mathematics. That is, a function maps values of its domain to values of its range. Outside (pure) functional programming, a function may also involve additional computational aspects or side effects. Functions are defined (or declared) in a program and then elsewhere applied.

Illustration

Consider the following function definition in Language:Haskell.

-- The increment function
inc :: Int -> Int
inc x = x + 1

The definition consists of a type signature assigning a type to the function inc and one equation providing the actual definition. The type signature declares inc as function from Int to Int. The equation binds the variable x on the left-hand side and returns the expression x+1 on the right-hand side.

Consider the following function application: inc is applied to 41; the result is 42.

> inc 41
42

Headline

A generic programming style

Illustration

"Scrap Your Boilerplate" (SYB) refers to a generic programming style where highly polymorphic function combinators are leveraged in assembling data-processing operations that recurse into compound data while being customized by type-specific cases. Consider the following implementation of Feature:Cut as part of Contribution:haskellSyb:

cut :: Company -> Company
cut = everywhere (extT id (/(2::Float)))

everywhere is a highly polymorphic function combinator which takes a polymorphic argument function to transform all immediate and non-immediate subterms of a given term of possibly any type. The actual traversal is provided by everywhere; the per-subterm functionality is to be described by the polymorphic argument of everywhere. Thus, the following type is needed:

everywhere :: forall a. Data a => (forall b. Data b => b -> b) -> a -> a

In the Haskell context, the combinators for SYB turn out to be polymorphic in an interesting manner from a typing perspective: they are rank-2 polymorphic and customization requires a form of type case. The rank-2 status can be observed in the above function signature: the inner "forall" is to the left of a function arrow. The use of type case is evident from the above application of everywhere. In particular, extT models type case such that the type-specific second argument is applied when possible and otherwise the generic first argument is applied. In general terms, extT g s x translates to s x if the argument type of s equals (or generalizes) the type of x; otherwise extT g s x translates to g x.

SYB has been conceived in a Haskell setting, but the style has been applied to other programming languages as well. SYB is particularly helpful in describing all kinds of transformations and queries for compound data in a concise manner, without involving conceptually irrelevant details of the data structures involved.

Headline

Parametrization by the shape of data structures rather than their contents