2

In A tutorial on universality and expressiveness of fold chapter 4.1, it states that this pattern of recursion 

h y [] = f y
h y (x:xs) = g y x xs (h y xs)

is primitive recursion, but I don't understand why the pattern 

h [] = v
h (x:xs) = g x (h xs)

is not primitive recursion according to the definition of primitive recursive.
The value of h y' is still based on h y in the h (x:xs) = g x (h xs) if we let y = xs and y' = x:xs.

Improve this question
5
  • 3
    Where does chapter 4.1 say that your second example is not primitive recursive? It starts with your second example and then just generalizes it somewhat (by adding the extra y parameter) to get your first version. But I see no claim that only your first one uses primitive recursion. Commented Nov 11, 2015 at 8:46
  • @Cactus This pattern of recursion on lists is called primitive recursion (Kleene, 1952). I think I misunderstand what it means. Thanks! Commented Nov 11, 2015 at 8:53
  • 3
    Yes, but that is not to be taken to mean that only your first example is called primitive recursion, in contrast to your second example (also, it's confusing to refer to your examples because you flipped their order compared to the tutorial...) Commented Nov 11, 2015 at 8:55
  • @Cactus The tutorial says "We will generalise this pattern of recursion to primitive recursion". This kind of implies that the original pattern is not primitive recursion. Commented Nov 11, 2015 at 9:02
  • Another question is why is that a generalise form ? Commented Nov 11, 2015 at 9:07

1 Answer 1

Reset to default
2

The primitive recursion scheme is parametric on the choice of f,g

h y [] = f y
h y (x:xs) = g y x xs (h y xs)

That is, we are free to choose f,g as we want, and h will be defined through primitive recursion.

In particular, we can choose 

f = \y -> v
g = \y x xs -> g' x z

where g' is any other function picked by us. We then get

h y [] = v
h y (x:xs) = g' x (h y xs)

Now, if we let

h' xs = h () xs

we fix the y argument to an immaterial value so to recover the function in the question. Pedantically, h' is not obtained directly as an instance of the general form, so h' is technically not defined through the primitive recursion scheme seen above (i.e., it is not an instance of that). Sometimes, instead of y we find there many variables y1 .. yn allowing us to pick n=0 and remove the y as we want in this case.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Well, you compare the general scheme and the desired goal and try to instantiate the parameters so that they match. A bit of trial and error may be needed.
According to primitive recursive definition, I think the general scheme should be h y (x:xs) = g y xs (h y xs) , but why in A tutorial on the universality and expressiveness of fold defines it as h y (x:xs) = g y x xs (h y xs) ?
@Sid The first definition of primitive recursion only considers natural numbers as arguments. When dealing with lists, it has to be extended. If we extend it as you propose, then h y (x:xs) can not depend on x, which is very restrictive: we can't access any of the list elements!

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.