# Difference between revisions of "Function"

BrettGiles (talk | contribs) (HaWiki conversion) |
BrettGiles (talk | contribs) m (Fix link) |
||

Line 1: | Line 1: | ||

[[Category:Glossary]] [[Category:Language]] |
[[Category:Glossary]] [[Category:Language]] |
||

− | Mathematically speaking, a [http://mathworld.wolfram.com/Function.html function] relates all values in a set <math>A</math> to values in a set <math>B</math>. The function <math>square\ x = x^2</math>, given that <math>x</math> 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 [[ |
+ | Mathematically speaking, a [http://mathworld.wolfram.com/Function.html function] relates all values in a set <math>A</math> to values in a set <math>B</math>. The function <math>square\ x = x^2</math>, given that <math>x</math> 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== |
==Examples== |

## Revision as of 00:16, 19 October 2006

Mathematically speaking, a function relates all values in a set to values in a set . The function , given that 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 *a*s to *b*s, and a list *xs* of *a*s. It returns a list of *b*s 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 *b*s 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 *Int*s 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.