6
Poniższy program wieje stosu:Dlaczego optymalizacja wywołania końcowego nie jest używana w tym programie Haskell?
__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)
nie powiedzie się z
przepełnienia stosu przestrzeni: aktualny rozmiar 8388608 bajtów. Użyj `+ RTS -Ksize -RTS ', aby go zwiększyć.
Jednak, o ile rozumiem, możliwy rekurencyjne wywołanie __find_first_occurrence jest ostatnią rzeczą, oceniane przez __find_first_occurrence, stąd ogon optymalizacja połączenia powinny być możliwe do zrobienia.
TCO nie jest tak przydatne w Haskell. Lenistwo zwykle to zajmuje, więc rzadko go potrzebujesz. W tym przypadku myślę, że problemem jest ogromny nieuporządkowany thunk na "i". Spróbuj wymusić 'i' przed wywołaniem rekursywnym. – Vitus
Zastanawiam się nad definicją pierwszego dopasowania wzorca w __find_first_occurrence, a mianowicie '__find_first_occurrence e l i ='. Czy to możliwe, że problem nie zmniejsza się w tym wyrażeniu? (Nawiasem mówiąc, jeśli szukasz pierwszego wystąpienia czegoś na liście, istnieje funkcja wbudowana w Data.List: http://hackage.haskell.org/packages/archive/base/latest/doc/html /Data-List.html#v:elemIndex, ale przypuszczam, że nie o to pytam :)) – Christoffer
@Christoffer: Ten przypadek nie powinien być w ogóle. Och, właśnie sprawdziłem i rzeczywiście, 'i \" seq \ '__find_first_occurrence e xs (i + 1)' rozwiązuje to. – Vitus