1

I want to know if this represents a tail-recursion. And if it isn't how can I do it.

 countP :: [a] -> (a->Bool) -> Int
 countP [] _ = 0
 countP (x:xs) p = countP_aux (x:xs) p 0

 countP_aux [] _ _ = 0
 countP_aux (x:xs) p acumul
                        |p x==True = (countP_aux xs p (acumul))+1
                        |otherwise = (countP_aux xs p (acumul))

  countP [1,2,3] (>0)
  3
  (72 reductions, 95 cells)

This exercise show how many values in a list are verified by p condition. Thanks

tomss
  • 111
  • 1
  • 6
  • I'm having trouble with double-negations - "if it isn't a non-tail recursion" means what? BTW. I would think that "countP [] f" should always return 0. Your code fails instead. – Chris Jan 16 '13 at 11:18
  • I want to know if it represents a tail-recursion. Post edited – tomss Jan 16 '13 at 11:28
  • Why does it matter if it's a tail recursion? – Waleed Khan Jan 16 '13 at 11:33
  • Tail recursion has a better performance than non-tail recursion – tomss Jan 16 '13 at 11:36
  • 4
    @tomss Not in the presence of lazy evaluation. (Tail recursion is faster in strict languages, but Haskell is non-strict.) You should read [this question about tail recursive optimization](http://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization). – AndrewC Jan 16 '13 at 12:45
  • (p x) == True, in your guard should be simplified by (p x) – zurgl Jan 17 '13 at 03:46

1 Answers1

4

This is not tail recursive because of

(countP_aux xs p (acumul))+1

Tail calls should return the result of the recursive call, rather than doing calculation with the result of the recursive call.

You can convert a non-tail recursive function to be tail-recursive by using an accumulator where you perform the additional work, i.e.

Say you have a simple counting function

f a
  | a < 1 = 0 
  | otherwise = f (a-1) + 1

You can make it tail recursive like so:

f' acc a = 
  | a < 1 = acc 
  | otherwise = f' (acc + 1) (a-1)
f = f' 0
yiding
  • 3,482
  • 18
  • 17