Converting a simple recursive haskell function to be tail recursive

Question

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?

Answer 1

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.