``````int sum = 0;
for (int i = 1; i <= 10; i++) {
sum += i;
}
printf("%d\n", sum);
``````

このように1から10までを足す関数を書くときは

``````sum :: [Int] -> Int
sum []     = 0
sum (x:xs) = x + sum xs

main = print (sum [1..10])
``````

## map, filter, foldr

``````doubleList :: [Int] -> [Int]
-- doubleList []     = []
-- doubleList (x:xs) = (x * 2) : doubleList xs
doubleList xs = map (*2) xs

evenElements :: [Int] -> [Int]
-- evenElements []     = []
-- evenElements (x:xs) = if even x then (x : evenElements xs) else evenElements xs
evenElements xs = filter even xs
``````

### foldl, foldr

• 正格データ（数値）を生成するには末尾再帰
• 遅延データ（リスト）を生成するには普通の再帰

## Foldable/Traversable

### Foldable

``````class Foldable t where
foldr :: (a -> b -> b) -> b -> t a -> b
``````

### Traversable

``````class (Functor t, Foldable t) => Traversable t where
sequenceA :: Applicative f => t (f a) -> f (t a)
``````

#### Distributive

Distributive is the categorical dual of Traversable.

``````class Functor g => Distributive g where
distribute  :: Functor f => f (g a) -> g (f a)
``````

## Recursion Schemes

### cata, ana, hylo, para

``````newtype Fix f = In { out :: f (Fix f) }

type Algebra f a = f a -> a

-- Church encoding
type Fix f = forall a. Algebra f a -> a
``````