3

Haskellでいくつかの基本的な原始再帰関数を定義しようとしています。times関数が何度も繰り返されるのはなぜですか（つまりeval times[x,y]、結果として(x+1)*y）？私の問題は、一般的に、合成関数がどのように機能するかについての理解が不十分なためだと思います。私の理解を明確にするために、説明なしで答えないでください。

 import Prelude hiding (pred,and,or,not)

 data PR = Z
         | S
         | P Int
         | C PR [PR]
         | PR PR PR
         deriving Show
 eval :: PR -> [Integer] - Integer
 eval Z _ = 0
 eval S [x] = x+1
 eval (P n) xs = nth n xs
 eval (C f gs) xs = eval f (map (\g -> eval g xs) gs)
 eval (PR g h) (0:xs) = eval g xs
 eval (PR g h) (x:xs) = eval h ((x-1) : eval (PR g h) ((x-1):xs) : xs)

 nth _ [] = error "nth nil"
 nth 0 _ = error "nth index"
 nth 1 (x:_) = x
 nth (n) (_:xs) = nth (n-1) xs

 one = C S [Z]
 plus = PR (P 1) (C S [P 2])
 times = PR (P 1) (C plus [P 2, P 3])

私はtimes最も近い存在のために他のいくつかのことを試みましたtimes = PR (P 1) (C plus[P 2, P 2]が、これは2x*y私が「まあ、それらP 2の1つを置き換えるだけでZ、それは次のようになる」と思っx*yたのです。これは実際にそれを恒等関数にします。y理由を考えてください。

4

2 に答える 2

3

この時間の定義は機能しているようです。

times' = PR Z (C plus [P 2, P 3])

*Main> eval times' [6,7]
42

1ではなく0*x = 0なので、これは理にかなっています。

eval (C ...)コンパイルするには、の定義を変更する必要があることに注意してください。

eval (C f gs) cs = eval f (map (\g -> eval g cs) gs)

より詳細な説明...

私たちはそれがいくつかtimesの形になることを知っています。PR Z hh

展開しましょうeval (PR Z h) (x+1:y:ys)...

eval (PR z h) (x+1:y:ys)
    = eval h ((x+1-1) : eval (PR g h) ((x+1-1):y:ys) : y : ys)
    = eval h (x : eval (PR Z h) (x:y:ys) : y : ys)
    = eval h (x : x*y : y : ys)

誘導によって私たちは知っているからeval (PR z h) (x:y:ys) = x*yです。

では、取得するには何がh必要(x+1)*y = y+x*yですか？y（これはP 3）とx*y（これは）を追加する必要があるため、次P 2のように定義する必要がありますh。

h = C plus [P 2, P 3]

P 1の代わりにを使用するZ場合、基本ケースはそうではyありません0：

eval (PR (P 1) ...) (0:y) = eval (P 1) (y) = y

再帰は同じままなのでy、答えはわかりません。

于 2012-11-25T01:14:52.933 に答える
3

opの形式であるとしますPR something (C otherThing projections)。次にx > 0、

eval op [x,y]

呼び出し

eval (C otherThing projections) [x-1, (x-1) `op` y, y]

これotherThingは、上位の操作opを構成する操作です。(x-1) `op` yそして、より単純なケースでは、再帰呼び出しとの結果に対してのみそれを呼び出したいyので、プロジェクションは引数リストの2番目と3番目の要素を選択する必要があります。

したがって、

times = PR something (C plus [P 2, P 3])

再帰方程式があるので

x*y = (x-1)*y + y

孤立したものは含まれませんx-1。

これで、基本ケースx == 0に達すると、再帰呼び出しは基本結果を返す必要があります。乗算の場合、それはもちろん0です。したがって、somethingはZ、に依存yせず、ではありませyんP 1。

したがって、user5402が言ったように、

times = PR Z (C plus [P 2, P 3])
于 2012-11-25T01:55:11.010 に答える