-2
foldr   ::  (a  ->  b   ->  b)  ->  b   ->  [a] ->  b
foldr   f   v   [] =    v
foldr   f   v   (x:xs)  =   f   x   (foldr  f   v   xs)

and

foldl   ::  (a  ->  b   ->  a)  ->  a   ->  [b] ->  a
foldl   f   v   [] =    v
foldl   f   v   (x:xs)  =   foldl   f   (f  v   x)  xs

seem to use different kinds of recursions.

What kinds of recursions are used in the definitions of foldr and foldl?

Thanks.

Tim
  • 1
  • 141
  • 372
  • 590
  • 6
    Can you describe what sort of thing you mean by a "kind of recursion"? – David Young Jul 29 '19 at 02:51
  • I think I know it: non tail and tail recursions. – Tim Jul 29 '19 at 03:02
  • 5
    It is true that one of them is tail recursive and one of them is not tail recursive. Is there a description of tail recursion that you are working from? If so, what parts of it do you understand and what parts of it do you not understand? Giving information like this helps us answer the question in a way that helps you to better understand. Try to provide a bit more information like this, when possible (especially definitions like that and what you do and don't understand about those definitions). – David Young Jul 29 '19 at 04:15
  • 1
    Relevant: [*foldl is tail recursive, so how come foldr runs faster than foldl?*](https://stackoverflow.com/q/3429634/2751851) – duplode Jul 29 '19 at 10:48

1 Answers1

3

foldl uses tail recursion.

foldr uses guarded recursion, the recursion being guarded by f's laziness (if any).

Will Ness
  • 70,110
  • 9
  • 98
  • 181