为什么在这个Haskell程序中不使用尾部调用优化？ [英] Why is the tail call optimization not used in this Haskell program?

问题描述

  __ find_first_occurrence ::（等式b）=> b  - > [b]  - > Int  - > Int 
 __find_first_occurrence e [] i = -1 
 __find_first_occurrence e（x：xs）i 
 | e == x = i 
 |否则= __find_first_occurrence e xs（i + 1）
 
 find_first_occurrence ::（等式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（显示idx）
  

不符合

堆栈空间溢出：当前大小8388608字节。使用`+ RTS -Ksize
-RTS'来增加它。

然而，据我了解，可能对 __ find_first_occurrence 进行递归调用是由 __ find_first_occurrence 评估的最后一项，因此应该可以进行尾部调用优化。 / p>

解决方案

使用尾部调用优化，但（i + 1）表达式得到thunked，并在最后评估它们导致堆栈溢出。

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.

解决方案

The tail call optimization is used, but the (i+1) expressions get thunked, and evaluating them at the end causes the stack to overflow.

这篇关于为什么在这个Haskell程序中不使用尾部调用优化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！