2 weeks new to haskell and functional programming. In the process of covering foldl and foldr in class, I found that I was quite new to tail recursion and never actually tried writing a tail recursive function before (also new to how foldl traverses a list which is where it came up).
As an exercise, I tried to rewrite the following function to be tail recursive.
--replace replaces all instances of value x in a list with y
replace :: (Eq a) => a -> a -> [a] -> [a]
replace _ _ [] = []
replace x y (h:t) =
(if x==h then y: (replace x y t) else h: (replace x y t))
--tail recursive version of the same function
replacet _ _ [] = []
replacet x y (h:t) =
(if x==h then (replacet x y (y:t)) else (replacet x y (h:t)))
...But the output is just the following in ghci:
Nothing seems to be running at all, let alone getting an overflow.
Any ideas?
Your replacet
never makes any progress. Observe that at each step, your input list stays the same size: you replace (h:t)
with either (y:t)
or (h:t)
, and then call replacet
on the result.