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 beofre (also new to how foldl traverses a list which is where it came up).

For practice I tried to rewrite the following 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:

ghci session

Nothing seems to be running at all, let alone getting an overflow.

Any ideas?

CodePudding user response：

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.