Pattern matching for lambda expressions

Question

 21 --Primitive recursion constructor
 22 pr :: ([Int] -> Int) -> ([Int] -> Int) -> ([Int] -> Int)
 23 pr f g = \xs 0 -> f xs
 24 pr f g = \xs (y+1) -> g xs y ((pr f g) xs y)

I want the function this function creates to act differently on different inputs, so that it can create a recursive function. As expected, the above code doesn't work. How do I do something like pattern matching, but for the function it creates?

Answer 1

pr f g = \xs y' -> case y' of 0     -> f xs
                              (y+1) -> g xs y ((pr f g) xs y)

or simply

pr f g xs 0 = f xs
pr f g xs (y+1) = g xs y ((pr f g) xs y)

(Remember that f a b = ... is basically a shortcut for f a = \b -> ... which is a shortcut for f = \a -> \b -> ....)

Note that n+1 patterns are deprecated and that the type you specified for pr does not match your (and mine) definition.

Specifically according to your type the function takes an [Int] -> Int (f), then a function that takes another [Int] -> Int (g), then a function that takes an [Int] (xs) and then returning an Int. However you call g with three arguments and the last function that you return takes two arguments, so presumably you want something like ([Int] -> Int) -> ([Int] -> Int -> Int -> Int) -> [Int] -> Int -> Int.