Home > database >  converting a simple recursive haskell function to be tail recursive
converting a simple recursive haskell function to be tail recursive

Time:01-30

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.

  • Related