haskell - Haskell の再帰を理解する

Question

問題を再帰的に考え、Haskell を使用して問題を解決する方法を理解するのに非常に苦労しています。私は、再帰について頭を悩ませようとして、何時間も読んでいます。それを理解している人から私がよく受ける説明は決して明確ではなく、「関数を引数として関数の名前を渡すと、関数が実行され、問題の小さな部分を解決し、基本ケースに到達するまで何度でも機能します。」

誰か親切にして、これら 3 つの単純な再帰関数の思考プロセスを説明してもらえますか? それらの機能ではなく、コードがどのように再帰的に実行され、問題を解決するかです。

よろしくお願いします！

機能 1

maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:rest) = max x(maximum' rest)

機能 2

take' n _  
    | n <= 0   = []  
take' _ []     = []  
take' n (x:xs) = x : take' (n-1) xs  

機能 3

reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]  

Answer 1

ガイドライン

再帰を理解しようとするとき、特定の入力に対してアルゴリズムがどのように動作するかを考えた方が簡単な場合があります。実行パスがどのように見えるかということに夢中になりやすいので、代わりに次のような質問を自問してみてください。

• 空のリストを渡すとどうなりますか?
• 項目が 1 つのリストを渡すとどうなりますか?
• 多くのアイテムを含むリストを渡すとどうなりますか?

または、数値の再帰の場合:

• 負の数を渡すとどうなりますか?
• 0 を渡すとどうなりますか?
• 0 より大きい数値を渡すとどうなりますか?

再帰アルゴリズムの構造は、多くの場合、上記のケースをカバーするだけの問題です。それでは、アルゴリズムがどのように動作するかを見て、このアプローチの感触をつかみましょう。

最大'

maximum []     = error
maximum [1]    = 1
maximum [1, 2] = 2

ご覧のとおり、興味深い動作は #3 だけです。他のものは、アルゴリズムが終了することを保証するだけです。定義を見ると、

maximum' (x:rest) = max x (maximum' rest)

これを呼び出すと、次のように[1, 2]展開されます。

maximum [1, 2]    ~ max 1 (maximum' [2])
                  ~ max 1 2

maximum'この場合、 を使用して再帰的に処理する方法を知っていますmax。もう 1 つのケースを見てみましょう。

maximum [0, 1, 2] ~ max 0 (maximum' [1, 2]) 
                  ~ max 0 (max 1 2)
                  ~ max 0 2

この入力の場合、maximum'最初の行の への再帰呼び出しが前の例とまったく同じであることがわかります。

逆行する'

reverse []     = []
reverse [1]    = [1]
reverse [1, 2] = [2, 1]

リバースは、指定されたリストの先頭を取得して最後に貼り付けることで機能します。空のリストの場合、これには作業が含まれないため、これが基本ケースです。したがって、次の定義が与えられます。

reverse' (x:xs) = reverse' xs ++ [x] 

代用をしましょう。[x]がと同等であることを考えるとx:[]、実際には 2 つの値を処理する必要があることがわかります。

reverse' [1]    ~ reverse' [] ++ 1
                ~ []          ++ 1
                ~ [1]

簡単です。2 要素リストの場合:

reverse' [0, 1] ~ reverse' [1] ++ 0
                ~ [] ++ [1] ++ 0
                ~ [1, 0]

取った'

この関数は、リストだけでなく整数引数にも再帰を導入するため、2 つの基本ケースがあります。

1. 0以下のアイテムを取るとどうなりますか? 項目を取得する必要はないので、空のリストを返すだけです。

   take' n _   | n <= 0    = [] 
   
   take' -1 [1]  = []
   take' 0  [1]  = []
   

2. 空のリストを渡すとどうなりますか? 取るアイテムがなくなったので、再帰を停止します。

   take' _ []    = []
   
   take' 1 []    = []
   take  -1 []   = []
   

アルゴリズムの本質は、実際にはリストをたどり、入力リストを引き離し、上記の基本ケースのいずれかがプロセスを停止するまで、取得するアイテムの数を減らすことです。

take' n (x:xs) = x : take' (n-1) xs

したがって、数値ベースのケースが最初に満たされた場合、リストの最後に到達する前に停止します。

take' 1 [9, 8]  ~ 9 : take (1-1) [8]
                ~ 9 : take 0     [8]
                ~ 9 : []
                ~ [9]

リストの基本ケースが最初に満たされた場合、カウンターが 0 に達する前にアイテムを使い果たし、可能なものだけを返します。

take' 3 [9, 8]  ~ 9 : take (3-1) [8]
                ~ 9 : take 2     [8]
                ~ 9 : 8 : take 1 []
                ~ 9 : 8 : []
                ~ [9, 8]

Answer 2

再帰は、特定の関数をセットに適用する戦略です。そのセットの最初の要素に関数を適用してから、残りの要素に対してこのプロセスを繰り返します。

例を見てみましょう。リスト内のすべての整数を 2 倍にしたいとします。まず、どの関数を使用するかを考えますか? 答え -> 2*、この関数を再帰的に適用する必要があります。それを と呼びましょうapply_rec。

apply_rec (x:xs) = (2*x)

ただし、これは最初の要素のみを変更するため、セットのすべての要素を変更する必要があります。apply_recしたがって、残りの要素にもを適用する必要があります。したがって：

apply_rec (x:xs) = (2*x) : (apply_rec xs)

今、あなたは別の問題を抱えています。いつapply_rec終わりますか？リストの最後に到達すると終了します。つまり[]、このケースもカバーする必要があります。

apply_rec [] = []
apply_rec (x:xs) = (2*x) : (apply_rec xs)

最後に到達すると、関数を適用したくないため、関数apply_recは「戻る」必要があり[]ます。

set = でのこの関数の動作を見てみましょう[1,2,3]。

1. apply_rec [1,2,3] = (2 * 1) : (apply_rec [2,3])
2. apply_rec [2,3] = 2 : ((2 * 2) : (apply_rec [3]))
3. apply_rec [3] = 2 : (4 : ((2 * 3) : (apply_rec []))
4. apply_rec [] = 2 : (4 : (6 : [])))

になり[2,4,6]ます。

あなたはおそらく再帰をよく知らないので、あなたが提示した例よりも簡単な例から始めるのが最善の方法です. 再帰の学習と、このHaskell Tutorial 3-recursionもご覧ください。

Answer 3

おそらくコンピューターではなくプログラマーの「思考プロセス」について質問しますよね？だからここに私の2セントがあります：

g再帰を使用して関数を記述することについて考える方法は、その関数を既に記述していると想像してください。それで全部です。

これは、必要なときにいつでも使用できることを意味し、実行すべきことは何でも「実行します」。それで、それが何であるかを書き留めてください-それが従わなければならない法律を策定し、それについて知っていることを何でも書き留めてください. それについて何か言ってください。

さて、言うだけg x = g xでは何も言いません。もちろんそれは真実ですが、意味のないトートロジーです。g x = g (x+2)それはもはやトートロジーではないと言うなら、とにかく無意味です。もっと賢明なことを言う必要があります。例えば、

g :: Integer -> Bool
g x | x<=0 = False
g 1 = True
g 2 = True

ここで何か言いました。また、

g x = x == y+z  where
          y = head [y | y<-[x-1,x-2..], g y]    -- biggest y<x that g y
          z = head [z | z<-[y-1,y-2..], g z]    -- biggest z<y that g z

言わなければならないことはすべて言いましたxか？私たちがしたかどうかにかかわらず、私たちはあり得ることについてそれを言いました x. これで再帰的な定義は終了です。すべての可能性が尽きるとすぐに、完了です。

しかし、終了はどうですか？関数からなんらかの結果を取得し、その作業を終了させたいと考えています。つまり、これを使用して を計算する場合、 「前に」定義されたもの、つまり定義された最も単純なケースの 1 つに「近い」ものを再帰的に使用するx必要があります。y x

そしてここで、私たちはそうしました。今、私たちは手仕事に驚くことができます。

filter g [0..]

最後に、定義を理解するために、その手順をたどろうとしないでください。方程式自体を読むだけです。上記の の定義が提示された場合、次のようgに単純に読むことができます:gは、True1 と 2の数値のブール関数であり、x > 2前の 2 つの数値の合計ですg。

Answer 4

関数 3 を見ると、次のようになります。

reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x] 

あなたがリバースを呼んだとしましょう' [1,2,3] そして...

1. reverse' [1,2,3] = reverse' [2,3] ++ [1]

   reverse' [2,3] = reverse' [3] ++ [2] ... so replacing in equation 1, we get:

2. reverse' [1,2,3] = reverse' [3] ++ [2] ++ [1]

   reverse' [3] = [3] and there is no xs ...

  ** UPDATE ** There *is* an xs!  The xs of [3] is [], the empty list. 

   We can confirm that in GHCi like this:

     Prelude> let (x:xs) = [3]
     Prelude> xs
     []

   So, actually, reverse' [3] = reverse' [] ++ [3]

   Replacing in equation 2, we get:

3. reverse' [1,2,3] = reverse' [] ++ [3] ++ [2] ++ [1]

   Which brings us to the base case: reverse' [] = []
   Replacing in equation 3, we get:

4. reverse' [1,2,3] = [] ++ [3] ++ [2] ++ [1], which collapses to:

5. reverse' [1,2,3] = [3,2,1], which, hopefully, is what you intended!

たぶん、他の2つと同様のことを試みることができます。小さなパラメータを選択してください。
成功してください！

Answer 5

たぶん、あなたの問題を提示する方法は良いものではありません。これは、既存の再帰関数の実装をちりばめることによって、それを複製する方法を理解できるということではありません。別の方法を提供したいと思います。それは、再帰呼び出しの標準的なスケルトンを記述し、それらについての推論を容易にするのに役立つ方法論的なプロセスと見なすことができます。

あなたの例はすべてリストに関するものであり、リストを操作するときの最初のことは網羅的であることです.パターンマッチングを使用することを意味します.

rec_fun [] = -- something here, surely the base case
rec_fun (x:xs) = -- another thing here, surely the general case  

現在、基本ケースに再帰を含めることはできません。そうしないと、確実に無限ループになってしまいます。基本ケースは値を返す必要があります。この値を把握する最善の方法は、関数の型注釈を調べることです。

例えば ​​：

reverse :: [a] -> [a]

基本ケースをタイプ [a] の値、逆の [] と見なすことをお勧めします。

maximum :: [a] -> a 

基本ケースを最大値のタイプ a の値と見なすことをお勧めします

再帰部分については、前述のように、関数に自分自身の呼び出しを含める必要があります。

rec_fun (x:xs) = fun x rec_fun xs 

再帰呼び出しの連鎖を実現する責任を負う別の関数の使用を示すのは楽しいことです。あなたの直感を助けるために、私たちはそれを演算子として提示することができます.

rec_fun (x:xs) = x `fun` rec_fun xs 

ここで、(再び) 関数の型注釈 (またはより簡潔には基本ケース) を検討すると、この演算子の性質を推測できるはずです。逆の場合、リストを返す必要があるため、演算子は確かに連結 (++) などです。

これらすべてをまとめれば、目的の実装にたどり着くのはそれほど難しくありません。

もちろん、他のアルゴリズムと同様に、常に少し考える必要があり、魔法のレシピはありません。考える必要があります。たとえば、リストの末尾の最大値がわかっている場合、リストの最大値は?