Editing Function (section)

==Examples==
<haskell>
square :: Int -> Int
square x = x * x
</haskell>

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.'')
===<hask>map</hask> example===
As an example of the power of first-class functions, consider the function ''map'': 
<haskell>
map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]
</haskell>

(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 <hask>map square [1,1,2,3,5,8]</hask> would yield the list <hask>[1,1,4,9,25,64]</hask>. 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 <hask>insert :: Int -> Set -> Set</hask>, 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 <hask>map insert myList</hask> -- 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 <hask>map insert [1,2,3]</hask> will return the list <hask>[(insert 1) (insert 2) (insert 3)]</hask>. 

===Composition / folding example===
Haskell supports a [[Function composition]] operator: 
<haskell>
(.) :: (b -> c) -> (a ->b) -> (a->c)
(f . g) x = f (g x) 
</haskell>
So, for example, <hask>((insert 1) . (insert 2) . (insert 3)) mySet</hask> is the same as <hask>insert 1 (insert 2 (insert 3 mySet))</hask>. We're almost there -- what we need now is a function that can automatically put the composition operator between every element of <hask>map insert myList</hask>. 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, <hask>foldr1 (+) [1,1,2,3,5]</hask> eventually creates the expression <hask>1+1+2+3+5</hask>, and thus returns 12. In the set example, <hask>foldr1 (.) (map insert myList)</hask> gives us what we want, the successive insertion of every element of ''myList.'' What is the type of this expression? It is <hask>Set -> Set</hask>, 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, 
<haskell>
newSet = (foldr1 (.) (map insert myList)) mySet 
</haskell>
will define ''newSet'' as ''mySet'' with the elements of ''myList'' inserted.