代表技術通信～Get Programming with Haskell⑨

草場代表

2020/12/03

テック

こんばんは。代表の草場です。

Haskell触ります。「Get Programming with Haskell」についてです。レッスン７です。

レッスン7. 再帰とパターンマッチングのルール

レッスン7を読んだ後は、次のようになります。

再帰関数の定義を理解する
再帰関数を書くためのルールを学ぶ
再帰的な関数定義の例を見て歩く
基本的なパターンマッチングを使用して再帰的な問題を解く

関数型言語で実用的なコードを書く上での最初の課題の一つは、状態変化がないために、forループ、whileループ、 untilループなどの状態変化に依存する一般的なループ関数がないことです。すべての反復問題は再帰によって解決しなければなりません。

いくつかの簡単なルールを使えば、再帰を簡単にすることができます。さらに、Haskellが部分的なアプリケーションを提供してクロージャの作業を容易にしているように、Haskellはパターンマッチングと呼ばれる機能を提供しており、再帰についての推論をやりやすくしてくれます。

前のレッスンでは、リストからn個の要素を取ることができる関数takeを学びました。

take 3 [1,2,3,4]
[1,2,3]

Haskellで独自バージョンのtakeを書くにはどうすればよいでしょうか？

7.1. Recursion

再帰は、プログラミングにおける他の形式の反復よりもずっと自然であることが多いです。リストは、空のリスト、または要素と別のリストとして定義された再帰的なデータ構造です。再帰関数とは、それ自身の定義で自分自身を使用する関数に過ぎません。再帰的な関数を、再帰的なプロセスを定義するもの、と考えれば、再帰はかなり平凡なものになります。

食器を洗うことを考えてみましょう。食器を洗うことを考えてみましょう。シンクに皿がなければ、洗い終わったことになるが、皿があれば、それをつかんで、きれいにして、ラックの上に置く。洗い物を続けるには、洗い終わるまで繰り返します。

7.2. 再帰の規則

再帰処理で困るのは、再帰的な処理を書き出すときです。再帰的な関数を書くコツは、再帰のことを考えないことです。再帰関数を解く方法は、このシンプルなルールに従うことです。

１．最終ゴールを特定する。
２．ゴールに到達したときに何が起こるかを決定する。
３．すべての代替可能性をリストアップする。
４．すすぎと繰り返し」のプロセスを決定します。
５．それぞれの代替案がゴールに向かってあなたを動かすことを確認してください。

7.2.1. ルール1: 最終目標を特定する

一般的に、再帰的なプロセスは終わりを迎えます。リストの場合、プロセスの終わりは空のリストであり、皿を洗う場合は空のシンクです。何かが再帰的なプロセスであることを認識したら、それを解決するための最初のステップは、いつ終了するかを知ることです。時には、目標が1つだけではないこともあります。テレマーケティング担当者は、100人に電話をかけたり、5つのセールスをしてからその日を迎えようとしているかもしれません。この場合、ゴールは100人に電話をかけたか、5つのセールスをしたかのどちらかです。

7.2.2. ルール2. 目標が達成されたときに何が起こるかを決定する

ルール１で設定した目標ごとに、その結果がどうなるかを考えてみましょう。皿洗いの場合は、皿洗いが終わったという結果になります。関数の場合は、値を返す必要があるので、終了状態でどのような値を返すかを決めなければなりません。

プログラマーが直面する典型的な問題は、ゴールの状態を長い再帰的なプロセスの終わりという観点から考えようとすることです。これは通常、不必要で複雑になりすぎています。多くの場合、「ゴール状態の値で自分の関数を呼び出すとどうなるか」という質問をすると、答えは明らかです。例えば、フィボナッチ数列の終了状態は 1 に到達することです。

7.2.3. ルール3: すべての代替可能性をリストアップする

目標の状態になっていない場合、どうでしょうか？ほとんどの場合、目標状態にあることの選択肢は1つか2つしかありません。

空のリストがなければ、何かが入っているリストを持っていることになります。シンクが空でなければ、皿のあるシンクを持っています。電話をかけているテレマーケティング担当者の場合、まだ100人に電話をかけたり、5つの売上を上げたりしていない場合、2つの可能性があります。電話をかけて売上を上げるか、電話をかけても売上を上げないかです。

7.2.4. ルール4: “Rinse and Repeat “を見極める

このルールはルール2とほぼ同じですが、処理を繰り返さなければなりません。考えすぎたり、再帰を解こうとしたりしないでください。

リストの場合は、要素を取って尻尾を見るかもしれません。皿を洗う場合は、皿を洗って、乾かすために立てて、もう一度シンクの中を見ます。テレマーケティングの場合は、電話をかけて、売り込みを記録して繰り返すか、電話がかかってきた（売り込みはしていない）と記録して繰り返す。

7.2.5. ルール5：それぞれの変化がゴールに向かって自分を動かすことを確認する

ルール４でリストアップしたすべてのプロセスについて、”これはゴールに近づいているか？“と自問自答する必要があります。もしあなたがリストの最後尾を取り続ければ、空っぽのリストを手に入れることになります。シンクから皿を取り続ければ、空っぽのシンクを手に入れることができます。売上と電話のどちらかを記録すると、最終的にはそれぞれのカウントがゴールに近づくことになります。

しかし、あなたがheadを得るまでコインを反転させたいと仮定します。目標はheadを得ることです。headを得たら、停止します。もう一つの方法は、裏表を取ることです。裏表を取ったら、もう一度裏返します。しかし、もう一度反転してもheadが取れるわけではありません。

7.3. あなたの最初の回帰関数：最大の共通ディバイザ

再帰を導入するに、ユークリッドのアルゴリズムから始めます。このアルゴリズムは、2つの数の最大公約除数（GCD）を計算するための方法です。例えば、20と16のGCDは4です。ユークリッドはこのアルゴリズムの概要は以下の通りです．

１．aとbという2つの数字から始めます。
２．a を b で割って残りが 0 であれば、明らかに b が GCD であることになります。
３．そうでなければ、aの値をbの値に代入して変更します（bは新しいaになります）。また、b の値を 2 で得た余りに変更します（新しい b は、元の a の余りを元の b で割ったものです）。
４．そして、a/b に余白がなくなるまで繰り返します。

例えば、

１．a = 20, b = 16
２．a/b = 20/16 = 1 余り4
３．a = 16, b = 4
４．a/b = 4　余り0
５．ＧＣＤ＝ｂ＝４である。

このアルゴリズムをコードで実装するには、ゴール条件（ルール1）から始めます。目標は、a/b の余りがないことです。コードでは、この考えを表現するためにモジュラス関数を使用します。

a `mod` b == 0

次に、ゴールの状態になったら何を返すかという問題です（ルール２）。a/b に余りがない場合、b は a を均等に割らなければならないので、b が GCD となります。これにより、ゴールの動作全体が得られます。

if a `mod` b == 0
then b ....

次に、目標が達成されなかった場合に、目標に近づくための方法をすべて見つけ出す必要があります（ルール 3）。この問題では、余りが 0 ではないという選択肢が 1 つだけあります。余りが 0 でない場合、b を新しい a、新しい b を余りとするアルゴリズムを繰り返します: a `mod` b (規則 4)。

else gcd b (a `mod` b)

これらすべてをユークリッドのアルゴリズムの再帰的な実装に入れることができます。

myGCD a b = if remainder == 0
then b
else myGCD b remainder
where remainder = a `mod` b

最後に，目標に向かって進んでいることを確認します（ルール5）．余りを使うと、常に新しい b を縮小することになります。両方の数値が素数である場合、最終的に a と b の値は 1 になります。

再帰関数を作成するためのルールに従うことで、無限に続く螺旋状の再帰について深く考える必要がなくなりました。

この myGCD の例では、2 つのこと、目標が達成されるか、またはプロセスが繰り返されるか、が起こります。これは if then else 式にぴったりです。

Haskellにはパターンマッチングという素晴らしい機能があり、引数として渡された値を覗き見して、それに応じた振る舞いをすることができます。

1なら “1”、2なら “2 “を返し、それ以外は束を返す関数sayAmountを作ってみます。まず、関数の定義でパターンマッチではなくケースを使うことでこれを実装する方法を見てみます。

sayAmount n = case n of
　1 -> "one"
　2 -> "two"
　n -> "a bunch"

これのパターンマッチバージョンは3つの別々の定義のように見え、それぞれが可能な引数の1つに対応します。

sayAmount 1 = "one"
sayAmount 2 = "2"
sayAmount n = "a bunch"

パターンマッチングは、ケースと同じように、オプションを順番に見ていくので、もしsayAmount nをリストの最初に置いた場合、sayAmountを呼び出すと、常に “a bunch “を返します。

パターン・マッチングについて理解しておくべき重要なことは、パターン・マッチングは引数のみを見ることができますが、マッチングの際に引数に対する計算を行うことができないということです。例えば、パターンマッチングでは、nが0より小さいかどうかを調べることはできません。パターン・マッチングを使用して、[] に対してマッチングを行うことで、リストが空かどうかをチェックすることができます。

isEmpty [] = True
isEmpty aList = False