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

草場代表

2020/12/03

テック

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

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

レッスン8. 再帰関数を書く

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

再帰の規則を適用する一般的なパターンを参照してください。
リストでの再帰の使い方を理解する
GHCiで関数の時間を覚える
再帰の5つのルールのエッジケースについての推論

前のレッスンで紹介した再帰のルールを適用できるように、さまざまな再帰関数を使って説明します。再帰的な問題を解くときにいくつかのパターンが繰り返されることに気づくでしょう。

Haskellではステートフル反復を使用して「ごまかす」ことができないため、Haskellで書くコードのほとんどすべてに、何らかの再帰が含まれています。これにより、再帰的な関数を書いたり、再帰的なスタイルで問題を解決したりすることにすぐに慣れることができます。

drop関数を自分で書くことについて考えてみます。

drop 3 [1,2,3,4]
[4]

drop の独自のバージョンを書いて、この関数が take とどのように似ているか、また異なるかを考えてみます。

8.1. レビュー：RULES OF RECURSION

再帰的な関数の書き方のルールを再び紹介します。

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

この後、さまざまな例を見ていきます。

8.2. リストの再帰

レッスン6で、関数型プログラミングにおいてリストがいかに重要であるかについて話し、リストを使った作業をより簡単にするHaskellのPreludeに含まれる関数のいくつかについて説明しました。今回はそれらをゼロから書いてみましょう。これにより、実際の問題を解決するために再帰的に考える方法を示すとともに、Haskell のこれらの重要な関数がどのように機能するのかをより深く理解することができます。

8.2.1. 長さの実装

リストの長さを計算することは、リスト上の再帰関数の最も単純で簡単な例の一つです。パターンマッチングを使えば、問題の分解が簡単です。

ゴールの状態では、空のリストがあります（ルール1）。リスト上の再帰関数の大部分は、ゴールの状態として空のリストを持っています。そのゴールに到達したらどうするか(ルール2)。さて、空リストの長さは0です。これでゴールの状態が記述されました。

myLength [] = 0

次に、任意の代替ケースを考えなければなりません（ルール3）。選択肢は1つだけで、それは空でないリストです。空でないリストに遭遇したとき、1つの要素を見たことを知っています。この空でないリストの長さを得るために、リストの末尾の長さに1を足します(ルール４)。

myLength xs = 1 + myLength (tail xs)

自分が終わったと宣言する前に、このステップがゴールに向かって進むかどうかを考えなければなりません（ルール５）。リストの最後尾を取り続ければ、最終的には[]に到達します。他の代替の可能性は残されておらず、ゴールではない状態のそれぞれがゴールに向かって移動するので、これで終了です。

myLength [] = 0
myLength xs = 1 + myLength (tail xs)

8.2.2. takeの実装

take関数は2つの理由で興味深いです: takeは2つの引数nとリストを使います。ほとんどいつものように、takeは空のリスト[]で終了します。前述したように、tailやheadとは異なり、takeは空のリストを問題にせず、できる限り多くのアイテムを返します。takeが終了できるもう一つの条件は、n = 0の場合です。空のリストからn個の要素を取ることは[]であり、任意のリストから0個の要素を取ることは[]です。

次のようになります。

myTake _ [] = []
myTake 0 _ = []

ゴールではない唯一のケースは、nが0よりも大きく、リストが空ではない場合です。length関数では、リストを分解することだけを気にしなければなりませんでしたが、myTakeではリストを返すことになります。新しいリストは何から作られるのでしょうか？take 3 [1,2,3,4,5]で考えてみましょう。

１．最初の要素、1を求め、それをtake 2 [2,3,4,5]と組み合わせます。
２．次に、次の要素2を求め、それをtake 1 [3,4,5]と連立させる。
３．次に、３を求め、それをtake０ [4,5] と合わせます。
４．0でゴールに達したので、[]を返します。
５．これは1:2:3:[]につながり、[1,2,3]になります。

コードでは、以下のような処理になります。

myTake n (x:xs) = x:rest
where rest = myTake (n - 1) xs

最後に、「再帰的呼び出しはゴールに近づけるか」という質問をします。この場合、両方ともイエスです。nを減らすことは最終的に0につながり、リストの末尾を取ることは最終的に[]につながります。

myTake _ [] = []
myTake 0 _ = []
myTake n (x:xs) = x:rest
where rest = myTake (n - 1) xs

8.2.3. cycleの実装

cycle関数は、リスト関数の中でも最も実装しやすい関数であり、Haskell以外のほとんどの言語で書ける関数でもあります。

cycle関数では、リストを受け取り、それを永遠に繰り返します。これが可能なのは、Haskell以外の言語にはほとんどない遅延評価があるからです。さらに興味深いのは、cycleにはゴール状態がないことです。ありがたいことに、Haskellでもゴール状態を持たない再帰はかなり珍しい。とはいえ、この例を理解していれば、再帰と遅延評価の両方をしっかりと理解することができます。

もう一度、リストを作ってみます。まず、リストの非無限バージョンを作成します。基本的な動作は、最初の要素を最後にして、正確なリストを返すことです。

finiteCycle (first:rest) = first:rest ++ [first]

finiteCycle関数は実際には循環しません。これを循環させるには、残りの部分:[first]セクションのために循環の動作を繰り返す必要があります。

myCycle (first:rest) = first:myCycle (rest++[first])

再帰問題を解決するための鍵は、時間をかけて、目標に向かって作業し、プロセスを通して推論することです。再帰問題の利点は、その解決策が数行のコードで済むことが多いことです。また、練習することで、再帰問題には数パターンしかないことがわかるようになります。

8.3. 病態学的回帰：アッケルマン機能とコラッツ概念

この節では、再帰のための 5 つの規則の限界を示す数学の 2 つの興味深い関数を見てみましょう。

8.3.1. アッカーマン関数

Ackermann関数はmとnの2つの引数をとります。関数の数学的定義を参照するときは、スペースを節約するためにA(m, n)を使います。アッカーマン関数は以下の3つのルールに従います。

１．m = 0の場合、n + 1を返す。
２．n = 0ならば，A(m – 1, 1)を返す．
３．m != 0 と n != 0 の両方が 0 ならば，A(m -1, A(m, n -1)) となります．

このルールを使ってHaskellで実装する方法を見てみましょう。まず、m が 0 のときにゴール状態が発生し、ゴール状態になったら n + 1 を返します。パターンマッチングを使えば、これは簡単に実装できます（ルール1と2）。

ackermann 0 n = n + 1

これで、選択肢は2つだけになりました：nは0にすることができ、mとnは両方とも0ではありません。この関数の定義は，このような場合にどうすればよいかを示しています（ルール3と4）．

ackermann m 0 = ackermann (m-1) 1
ackermann m n = ackermann (m-1) (ackermann m (n-1))

最後に、この2つの代替案（ルール5）で、あなたはゴールに向かって進んでいますか？n = 0の場合、そうです。mを減らし続ければ、最終的にはm = 0になるからです。ackermannへの呼び出しが2回あるにもかかわらず、最初の呼び出しのmは0に向かって減少しており、2回目の呼び出しのnも0に向かって減少しています。

コードを実行するまでは、すべてが完璧です。この関数をGHCiにロードして、今度は :set +s を使って関数の呼び出しのタイミングを調整します。

GHCi> :set +s
GHCi> ackermann 3 3
61
(0.01 secs)
GHCi> ackermann 3 8
2045
(3.15 secs)
GHCi> ackermann 3 9
4093
(12.97 secs)

再帰的な呼び出しは、それ自身に対して入れ子になった呼び出しを行っているため、実行時のコストはすぐに爆発し始めます。再帰のルールに従っていたにもかかわらず、Ackermann 関数で深刻なトラブルに巻き込まれてしまいます。

8.3.2. コラッツ推論

コラッツ推論は数学の中でも特に魅力的な問題である．コラッツ推論は，開始数nを与えられた再帰的過程を定義することを含む．

nが1であれば終了です．
nが偶数ならば、n/2と繰り返す。
n が奇数の場合、n × 3 + 1 を繰り返します。

この処理を実装した関数 collatz を書いてみます。唯一の問題は、collatz は常に 1 を返すということです。ちょっとした工夫として、1 に到達するまでの時間を記録しておきます。例えば collatz 5 の場合、次のようになります。

5 -> 16 -> 8 -> 4 -> 2 -> 1

この場合、コラッツ5が6になると予想します。

さて、コードを書いてみます。まず、ゴール（ルール1）を設定します。これは単純にnが1の場合です。ゴール（ルール2）に到達したら、これを1段階と見なしているので、1を返したいと思うでしょう。パターンマッチングを使えば、このステップを簡単に記述することができます。

collatz 1 = 1

次に、選択肢をリストアップしなければなりません（ルール3）。

この場合、2つの選択肢があります：nが1ではなく偶数の場合、またはnが1ではなく奇数の場合です。比較をしているので、計算が必要なので、これらの両方のケースでパターンマッチングを使うことはできません。

collatz n = if even n
then ....
else ...

これでほぼ完成です。次のステップは、代替ケースで何が起こるかを記述することです(ルール4)。自分のパスの長さを記録しておくことも忘れないでください。これは、次の collatz への呼び出しに 1 を追加しなければならないことを意味します。

collatz 1 = 1
collatz n = if even n
then 1 + collatz (n `div` 2)
else 1 + collatz (n*3 + 1)

そして、関数は完成です。

GHCi>collatz 9
20
GHCi＞collatz 999
50
GHCi＞collatz 92
18
GHCi＞collatz 91
93
GHCi> map collatz [100 ... 120]
[26,26,26,88,13,39,13,101,114,114,114,70,21,13,34,34,21,21,34,34,21]

しかし、代替状態のそれぞれの再帰がゴールに近づくことを確認するのを忘れています(ルール5)。

最初の代替状態、n が偶数の場合は問題ありません。nが偶数の場合、半分に割っていることになります。しかし，n × 3 + 1 の奇数の場合は，近づいているようには見えません．このように奇数を増やす方法と偶数を減らす方法を組み合わせると，常に1になる可能性があります．残念ながらあなたには分からない誰も知らないんだ！コラッツ推論は、あなたのコラッツ関数が常に終了するという仮定ですが、これが本当であるという証明はありません。

このコラッツ関数はルールに違反しています。