# 関数

## Examples

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

• 名前が与えられる
• ある式の値である
• リストのメンバになれる
• タプルの要素になれる
• 関数の引数として与えられる
• 関数の結果として返される

（Davieの "Introduction to Functional Programming Systems using Haskell."より引用）

### `map` の例

ファーストクラス関数の威力を見られる例として、"map"関数を考えてみましょう。 map:

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

（これは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.