再帰関数を暗記
暗記しておいたほうがいい再帰関数をまとめてみた。ghci に向かったら空で入力できるようになるといろいろと便利だ。何回も ghci から入力しているうちに自然とプログラムが出てくるようになる。
ここに紹介したプログラムは全て、長い１行プログラムだ。それは、デバッグが上矢印キーで簡単にできるためだ。Windows のコマンドプロンプトでは長い行を入力すると後のほうがみえなくなるが、一旦リターンキーをおしたあと、上矢印で表示させることができる。表示された複数行にわたる入力は修正も可能だ。
整数値の再帰関数
Prelude> fact 0 = 1; fact n = n * fact(n-1)
Prelude> fact 5
120
リストの再帰関数
Prelude> mysum[] = 0; mysum (x:xs) = x + mysum xs
Prelude> mysum [1..10]
55
Prelude> mymap f [] = []; mymap f (x:xs) = (f x) : mymap f
xs
Prelude> mymap (*2) [1..5]
[2,4,6,8,10]
Prelude> myfilter f [] = []; myfilter f (x:xs) = if (f x == True)
then x : myfilter f xs else myfilter f xs
Prelude> filter odd [1..10]
[1,3,5,7,9]
２分岐する再帰関数
Prelude> qsort [] = []; qsort (x:xs) = qsort (filter (<=x) xs) ++ [x]
++ qsort (filter (>x) xs)
Prelude> qsort [2,0,1,8]
[0,1,2,8]
Prelude> hanoi 1 from to work = [(from,to)]; hanoi n from to work =
hanoi (n-1) from work to ++ [(from,to)] ++ hanoi (n-1) work to from
Prelude> hanoi 3 'A' 'C' 'B'
[('A','C'),('A','B'),('C','B'),('A','C'),('B','A'),('B','C'),('A','C')]
木構造の再帰関数
Prelude> data Tree a = Leaf a | Node (Tree a) (Tree a) deriving Show;
flatten (Leaf x) = [x]; flatten (Node x y) = flatten x ++ flatten y
Prelude> flatten (Node (Leaf "foo") (Node (Leaf "bar") (Leaf "buz")))
["foo","bar","buz"]
多分岐する再帰関数
Prelude> perm [] = [[]]; perm xs = [x : ys | x <- xs, ys <- perm
(filter (/=x) xs)]
Prelude> perm [1..3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
初期条件 base case が２つある再帰関数
Prelude> comb 0 _ = [[]]; comb _ [] = []; comb n (x:xs) = map (x:)
(comb (n-1) xs) ++ comb n xs
Prelude> comb 2 [1..3]
[[1,2],[1,3],[2,3]]
IOモナドの再帰関数
Prelude> getLines = do x <- getLine; if x == "" then return [] else do
ys <- getLines; return (x:ys)
Prelude> getLines
hello
world
["hello","world"]