haskelltail-recursiontail-call-optimization# Converting a simple recursive haskell function to be tail recursive

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?

Solution

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.

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code