6
El siguiente programa sopla la pila:¿Por qué no se usa la optimización de llamadas finales en este programa 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)
error con
desbordamiento de pila espacio: tamaño actual 8388608 bytes. Use `+ RTS -Ksize -RTS 'para aumentarlo.
Sin embargo, por lo que yo entiendo, la posible llamada recursiva a __find_first_occurrence es lo último evaluadas por __find_first_occurrence, por lo tanto, la optimización de llamada de cola debe ser posible hacerlo.
TCO no es tan útil en Haskell. La pereza generalmente se ocupa de eso, por lo que rara vez lo necesita. En este caso, creo que el problema es un gran golpe no acelerado en 'i'. Intenta forzar 'i' antes de hacer una llamada recursiva. – Vitus
Me preguntaba sobre la definición de la primera coincidencia de patrón en __find_first_occurrence, es decir, '__find_first_occurrence e l i ='. ¿Es posible que el problema no se reduzca en esa expresión? (Por cierto, si está buscando la primera aparición de algo en una lista, hay una función incorporada en Data.List: http://hackage.haskell.org/packages/archive/base/latest/doc/html /Data-List.html#v:elemIndex, pero supongo que ese no es el punto de la pregunta :)) – Christoffer
@Christoffer: Ese caso no debería estar allí para nada. Oh, acabo de verificar y, de hecho, 'i \' seq \ '__find_first_occurrence e xs (i + 1)' lo resuelve. – Vitus