お気楽 Haskell プログラミング入門

はじめに

関数を定義するとき、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。

特に関数型言語の場合、再帰定義を積極的に活用してプログラミングを行うので、初心者の方が覚えるべき基礎テクニックのひとつにすぎません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。

●再帰定義の基本

まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を図に示します。

$\begin{array}{l} 0! = 1 \\ n! = n \times (n - 1)! \end{array}$

図 : 階乗の定義

階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。次のリストを見てください。

リスト : 階乗

fact :: Integer -> Integer
fact n = if n == 0 then 1 else n * fact (n - 1)

-- 記号 = の後ろで改行する場合
{-
fact n =
  if n == 0 then 1
  else n * fact (n - 1)
-}

関数 fact は引数 n が 0 であれば 1 を返し、そうでなければ n * fact (n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。なお、記号 = の後ろで改行する場合はインデントをつけてください。Haskell では、-- から改行までがコメントになります。コメントはもう一種類あって、{- と -} で囲まれた範囲がコメントになります。

それでは、本当にこれで階乗を計算できるのか、実際に試してみましょう。ファイル fact.hs にプログラムが書かれているとしましょう。対話モードで :load fact (または :l fact) と入力すると、ファイルがロードされて関数 fact を呼び出すことができるようになります。ghci を実行するときに、"$ ghci fact.hs" (または "$ stack exec ghci fact.hs") のようにコマンドラインからファイル名を指定してもかまいません。

ghci> :l fact
[1 of 2] Compiling Main             ( fact.hs, interpreted )
Ok, one module loaded.
ghci> fact 4
24
ghci> fact 10
3628800
ghci> fact 20
2432902008176640000

ファイルをロードすると、プロンプトは *"ファイルに定義されているモジュール名" にかわります。モジュール名が省略されている場合は *Main になります。モジュールについては後の回で説明します。関数 fact を実行すると、確かに階乗の答えを求めることができました。

●再帰定義のポイント

それでは、再帰定義のポイントを説明しましょう。次の図を見てください。

Call:1    -->  Call:2    -->  Call:3    --> Call:4    --> Call:5
n:4            n:3            n:2           n:1           n:0
value 24  <--  value : 6 <--  value : 2 <-- value : 1 <-- value : 1 

        図 : fact の再帰呼び出し（n:引数の値, value:返り値

上図は関数 fact 4 の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact を再帰呼び出しします。2 回目の呼び出し (Call:2) では、引数 n は 3 に束縛されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。

関数の引数は局所変数として扱われます。前回説明したように、局所変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。関数呼び出しが行われるたびに新しい局所変数を生成して、そこに値を束縛します。そして、関数の実行が終了すると、生成された局所変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。

プログラムを見ると変数 n は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact 4 を実行しているときの n は 4 であり、fact 3 を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を束縛するのです。

同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの停止条件といいます。ここが第 2 のポイントです。

停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Haskell であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。

fact 0 は 1 を返して fact 1 に戻ります。fact 1 を実行しているあいだ、引数 n の値は 1 です。したがって、fact 1 の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact 4 の値 24 を求めることができます。

●フィボナッチ関数

もうひとつ簡単な例を示しましょう。フィボナッチ関数も再帰的に定義される関数です。

$ fibo(n) = \begin{cases} 0, & \mathrm{if} \ n = 0 \\ 1, & \mathrm{if} \ n = 1 \\ fibo(n - 1) + fibo(n - 2), & \mathrm{if} \ n \gt 1 \end{cases} $

0, 1, 1, 2, 3, 5, 8, 13 ... という直前の 2 項を足していく数列

図 : フィボナッチ関数の定義

フィボナッチ関数も再帰定義を使えば簡単にプログラムできます。

リスト : フィボナッチ関数

fibo :: Integer -> Integer
fibo n =
  if n == 0 || n == 1 then n
  else fibo (n - 1) + fibo (n - 2)

定義をそのままプログラムしただけです。それでは実行してみましょう。

ghci> fibo 0
0
ghci> fibo 1
1
ghci> fibo 2
1
ghci> fibo 3
2
ghci> fibo 4
3
ghci> fibo 5
5
ghci> fibo 6
8
ghci> fibo 10
55
ghci> fibo 20
6765

関数 fibo は fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo の呼び出しをトレースすると下図のようになります。

f(5) ┬ f(4) ┬ f(3) ┬ f(2) ┬ f(1)
     │      │      │      │
     │      │      │      └ f(0)
     │      │      └ f(1)
     │      └ f(2) ┬ f(1)
     │              │
     │              └ f(0)
     │
     └ f(3) ┬ f(2) ┬ f(1)
             │      │
             │      └ f(0)
             └ f(1)

    図 : fibo のトレース

同じ値を何回も求めているため、効率はとても悪いのです。もちろん、高速に求める方法があるので、心配しないで下さい。

●ユークリッドの互除法

フィボナッチ関数は二重再帰でプログラムしたので実行速度はとても遅いのですが、再帰定義を使うと非効率的なプログラムになるというわけではありません。再帰定義でも効率的なプログラムを作ることができます。簡単な例題として、負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ってみましょう。まず最初に、ユークリッドの互除法を説明します。

[ユークリッドの互除法]
負でない整数 $a, b \ (a \gt b)$ で、$a$ を $b$ で割った余りを $r$ とする。
このとき、$a$ と $b$ の最大公約数は $b$ と $r$ の最大公約数に等しい。

ユークリッドの互除法は簡単に証明できます。$a$ と $b$ の割り算を式 (1) で表します。

$a = q \times b + r \quad \quad (1)$

ここで、$a$ と $b$ の最大公約数を $m$ とすると、$a = m \times a', \ b = m \times b'$ となります。すると、式 (1) は式 (2) で表すことができます。

$m \times a' = q \times m \times b' + r \quad \quad (2)$

左辺は $m$ で割り切れるので、右辺も $m$ で割り切れる必要があります。$q \times m \times b'$ は $m$ で割り切れるので、$r$ も $m$ で割り切れることになります。つまり、$m$ は $b$ と $r$ の公約数であることがわかります。$b$ と $r$ の最大公約数を $m'$ とすると、式 (3) が成り立ちます。

$m \leq m' \quad \quad (3)$

次に、$b = m' \times b'', \ r = m' \times r' $として式 (1) に代入すると、式 (4) が成り立ちます。

$a = q \times m' \times b'' + m' \times r' \quad \quad (4)$

右辺は $m'$ で割り切れるので、$a$ も $m'$ で割り切れる必要があります。つまり、$m'$ は $a$ と $b$ の公約数であることがわかります。したがって、式 (5) が成り立ちます。

$m' \leq m \quad \quad (5)$

式 (3) と (5) より $m = m'$ となり、$a$ と $b$ の最大公約数は $b$ と $r$ の最大公約数に等しいことが証明されました。

あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。

プログラムは再帰定義を使って簡単に作ることができます。次のリストを見てください。関数 gcd は Haskell に定義されているので、ここでは関数名を gcd' としました。

リスト : 最大公約数

gcd' :: (Integer, Integer) -> Integer
gcd' (a, b) =
  if b == 0 then a else gcd' (b, a `mod` b)

関数 gcd' は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ gcd' を再帰呼び出しして、b と a `mod` b の最大公約数を求めます。上のリストはユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。

それでは実行例を示しましょう。

ghci> gcd' (42, 30)
6
ghci> gcd' (15, 70)
5

最小公倍数は最大公約数を使って簡単に求めることができます。次のリストを見てください。

リスト : 最大公倍数

lcm' :: (Integer, Integer) -> Integer
lcm' (a, b) = a * b `div` gcd' (a, b)

Haskell には関数 lcm が定義されているので、ここでは関数名を lcm' としました。整数 a と b の最小公倍数は a * b / gcd' (a, b) で求めることができます。実行例を示します。

ghci> lcm' (5, 7)
35
ghci> lcm' (14, 35)
70

●組み合わせの数

次は組み合わせの数を求めるプログラムを作ってみましょう。ここでは組み合わせの数を ${}_n \mathrm{C}_r$ と表記します。${}_n \mathrm{C}_r$ を求めるには、次の公式を使えば簡単です。

$ {}_n \mathrm{C}_r = \dfrac{n \times (n-1) \times (n-2) \times \cdots \times (n - r + 1)}{1 \times 2 \times 3 \times \cdots \times r} = \dfrac{n!}{r! \times (n-r)!} $

皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。Haskell は多倍長演算をサポートしているので、桁あふれを心配する必要はありません。

この公式をそのままプログラムすることもできますが、次の式を使うともっと簡単にプログラムできます。

$ {}_n \mathrm{C}_r = \begin{cases} 1 & \mathrm{if} \ r = 0 \\ 1 & \mathrm{if} \ r = n \\ {}_n \mathrm{C}_{r-1} \times (n - r + 1) \div r \quad & \mathrm{if} \ r \gt 0 \end{cases} $

この式は ${}_n \mathrm{C}_r$ と ${}_n \mathrm{C}_{r-1}$ の関係を表しています。あとは階乗と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。

リスト : 組み合わせの数を求める

comb :: (Integer,Integer) -> Integer
comb (n, r) =
  if n == r || r == 0 then 1
  else comb (n, r - 1) * (n - r + 1) `div` r

定義をそのままプログラムしただけです。それでは実行してみましょう。

ghci> comb (20, 10)
184756
ghci> comb (30, 15)
155117520
ghci> comb (40, 20)
137846528820

ところで、整数値の範囲が限られているプログラミング言語では、この方法でも桁あふれする場合があるので注意してください。

●累乗の計算

次は累乗を求める関数 pow を作ってみましょう。累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは x ** n と書くことにします。なお、Haskell には累乗を求める演算子 ^ が用意されています。

pow (x, y) = x ** y

x ** 3 = x * x * x;
x ** 4 = x * x * x * x;
x ** 5 = x * x * x * x * x;

  図 : 累乗の計算

今回のプログラムは、引数 x を Integer、y を Integer とします。そうすると、x ** y は次のように定義することができます。

$\begin{array}{l} x ** \ 0 = 1 \\ x ** \ y = x \times (x ** \ (y - 1)) \end{array}$

図 : 累乗の定義

階乗の場合と同様に、x ** y は x ** (y - 1) がわかれば求めることができます。プログラムは次のようになります。

リスト : 累乗 (1)

pow :: (Integer, Integer) -> Integer
pow (x, y) =
  if y == 0 then 1 else x * pow (x, y - 1)

ghci> pow (2, 8)
256
ghci> pow (2, 16)
65536
ghci> pow (2, 32)
4294967296

再帰定義を使って x ** y を計算しています。手続き型言語では単純な繰り返しで実現できる処理ですが、関数型言語では単純な繰り返しでも再帰定義を使って実現します。

●累乗の高速化

関数 pow は n 回の掛け算をしなくてはいけませんが、式を変形するともっと少ない回数で累乗を求めることがでます。次の式を見てください。

x ** 4  = (x ** 2) ** 2 -> 2 回
x ** 8  = (x ** 4) ** 2 -> 3 回
x ** 16 = (x ** 8) ** 2 -> 4 回

一般化すると

x ** y = (x ** (y / 2)) ** 2       （n は偶数）
x ** y = ((x ** (y / 2)) ** 2) * x （n は奇数）

        図 : 累乗の高速化

階乗の計算では n を n - 1 の計算に置き換えていきますが、累乗の場合は y を y / 2 に置き換えていくことができます。y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。これを単純にプログラムすると、次のようになります。

リスト : 累乗 (2)

pow' :: (Integer, Integer) -> Integer
pow' (x, y) =
  if y == 0 then 1
  else if even y then pow' (x, y `div` 2) * pow' (x, y `div` 2)
       else x * pow' (x, y `div` 2) * pow' (x, y `div` 2)

それでは実行してみましょう。

ghci> pow' (2, 16)
65536
ghci> pow' (2, 15)
32768
ghci> pow' (2, 31)
2147483648

ところで、このプログラムは y が偶数の場合でも奇数の場合でも、pow' (x, y / 2) を 2 回呼び出していますね。このような場合、関数の中で局所変数を定義すると無駄を省くことができます。

●let 式による局所変数の定義

Haskell の場合、let 式で局所変数を定義することができます。

let 変数 = 式1 in 式2
let {変数1 = 式1; 変数2 = 式2; ...} in 式n

let 式は let ... in の間にある式を評価して、その結果を変数に束縛します (正確にいうと変数の値が必要になったときに式が評価されます)。そして、in 以降の式を評価します。その評価結果が let 式の返り値になります。また、let 式を使って局所的な関数を定義することもできます。変数の有効範囲は let 式の中だけになります。

変数は複数定義することができますが、その場合は { } で囲ってセミコロン ( ; ) で区切ってください。ただし、ファイルに書き込む場合はインデントを揃えることで { } と ; を省略することができます。これはあとで説明します。

関数 pow' の場合、同じ計算を 2 回しているのは無駄なので、let を使って局所変数を定義しましょう。次のリストを見てください。

リスト : 累乗 (3)

pow'' :: (Integer, Integer) -> Integer
pow'' (x, y) =
  if y == 0 then 1
  else let z1 = pow'' (x, y `div` 2)
           z2 = z1 * z1
       in if even y then z2 else x * z2

let で局所変数 z1 と z2 を定義します。let は式なので、if の then 節や else 節に入れてもかまいません。z1 の値は x ** (y/2) です。これは pow を再帰呼び出しすれば簡単に求めることができます。z2 の値は z1 * z1 になります。あとは、y が偶数であれば、z2 をそのまま返し、奇数であれば x * z2 を返します。このように、局所変数 z1 に pow (x, y `div` 2) の値を求めておくことで、累乗を効率的に計算することができます。

●レイアウト

ところで、let で複数の変数を定義していますが、{ } と ; が書かれていませんね。Haskell はインデントをそろえることで、{ } の範囲を指定することができます。このとき ; を省くことができます。この機能を「レイアウト」といいます。ルールは簡単で、let の後に出現する最初の変数名の位置にインデントを揃えます。次の例を見てください。

リスト : レイアウトの例

-- その１
let a = ...
    b = ...
    c = ...
in ...

-- その２
let
  a = ...
  b = ...
  c = ...
in ...

その１では、変数 a が 4 桁目から定義されているので、それ以降の変数定義は同じ位置 (4 桁目) から始めます。インデントが変わると、そこで { } の範囲が終了したと判断されます。また、let の後に改行を入れてもかまいません。その２では、最初に現れる変数 a が 2 桁目から定義されているので、他の変数も 2 桁目から定義します。

●where 節による局所変数の定義

局所変数は let 式だけではなく where 節を使って定義することもできます。もちろん、局所関数の定義もできます。累乗のプログラムを where 節を使って書き直すと次のようになります。

リスト : 累乗 (4)

pow''' :: (Integer, Integer) -> Integer
pow''' (x, y) =
  if y == 0 then 1
  else if even y then z2
       else x * z2
  where z1 = pow''' (x, y `div` 2)
        z2 = z1 * z1

式の後ろに where 節を定義します。where 節は式ではないので値を返すことはありません。where 節はレイアウトを使うことができます。この中で局所変数 z1 と z2 を定義します。where 節で定義された局所変数の有効範囲は、where 節の前に定義されている式になります。

●再帰定義によるリスト操作

リストを操作する関数は再帰定義を使うと簡単に作ることができます。実は、リスト操作と再帰定義はとても相性が良いのです。まずは、リストの長さを求める関数 length' を作りましょう。 Hakell には length という同等の機能を持つ関数が用意されていますが、再帰定義を使えば私達でも簡単に作ることができます。

まず、いちばん簡単な場合を考えます。引数が空リスト [ ] であれば 0 を返せばいいですね。あとは、リストが空リストになるように分解していけばいいのです。つまり、リスト xs の長さを求めるには、リスト xs に tail を適用したリストの長さがわかればいい、と考えるのです。それに 1 を足せば、リストの長さを求めることができます。これをプログラムすると、次のようになります。

リスト : リストの長さを求める

length' :: [a] -> Int
length' xs =
  if null xs then 0
  else 1 + length (tail xs)

関数 null xs は引数 xs が空リストであれば真 (True) を返し、そうでなければ偽 (False) を返します。引数 xs が空リストであれば 0 を返します。そうでなければ、引数 xs に関数 tail を適用して length' を再帰呼び出しします。リストに taill を繰り返し適用していくと最後は空リストになります。ここで再帰呼び出しが止まって 0 を返します。そうすると、1 + length' によって length' の返り値に 1 を足した値を返していきます。すなわち tail した回数だけ 1 が足されるわけです。

●多相型関数

ところで、Haskell では格納するデータ型によってリストの型は変化します。もしも、[Integer] と [String] で異なる関数が必要だとしたら、とても面倒なことですね。ところが Haskell の場合、関数をひとつ定義するだけで、[Integer] にも [String] にも [Char] にも対応することができます。このような関数を「多相型関数 (polymorphic function)」といいます。

多相型関数の極端な例に「恒等関数 (identity function)」があります。次の例を見てください。

ghci> identity x = x
ghci> :t identity
identity :: p -> p
ghci> identity 10
10
ghci> identity 1.2345
1.2345
ghci> identity 'a'
'a'
ghci> identity [1,2,3,4,5]
[1,2,3,4,5]
ghci> identity (1, 'a')
(1,'a')

関数 identity は引数をそのまま返す関数です。identity の型は p -> p なので、任意の型のデータを受け取り、同じ型を返す関数であることがわかります。したがって、identity は Integer, Double, Char, [Integer] など、Haskell のデータ型であれば何でも対応することができます。なお、Haskell には identity と同じ働きをする関数 id が用意されています。

length' の場合、任意の型 a を格納するリストを引数に取り、Int を返すことが示されています。つまり、引数が [Integer] でも [String] でも、リストであればその長さを返すことができます。このように、length' は多相型関数として定義されます。Haskell の関数 null, head, tail, fst, snd も多相型関数です。

それでは実際に試してみましょう。

ghci> length' [1,2,3,4,5]
5
ghci> length' ["foo", "bar", "baz"]
3
ghci> length' []
0

正常に動作していますね。Haskell は型チェックを厳密に行うプログラミング言語ですが、多相型関数により柔軟なプログラミングが可能になっています。

●リストの連結

次はリストを連結する演算子 ++ と同じ動作をする関数 append を作ってみましょう。引数としてリスト xs と ys を渡して、それを連結したリストを返します。

処理手順ですが、簡単な場合から考えていきましょう。まず、リスト xs が空リストならば、リスト ys を返すだけでいいですね。次に、リスト xs に要素が 1 つしかない場合を考えてみます。これは、リスト xs に head を適用して要素を取り出し、それをコンス演算子でリスト ys の先頭に追加すればいいでしょう。

それでは、リスト x に要素が複数ある場合を考えてください。リスト xs を head と tail で分解します。そして、tail xs と ys を連結したリストを求め、そのリストの先頭に head xs を追加すれば xs と ys を連結することができます。tail xs と ys の連結は再帰呼び出しで実現することができます。これを図に示すと次のようになります。

 ┌────────────────────────────┐ 
 │append( [1, 2], [3, 4] )                                │
 ├────────────────────────────┤
 │ [ 1,  2 ]                                              │
 │  ┬  ───tail─┐                                    │
 │ head             ↓                                    │
 │  │    ┌──────────────────────┐│
 │  │    │append( [2], [3, 4] )                       ││
 │  │    ├──────────────────────┤│
 │  │    │ [  2     ]                                 ││
 │  │    │    ┬── tail─┐                         ││
 │  │    │   head          ↓                         ││
 │  │    │    │  ┌────────────────┐││
 │  │    │    │  │append( [],  [3, 4] ) => [3, 4] │││
 │  │    │    │  └────────────────┘││
 │  │    │    │            │                        ││
 │  │    │    └─→ :  ←─┘                        ││
 │  │    │       [2, 3, 4]                            ││
 │  │    └─────┼────────────────┘│
 │  └──→  :   ←─┘                                  │
 └──────┼─────────────────────┘
               ↓
           [1, 2, 3, 4]

                    図：append の動作

これをプログラムすると次のようになります。

リスト : リストの結合

append :: ([a], [a]) -> [a]
append (xs, ys) =
  if null xs then ys
  else head xs : append (tail xs, ys)

引数 xs が空リストであればリスト ys をそのまま返します。これが再帰呼び出しの停止条件になります。そうでなければ、tail xs を append に渡して再帰呼び出しします。そして、その返り値と head xs をコンス演算子で接続します。これでリストを連結することができます。

append も多相型関数になります。簡単な実行例を示します。

ghci> append ([1,2,3], [4,5,6])
[1,2,3,4,5,6]
ghci> append ("foo", "bar")
"foobar"
ghci> append (["foo", "bar"], ["baz", "oops"])
["foo","bar","baz","oops"]

●リストの反転

今度はリストの要素を反転する関数 reverse' を作ってみましょう。Haskell には reverse という同等の機能を持つ関数が用意されていますが、再帰定義で簡単に作ることができます。reverse' は引数のリスト xs を head と tail で分解し、tail xs を反転させてから head xs を最後尾に追加することで実現できます。次の図を見てください。

  [1, 2, 3]                                 [3, 2] ++ [1] => [3, 2, 1]  
        ↓                                  ↑
     [2, 3]                   [3] ++ [2] => [3, 2]
        ↓                    ↑
        [3]     nil ++ [3] => [3]
        ↓      ↑
        nil ──┘

                図 : reverse' の動作

これをプログラムすると、次のようになります。

リスト：リストの反転

reverse' :: [a] -> [a]
reverse' xs =
  if null xs then []
  else reverse' (tail xs) ++ [head xs]

引数 x が空リストの場合は [ ] を返します。そうでなければ、reverse' を再帰呼び出しして tail xs を反転し、演算子 ++ で反転したリストの最後尾に先頭の要素を追加します。

reverse' も多相型関数になります。簡単な実行例を示します。

ghci> reverse' [1,2,3,4,5]
[5,4,3,2,1]
ghci> reverse' ["foo", "bar", "baz"]
["baz","bar","foo"]
ghci> reverse' "abcdefg"
"gfedcba"

●リストの探索

次はリストからデータを探索する関数 member を作ってみましょう。関数の名前と動作は Common Lisp から拝借しました。member はリストの中にデータがなければ空リスト [ ] を返します。データを見つけた場合は、そのリストの残りを返します。つまり、返り値のリストの先頭要素が見つけたデータになります。

プログラムは次のようになります。

リスト：リストの探索

member :: Eq a => (a, [a]) -> [a]
member (x, xs) =
  if null xs then []
  else if x == head xs then xs
       else member (x, tail xs)

関数 member はリスト xs の中から x を探します。これは member を再帰呼び出ししてリストを分解し、リストの先頭要素をチェックしていくことで実現できます。xs が空リストの場合は x を見つけることができなかったので [ ] を返します。これが再帰の停止条件になります。次に、リスト xs の先頭の要素 head xs が x と等しいかチェックします。そうであれば、リスト xs をそのまま返します。そうでなければ、member を再帰呼び出しして次の要素を調べます。

ここで member の型に注目してください。型クラス制約 Eq a が指定されていすね。Eq は等値演算子 ==, /= が定義されている型クラスです。つまり、型 a は等値演算子 (=, /=) を適用できる型に限られるわけです。Integer, Double, Char, Bool など基本的な型は Eq のインスタンスです。また、等値演算子はタプルやリストにも適用できますが、要素の型が Eq のインスタンスでないとエラーになります。

ghci> (1, 2) == (1, 2)
True
ghci> (1, 2) == (1, 3)
False
ghci> [1,2,3,4] == [1,2,3,4]
True
ghci> [1,2,3,4] == [1,2,3,5]
False

member は多相型関数ですが、データの比較で演算子 == を使っているため、要素の型が型クラス Eq で制限されているのです。それでは、簡単な実行例を示します。

ghci> member (5, [1,2,3,4,5,6,7,8])
[5,6,7,8]
ghci> member (1, [1,2,3,4,5,6,7,8])
[1,2,3,4,5,6,7,8]
ghci> member (8, [1,2,3,4,5,6,7,8])
[8]
ghci> member (9, [1,2,3,4,5,6,7,8])
[]

ghci> member ("foo", ["foo", "bar", "baz"])
["foo","bar","baz"]
ghci> member ("baz", ["foo", "bar", "baz"])
["baz"]
ghci> member ("a", ["foo", "bar", "baz"])
[]

member はリストを返しますが、真偽値を返すようにプログラムすることも簡単です。Haskell の関数 elem はデータを見つけたら True を、見つからなかったら False を返します。elem はカリー化関数という形式で定義されていますが、タプルを使ってプログラムすると次のようになります。

リスト：リストの探索 (2)

elem' :: Eq a => (a, [a]) -> Bool
elem' (x, xs) =
  if null xs then False
  else if x == head xs then True
       else elem' (x, tail xs)

簡単な実行例を示します。

ghci> elem'(5, [1,2,3,4,5,6,7,8])
True
ghci> elem'(1, [1,2,3,4,5,6,7,8])
True
ghci> elem'(8, [1,2,3,4,5,6,7,8])
True
ghci> elem'(9, [1,2,3,4,5,6,7,8])
False

●問題

次の関数を定義してください。

リスト xs の要素がただひとつか調べる述語 single xs
リスト xs の要素が二つあるか調べる述語 double xs
リスト xs はリスト ys よりも長いとき真を返す関数 longer (xs, ys)
リスト xs の先頭から n 個の要素を取り出す関数 take' (n, xs)
リスト xs の先頭から n 個の要素を取り除く関数 drop' (n, xs)

Haskell には同様の関数 take n xs と drop n xs がある

リスト xs の n 番目の要素を求める関数 nth (n, xs)
リスト xs の要素を足し算する関数 sum' xs
リスト xs の要素を掛け算する関数 product' xs

Haskell には同様の関数 sum xs と product xs がある

●解答

ghci> single xs = not (null xs) && null (tail xs)
ghci> single [1]
True
ghci> single [1, 2]
False
ghci> single (tail [1])
False

ghci> double xs = not (null xs) && single (tail xs)
ghci> double [1]
False
ghci> double [1, 2]
True
ghci> double [1, 2, 3]
False
ghci> double (tail [1])
False

ghci> longer (xs, ys) = if null xs then False else if null ys then True 
else longer (tail xs, tail ys)
ghci> longer ([1,2,3],[4,5,6])
False
ghci> longer ([1,2,3],[4,5])
True
ghci> longer ([1,2,3],[4,5,6,7])
False
ghci> longer ([],[4,5,6,7])
False
ghci> longer ([],[])
False

ghci> take' (n, xs) = if n == 0 || null xs then [] else (head xs) : 
take' (n - 1, tail xs)
ghci> take' (3, [1,2,3,4,5])
[1,2,3]
ghci> take' (0, [1,2,3,4,5])
[]
ghci> take' (5, [1,2,3,4,5])
[1,2,3,4,5]
ghci> take' (6, [1,2,3,4,5])
[1,2,3,4,5]

ghci> drop' (n, xs) = if n == 0 || null xs then xs
else drop' (n - 1, tail xs)
ghci> drop' (3, [1,2,3,4,5])
[4,5]
ghci> drop' (0, [1,2,3,4,5])
[1,2,3,4,5]
ghci> drop' (5, [1,2,3,4,5])
[]
ghci> drop' (6, [1,2,3,4,5])
[]

ghci> nth (n, xs) = if n == 0 then head xs else nth (n - 1, tail xs)
ghci> nth (3, [1,2,3,4,5])
4
ghci> nth (0, [1,2,3,4,5])
1
ghci> nth (4, [1,2,3,4,5])
5
ghci> nth (5, [1,2,3,4,5])
*** Exception: Prelude.head: empty list

ghci> sum' xs = if null xs then 0 else (head xs) + sum' (tail xs)
ghci> sum' [1,2,3,4,5,6,7,8,9,10]
55
ghci> sum' [1,4,9,16,25,36]
91

ghci> product' xs = if null xs then 1 else (head xs) * product' (tail xs)
ghci> product' [1,2,3,4,5,6,7,8,9,10]
3628800
ghci> product' [1,4,9,16,25,36]
518400

nth は drop を使って、nth (n, xs) = head (drop (n, xs)) としてもよい