Skip to content

Latest commit

 

History

History
150 lines (107 loc) · 3.65 KB

4.md

File metadata and controls

150 lines (107 loc) · 3.65 KB
Raw

再帰ドリル(4)：再帰的な自然数

これまで自然数に対する再帰を学んできたが、Haskell が提供する基本的な関数/二項演算子を使ったために、なんだかよくわらかない部分もあったかもしれない。今回は、自然数の定義から始め、基本的な四則演算子を再実装する。

自然数を再帰関数で処理するのは、自然数が再帰的に定義されたデータだからである。このドリルがバカらしいと感じる人は、結局再帰を理解できない可能性があるので、あなどらないでいただきたい。

自然数の定義

自然数を以下のように定義する。ただし、自然数は0から始まるとする。

data Nat = Z | S Nat

数値と対応づけると以下のようになる

  • 0 は Z
  • 1 は S Z
  • 2 は S (S Z)
  • 3 は S (S (S Z))

最低限必要な定数/関数は、以下の通り。

  • 0
  • 0 か確かめる
  • 1 を足す
  • 1 を引く

これらを以下のように定義する。

my_zero_n :: Nat
my_zero_n = Z

my_isZero_n :: Nat -> Bool
my_isZero_n Z = True
my_isZero_n _ = False

my_plus1_n :: Nat -> Nat
my_plus1_n = S

my_minus1_n :: Nat -> Nat
my_minus1_n (S n) = n
my_minus1_n _     = error "my_minus1_n"

また、Integer と Nat の変換関数を以下のように定義する。

my_from_n :: Nat -> Integer
my_from_n n = iter n 0
  where
    iter m acc
      | my_isZero_n m = acc
      | otherwise     = iter (my_minus1_n m) (acc + 1)

my_to_n :: Integer -> Nat
my_to_n 0 = Z
my_to_n n = S (my_to_n (n - 1))

これ以降、Nat を抽象データ型として扱うので、直接 Z や S を用いることはできない。Nat ライブラリの全体像はここにある。

使ってみよう。

% ghci Nat.hs
> my_from_n (my_plus1_n my_zero_n)
1
> my_from_n (my_minus1_n (my_to_n 3))
2

足し算

これまでに学んだように、Integer に対する足し算を素朴な再帰で実装すると以下のようになる。

my_plus :: Integer -> Integer -> Integer
my_plus m 0 = m
my_plus m n = my_plus m (n - 1) + 1

これを参考に Nat に対する足し算を実装すると、以下のようになる。

my_plus_n :: Nat -> Nat -> Nat
my_plus_n m n
  | my_isZero_n n = m
  | otherwise     = my_plus1_n (m `my_plus_n` my_minus1_n n)

掛け算

これまでに学んだように、Integer に対する掛け算を素朴な再帰で実装すると以下のようになる。

my_mul :: Integer -> Integer -> Integer
my_mul m 1 = m
my_mul m n = my_mul m (n - 1) + m

これを参考に Nat に対する掛け算を実装すると、以下のようになる。

my_isOne_n :: Nat -> Bool
my_isOne_n n
  | my_isZero_n n               = False
  | my_isZero_n (my_minus1_n n) = True
  | otherwise                   = False

my_mul_n :: Nat -> Nat -> Nat
my_mul_n m n
  | my_isOne_n n = m
  | otherwise    = my_mul_n m (my_minus1_n n) `my_plus_n` m

演習

引き算

Nat に対して引き算の関数 my_minus_n を定義しなさい

my_minus_n :: Nat -> Nat -> Nat
my_minus_n = undefined

割り算

Nat に対して割り算の関数 my_divide_n を定義しなさい (ヒント：まず my_lt_n を実装すること)

my_lt_n :: Nat -> Nat -> Bool
my_lt_n = undefined

my_divide_n :: Nat -> Nat -> Nat
my_divide_n = undefined

余り

Nat に対して余りを計算する関数 my_remainder_n を実装しなさい

my_remainder_n :: Nat -> Nat -> Nat
my_remainder_n = undefined

[目次] [演習4]