From HaskellWiki
Mathematically speaking, a function relates all values in a set A to values in a set B. The function 
, 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|type specification] that gives the compiler (and other programmers) a hint as to the use of the function.
1 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.)
1.1 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
would yield the list
. 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
-- 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
will return the list
[(insert 1) (insert 2) (insert 3)]
.
1.2 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
. 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,
eventually creates the expression
, 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
, 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.
2 See also
Categories: Glossary | Language
