Primitive Recursive functions

Question

I'm trying to define some basic Primitive Recursive functions in Haskell. Why is my times function recursing one too many times (ie eval times[x,y] is resulting in (x+1)*y)? I think my problem is generally due to a poor understanding of how the Composition function works. Please don't give an answer without an explanation to clarify my understanding.

 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])

I've tried a few other things for times the closest being times = PR (P 1) (C plus[P 2, P 2] but this comes out to 2x*y I thought "Well I'll just replace one of those P 2's with Z and then it will be x*y" This actually makes it the identity function of y and I have no idea why.

Answer 1

This definition for times seems to work:

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

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

This makes sense since 0*x = 0 not 1.

Note that I had to change the definition of eval (C ...) in order for it to compile:

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

More detailed explanation...

We know that times will be of the form PR Z h for some h.

Let's expand 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)

because by induction we know eval (PR z h) (x:y:ys) = x*y.

So what does h have to be in order to get (x+1)*y = y+x*y? We need to add y (which is P 3) and x*y (which is P 2), so we should define h as:

h = C plus [P 2, P 3]

If you use P 1 instead of Z, then your base case is y and not 0:

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

The recursion stays the same, so you're off by y in your answer.

Answer 2

Suppose op is of the form PR something (C otherThing projections). Then, if x > 0,

eval op [x,y]

calls

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

The otherThing is the operation the higher-ranked op is composed from. And in the simpler cases, you want to invoke that only on the result (x-1) `op` y of the recursive call and y, so the projections should select the second and third element of the argument list.

Hence we have

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

since we have the recursive equation

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

which doesn't involve an isolated x-1.

Now, when the base case x == 0 is reached, the recursive call should return the base result. For multiplication, that is of course 0, thus the something should be Z, independent of y, and not y which P 1 would give you.

Therefore, as user5402 said, you should have

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