# 関数

## 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であることを覚えていてください） この関数は２つの引数をとります："f"という"a"から"b"へ写像する関数と、"a"のリスト"xs"です。返り値は"b"のリストで、これは"xs"の中のすべての要素に"f"を適用した結果のリストになります。したがって、`map square [1,1,2,3,5,8]``[1,1,4,9,25,64]`というリストを返します。"map"が返した”ｂ”のリストが関数のリストにもなりえると気づくと、だんだん面白くなってきます。

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.