6
Il seguente programma soffia stack:Perché l'ottimizzazione della coda non viene utilizzata in questo programma 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)
FAIL con
Stack spazio overflow: dimensione corrente 8388608 byte. Usa `+ RTS -Ksize -RTS 'per aumentarlo.
Tuttavia, per quanto mi risulta, la possibile chiamata ricorsiva al __find_first_occurrence è l'ultima cosa valutate dalla __find_first_occurrence, quindi l'ottimizzazione chiamata coda dovrebbe essere possibile fare.
TCO non è tutto ciò che è utile in Haskell. Solitamente la pigrizia si prende cura di te, quindi raramente ne hai bisogno. In questo caso, penso che il problema sia un enorme thunk non elaborato su "i". Prova a forzare 'i' prima di effettuare una chiamata ricorsiva. – Vitus
Mi chiedevo la definizione della prima corrispondenza del pattern in __find_first_occurrence, ovvero '__find_first_occurrence e l i ='. È possibile che il problema non si riduca in quella espressione? (A proposito, se stai cercando la prima occorrenza di qualcosa in una lista, c'è una funzione incorporata in Data.List: http://hackage.haskell.org/packages/archive/base/latest/doc/html /Data-List.html#v:elemIndex, ma suppongo che non sia il punto della domanda :)) – Christoffer
@Christoffer: Quel caso non dovrebbe esserci affatto. Oh, ho appena controllato e infatti, 'i \' seq \ '__find_first_occurrence e xs (i + 1)' lo risolve. – Vitus