Haskell には手続き型言語で慣れ親しんだfor文が存在しない

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

変な話なのですが、再帰をよく理解したら、なるべく再帰を使ってはいけません

出典: Haskellの文法(再帰編)

高階関数で実現できる再帰のパターンは再帰で書かない方が読みやすい

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

出典: http://d.hatena.ne.jp/kazu-yamamoto/20091122/1258899591

リスト

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

F始代数

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

mutu

融合変換

Other morphisms

動的計画法

応用例

その他