【Haskell】再帰関数の実装方法

Haskellを使って再帰関数を実装する方法を解説します。forやwhileといった制御構文がないHaskellにとっては再帰関数は非常に重要な関数です。

Contents

1 Haskellにおける再帰関数
2 まとめ

Haskellにおける再帰関数

再帰関数とは、自分自身を呼び出す関数のことを言います。純粋関数型のプログラミング言語であり、関数を主体にプログラミングを行っていくHaskellにとって再帰関数は非常に重要なものになっています。

本記事では、Haskellを使って再帰関数を実装する方法を紹介します。

Haskellにおける再帰関数の重要性

C/C++、Java、Pythonといった手続き型、オブジェクト指向型のプログラミング言語を学んできた人にとってHaskellを勉強した時に戸惑うことがあります。多くのプログラミング言語では、繰り返しの制御を行うためにforやwhileといった制御構文がありますが、Haskellにはないことです。

では、Haskellではどのように繰り返し処理を行うかというと、そこで登場するのが再帰関数です。再帰関数で表現することについては理解しにくい部分かと思いますが、Haskellを学んで慣れていくことで非常に美しい直感的なコードを書くことができるようになります。

本記事では、Haskellで再帰関数を実装する方法について紹介していきます。

再帰関数の基本

再帰関数とは、どういったものでしょうか。例えば再帰関数の代表的な例として$n!=n\cdot(n-1)\cdot…\cdot2\cdot1$といった階乗を求める関数があります。なお、$0!=1$です。

Haskellで階乗を求める関数を実装する場合は以下のようになります。

-- 階乗関数
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n-1)

【実行例】
ghci> factorial 1
1
ghci> factorial 2
2
ghci> factorial 3
6
ghci> factorial 4
24
ghci> factorial 5
120

Haskellの再帰関数を記述するときに非常に重要になってくるのは、パターンマッチという機能です。パターンマッチについては「関数におけるパターンマッチ」でまとめていますので参考にしてください。

階乗関数では、$0!=1$です。このパターンを示しているのがfactorial 0 = 1の部分です。$n$番目の値を処理する場合には、$n$と$n-1!$をかけることになるのでfactorial n = n * factorial (n-1)となります。nに値を入れてみて自分で展開してみると分かりやすいでしょう。

上記コードは負の数に対するエラーなどは考慮していません。今回は再帰部分に焦点を当てるために除外してシンプルにしていますが、適切な関数として考慮する場合にはEither型クラスを利用した実装等を検討する必要があることに注意が必要です。詳細説明は省略しますが、例えば以下のような実装例が考えられます。

factorial' :: Integer -> Either String Integer
factorial' n
    | n < 0     = Left "Error: Negative numbers are not allowed."
    | n == 0    = Right 1
    | otherwise = case factorial' (n - 1) of
        Left err -> Left err
        Right res -> Right (n * res)

【実行例】
ghci> factorial' 5
Right 120
ghci> factorial' (-1)
Left "Error: Negative numbers are not allowed."

階乗関数は他の言語でも再帰で実装されることがあるので、もう少し違う例を見てみましょう。非常に簡単ですが、リストの要素を順番に取り出して値を2倍する関数を考えます。この時、他の言語ではfor文で要素を一つずつ取り出して2倍していくという方法をとるかもしれません。しかし、Haskellではfor文などの繰り返し制御構文がないため、こういった対応ができません。Haskellでは以下のように関数を定義します。

-- リストを2倍する関数
doubleList :: [Integer] -> [Integer]
doubleList [] = []
doubleList (x:xs) = (2 * x) : doubleList xs

【実行例】
ghci> doubleList [1, 2, 3, 4, 5] 
[2,4,6,8,10]

リストを2倍するには「先頭から1要素取り出して2倍し、残りのリストの各要素を2倍したリストと結合する」と考えてみます。この処理の終了条件を考えていくと、要素を取り出していった場合には最後には空リスト[]が残ります。この空リスト[]に対する結果は、空リスト[]でよいでしょう。この部分がdoubleList [] = []となります。

では、繰り返しプロセス「先頭から1要素取り出して2倍し、残りのリストの各要素を2倍したリストと結合する」の定義を考えてみます。Haskellでは(x:xs)というパターンマッチで先頭要素xと残りのリストxsを取得することができます。取り出した先頭要素を2倍し、残りのリストを2倍したリストと結合します。この部分が「doubleList (x:xs) = (2 * x) : doubleList xs」になります。リストの結合は「:」で実行でき、コンスと呼ばれます。

実行例を見ても分かるようにこのように実装することでリストを2倍したリストを取得できていることが分かります。

上記の例を参考にして再帰のプログラミングをする際の考え方を整理してみると以下のようになります。

再帰関数定義の考え方

再帰プロセスの終了条件を決め、終了時の結果を定義する
再帰の繰り返しプロセスを決めて定義する

１の手順は、factorialの場合は「factorial 0 = 1」、doubleListの場合は「doubleList [] = []」に該当します。そして、２の手順がそれぞれ「factorial n = n * factorial (n-1)」や「doubleList (x:xs) = (2 * x) : doubleList xs」になります。

Haskellは宣言的に関数を定義するというのが特徴的で、処理の内容を捉えやすい理由です。「先頭から1要素取り出して2倍し、残りのリストの各要素を2倍したリストと結合する」ということが、まさに「doubleList (x:xs) = (2 * x) : doubleList xs」に表現されています。

多くの場合は便利な高階関数を利用する

上記では、再帰関数の定義の考え方について紹介してきました。しかし、Haskellでのプログラミングをする場合は、多くの場合は便利な高階関数を使用します。高階関数とは、関数を引数として受け取ったり、関数自体を返却したりする関数のことを言い、関数型プログラミングのパラダイムでよく登場します。

例えば、上記で紹介したdoubleList関数は、map関数という高階関数を使って以下のdoubleList'関数のように書き換えることができます。

-- リストを2倍する関数
doubleList' :: [Integer] -> [Integer]
doubleList' xs = map (*2) xs

ghci> doubleList' [1, 2, 3, 4, 5]
[2,4,6,8,10]

再帰関数での実装例と比べるとシンプルになっていることが分かるかと思います。map関数は、関数とリストを受け取ってリスト要素のそれぞれに受け取った関数を適用した結果リストを返してくれます。Haskellでは(*2)は2倍するという関数を意味します。この関数とリストxsを引数に渡すとすべての要素に適用した結果リストを返してくれます。

他にも代表的な高階関数として要素を抽出するfilterや畳み込みのためのfoldl、foldrといった関数等がありますので、そういった関数をまずは使うことを考えるのが一般的です。これらの高階関数については、また別途まとめてみようかと思います。

なお、より複雑な処理などを検討する場合には自分で再帰関数を書くべき時もあるため、考え方をよく理解しておいてもらうと良いかと思います。