Recursions

このブログを始める前に、Haskellにはforループが存在しないという悪いニュースをお伝えしなければなりません。 では、どのようにしてループを実現するのか、と思っているかもしれませんね。Haskellでは、ループは再帰を使って実現します。 これが、Haskellを学ぶことが楽しく報われる理由の一つであり、すべてのことに盲目的にforループを使わずに再帰的に考えることを 強制されるからです。ここでは、数の階乗を計算する階乗関数factorialの例を見てみましょう。

factorial :: Integer -> Integer
factorial n = 
    if n == 1 then 1 --- base case
    else n * factorial (n-1)

美しいですね。 (再帰についての知識に不安を抱えている方はNorth Bay Pythonの Recursion for Beginners: A Beginner's Guide to Recursionというわかりやすい動画を視聴することをおすすめします。)

ガード

Haskellでは、多くの場合再帰を書く必要がありますが、すべての関数のすべてのケースでif文を書くのはかなり大変です。そこで、ガードの出番です。 ガードを使って、階乗関数factorialをリファクタリング(書き換え)してみましょう。

factorial n
    | n <= 1 = 1 --- base case
    | otherwise n * factorial (n-1)

otherwiseはHaskellでは常にTrueに評価されるので、elseの代替として使用できます。

アキュムレータ

Haskellでは、再帰を実装する別の方法もあります。階乗関数factorialの場合は次のようになります。

factorial n = aux n 1
  where
    aux n acc
        | n <= 1 = acc
        | otherwise = aux (n-1) (n*acc) 
        --- aux (n-1) $! (n*acc) for strictly evaluating (n*acc) and fully prevent stack overflow?
        --- If you are a good Haskeller, please reach out and lmk if $! is necessary. 

1部の人は上の関数を見て、「ただ無駄に複雑にしただけじゃないか」と言うかもしれません。確かに複雑ですが、これが階乗関数factorialを最適に実装する方法です。 なぜこれが最適な再帰なのかについて混乱している方のために、上記アルゴリズムのPython版を見てみましょう。

def factorial (n: int):
  acc = 1
  while True:
    if n <= 1:
      return acc
    else:
      acc = n * acc
      n = n - 1

上記のように、acc(アキュムレータ)を使って前の反復の結果を保存し、階乗関数内での再帰呼び出しを避けています。 これは末尾再帰と呼ばれ、古典的なスタックオーバーフロー問題を回避することができます。(末尾再帰とスタックオーバーフローについての知識に不安を抱えている方はNorth Bay Pythonの Recursion for Beginners: A Beginner's Guide to Recursionというわかりやすい動画を視聴することをおすすめします。)

一部の言語(PythonやCなど)のコンパイラは末尾再帰最適化をサポートしていませんが、HaskellのGHCはサポートしています。 これにより、適切な場合には通常の再帰関数が末尾再帰関数に変換されます。 ただ、個人的にはコンパイラに最適化を完全に頼りきるよりも、最適な関数についての十分な知識を各々が持つべきだと思っています。 (私はこの分野について多くを知っているわけではありませんが。末尾再帰をただすればいい訳でもなく、末尾再帰はアルゴリズムを悪化させることもあります。 再帰を適用する際には、問題を本当によく分析することが重要です。)

パターンマッチング

上記に加えて、Haskellでは次のようにパターンマッチングを行うことができます。

isZero 0 = True
isZero _ = False

このようにすると、他の言語では関数定義が上書きされる所を、Haskellでは入力に対してパターンマッチングを行い、対応する操作を実行することができます。_は、先に示した値以外の任意の値を示すために使用されます。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

• Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #3 - Recursions, Guards, Patterns. YouTube.