3.md

再帰ドリル(3)：いろいろな終わり方

これまで、再帰を終わらせる基底部は 1 つだけだった。しかし、複数の場合で再帰を終了させたいことがある。

偶数

偶数か確かめる関数 my_even は以下のように定義できる。

my_even :: Integer -> Bool
my_even 0 = True
my_even 1 = False
my_even n = my_even (n - 2)

より小さい、以下

たとえば、「より小さい」を確かめる関数 my_lt は、以下のように定義できる。

my_lt :: Integer -> Integer -> Bool
my_lt _ 0 = False
my_lt 0 _ = True
my_lt m n = my_lt (m - 1) (n - 1)

また、「以下」を確かめる関数 my_lteq は、以下のように定義できる。

my_lteq :: Integer -> Integer -> Bool
my_lteq 0 _ = True
my_lteq _ 0 = False
my_lteq m n = my_lteq (m - 1) (n - 1)

基底部の順番が入れ替わっていることに注意。

割り算

はっきりとは説明しなかったが、これまでの内容から、以下の基本演算があれば、足し算、引き算、掛け算、より小さい、以下が定義できるのが分かる

• 0 という値
• 0 であるか調べる
• 1 を足す
• 1 を引く

実装した関数は、my_plus、my_minus、my_mul、my_lt、my_lteq であった。以下では、Haskell の組み込み関数である +、-、*、<、<= を必要に応じて使う。

四則演算の最後の演算子、my_divide を実装しよう。基底部の判定に < が使えるようになったので、以下のように定義できる。

my_divide :: Integer -> Integer -> Integer
my_divide m n
  | m < n     = 0
  | otherwise = my_divide (m - n) n + 1

演習

奇数

奇数か確かめる関数 my_odd を実装しなさい

my_odd :: Integer -> Bool
my_odd = undefined

より大きい

「より大きい」を確かめる関数 my_gt を実装しなさい。

my_gt :: Integer -> Integer -> Bool
my_gt = undefined

以上

「以上」を確かめる関数 my_gteq を実装しなさい

my_gteq :: Integer -> Integer -> Bool
my_gteq = undefined

余り

余りを計算する my_remainder を実装しなさい

my_remainder :: Integer -> Integer -> Integer
my_remainder = undefined

割り算(2)

my_divide を末尾再帰の形に直しなさい。

my_divide_iter :: Integer -> Integer -> Integer
my_divide_iter x y = iter x y undefined
  where
    iter :: Integer -> Integer -> Integer -> Integer
    iter = undefined

[目次] [演習3]