Function

Mathematically speaking, a function relates all values in a set $A$ to values in a set $B$. The function $square\ x=x^{2}$, given that $x$ is an integer, will map all elements of the set of integers into another set -- in this case the set of square integers. In Haskell functions can be specified as below in the examples, with an optional type specification that gives the compiler (and other programmers) a hint as to the use of the function.

Examples

square :: Int -> Int
square x = x * x

In other words, a function has input and output, and it describes how to produce the output from its input. Functions can be applied, which just means that you give an input value as argument to the function and can then expect to receive the corresponding output value.

Haskell functions are first class entities, which means that they

• can be given names
• can be the value of some expression
• can be members of a list
• can be elements of a tuple
• can be passed as parameters to a function
• can be returned from a function as a result

(quoted from Davie's Introduction to Functional Programming Systems using Haskell.)

map example

As an example of the power of first-class functions, consider the function map:

map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]

(Note this is a Higher order function.) This function takes two arguments: a function f which maps as to bs, and a list xs of as. It returns a list of bs which are the results of applying f to every member of xs. So map square [1,1,2,3,5,8] would yield the list [1,1,4,9,25,64]. When you realize that the list of bs that map returns can itself be a list of functions, things start to get interesting.

Suppose you have some data structure (e.g. Set) that has the function insert :: Int -> Set -> Set, which takes an integer and a set, and returns the set created by inserting the given integer into the given set. And suppose you have mySet and myList, a set and a list of values to be added to the set, respectively. One could write a function to recurse over the list of integers, each time inserting a single member of myList, but with first-class functions this is not necessary. Look at the expression map insert myList -- what is the type of the list which it produces? Since insert takes an Int and a Set, but only Ints were given, the resulting list will be of functions that take a set and return a set. Conceptually, the code map insert [1,2,3] will return the list [(insert 1) (insert 2) (insert 3)].

Composition / folding example

Haskell supports a Function composition operator:

(.) :: (b -> c) -> (a ->b) -> (a->c)
(f . g) x = f (g x)

So, for example, ((insert 1) . (insert 2) . (insert 3)) mySet is the same as insert 1 (insert 2 (insert 3 mySet)). We're almost there -- what we need now is a function that can automatically put the composition operator between every element of map insert myList. Such code is included in Haskell, and it's known as folding.

Several variants of the fold function are defined, but the basic concept is the same: given a function and a list, "collapse" the list by applying the function "between" its elements. This is easiest to see with simple binary operators, but it is not limited to them. For example, foldr1 (+) [1,1,2,3,5] eventually creates the expression 1+1+2+3+5, and thus returns 12. In the set example, foldr1 (.) (map insert myList) gives us what we want, the successive insertion of every element of myList. What is the type of this expression? It is Set -> Set, meaning it will take a set and return a set -- in this case, the set it returns will have every element of myList inserted. To complete the example,

newSet = (foldr1 (.) (map insert myList)) mySet

will define newSet as mySet with the elements of myList inserted.

See also

• The Functions section in the Gentle Introduction.

Languages: ja