Menu
The following program blows the stack:
__find_first_occurrence :: (Eq b) => b -> [b] -> Int -> Int
__find_first_occurrence e [] i = -1
__find_first_occurrence e (x:xs) i
| e == x = i
| otherwise = __find_first_occurrence e xs (i + 1)
find_first_occurrence :: (Eq a) => a -> [a] -> Int
find_first_occurrence elem list =
__find_first_occurrence elem list 0
main = do
let n = 1000000
let idx = find_first_occurrence n [1..n]
putStrLn (show idx)
Fails with
Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it.
However, as far as I understand it, the possible recursive call to __find_first_occurrence is the last thing evaluated by __find_first_occurrence, hence tail call optimization should be possible to do.
905
Note that foldl is tail recursive. The important concept to know in Haskell is guarded recursion (see tail recursion modulo cons), where any recursive calls occur within a data constructor (such as foldr , where the recursive call to foldr occurs as an argument to (:) ).
This kind of function call is called a tail call, and languages like Haskell, Scala, and Scheme can avoid keeping around unnecessary stack frames in such calls. This is called tail call optimization (TCO) or tail call elimitation.
Tail call optimization is the specific use of tail calls in a function or subroutine that eliminate the need for additional stack frames. Tail call optimization can be part of efficient programming and the use of the values that subroutines return to a program to achieve more agile results or use fewer resources.
No. Go for readability. Many computations are better expressed as recursive (tail or otherwise) functions. The only other reason to avoid them would be if your compiler does not do tail call optimizations and you expect you might blow the call stack.
The tail call optimization is used, but the (i+1) expressions get thunked, and evaluating them at the end causes the stack to overflow.
188
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
