CODEWITHSUNDEEP
haskellrecursion
keepitreal
keepitreal

Reputation: 45

Haskell - Writing foldr recursively

I am trying to write the library function foldr using recursion. However, I am getting syntax errors and not sure about the functional correctness. This is my code:

foldr :: (a -> b) -> [a] -> [b]
foldr f [] = []
foldr f xs = foldr f (init xs) : f (last xs)

I would appreciate it if I can get some help on this

Upvotes: 0

Views: 179

Answers (1)

Louis Wasserman
Louis Wasserman

Reputation: 198471

That is not the type of the foldr function. That is the type of the map function.

But that said, : concatenates one element to the front of a list. The way you are using it attempts to concatenate one element to the end of a list, which does not work.

The closest thing to what you mean -- which is still O(n^2) and deeply inefficient -- is to replace the last line with 

foldr f xs = foldr f (init xs) ++ [f (last xs)]

Upvotes: 3

Related Questions