Yet Another Haskell 3章 (7)

3.7 Recursion
再帰に関して

C言語などでは、for文を使ったループをよく使う。
しかし、for文では破壊的変更を伴うため、Haskellでは使われない。

代わりに再帰を使う。

例えば、C言語で階乗を計算する関数は次のように書ける。

int factorial(int n) {
  int fact = 1;
  for (int i = 2; i <= n; ++i)
    fact = fact * i;
  return fact;
}

Haskellでは次のように書く。

factorial 1 = 1
factorial n = n * factorial(n - 1)

シンプルですね。

再帰をマスターするのは難しいけど、最初の場合と再帰の場合を分けて考えるのが大事。
例えば、aのb乗を計算する関数は、b=1とそれ以外で分けるといい。

exponent a 1 = a
exponent a b = a * exponent a (b-1)

リストの長さを計算する関数(lengthと同じ関数)は、リストが空の場合と、それ以外で分けるといい。

my_length [] = 0
my_length (x:xs) = 1 + my_length xs

この(x:xs)という記法は特徴的ですね。
リストが空でない場合は、最低1つの要素があるため、先頭の要素をxで操作でき、残りのリストをxsで表し、それを自分自身に渡して再帰すればいい。

filterもリストが空の場合と、それ以外で分けるといい。
リストが空の場合は、空のリストを返し、
リストが空でない場合は、先頭の要素が条件を満たすかしらべ、残りのリストを再帰で処理する。

my_filter p [] = []
my_filter p (x:xs) =
  if p x
    then x : my_filter p xs
    else my_filter p xs

このパターンは頻出しそう。

Exercise 3.7

fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

Exercise 3.8

mult a 1 = a
mult a b = a + mult a (b-1)

Exercise 3.9

my_map p [] = []
my_map p (x:xs) = p x : my_map p xs