Утечка пространства с рекурсивным списком zipWith

Question

Утечка пространства происходит в одном из моих личных проектов. Но я не хочу, чтобы кто-то решал это в моем проекте. Я хочу это понять.

Я воспроизведен мое место утечки, делая этот алгоритм:

U представляет собой последовательность определяется по формуле:

• и (0) = 1
• и (1) = 2
• и (2) = 1
• и (4) = 3
• ...
• и (19) = 11

после этого, и определена: и (п) = и (п-5) + и (п-10) - и (п-15)

Легко реализовать в Haskell правильно?

import System.Environment (getArgs) 

u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11] 
     ++ zipWith3 go u' u'' u''' 
    where u' = drop 15 u 
      u'' = drop 10 u 
      u''' = drop 5 u 
      go a b c = a + b - c 

main = do 
    args <- getArgs 
    let n = read $ args !! 0 
    putStrLn $ show $ u !! n 

К сожалению, это пространство утечки:

$ time ./algo 9999999 
Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 
1.17user 0.19system 0:01.37elapsed 100%CPU (0avgtext+0avgdata 865124maxresident)k 
0inputs+0outputs (0major+215695minor)pagefaults 0swaps 

Похоже Haskell кэширование весь список, в котором, как я хочу, чтобы кэшировать только 20 последних элементов.

Например, вот моя реализация в C:

#include <stdint.h> 
#include <stdio.h> 

int main(int argc, char **argv) 
{ 
    size_t cursor; 
    int64_t buffer[20] = {1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11}; 
    int n = atoi(argv[1]); 

    for (cursor = 20; cursor <= n; cursor++) { 
     buffer[cursor%20] = buffer[(cursor+20-5)%20] + buffer[(cursor+20-10)%20] - buffer[(cursor+20-15)%20]; 
    } 

    printf("%d\n", buffer[n%20]); 
    return 0; 

} 

$ ./a.out 9999999 
5000001 

Моя реализация C использует O (N) времени и O (1) пространство. Но похоже, что реализация haskell использует O (n) пространство.

Почему Haskell способен вычислить его для fibonnacci, но не для моей составленной последовательности? Что я сделал не так? Как реализовать этот алгоритм в Haskell?

Answer 1

Ну, это переполнение стека, но у вас также есть утечка пространства, что проще объяснить в нескольких словах.

При выполнении индексации u !! n, u выглядит

1 : 2 : 1 : ... : 11 : <go thunk> : ... : <go thunk> : <zipWith3 thunk> 

и извлекать последнюю <go thunk>, один с индексом n в списке u. На этом этапе каждый <go thunk> имеет ссылки на более ранние элементы u, поэтому (почти) целое число u должно сохраняться в памяти (первые пять или около того элементов на самом деле не нужны).

Переполнение стека заключается в том, что для оценки элемента 9999999th u вы сначала должны оценить элемент 9999994th, и для того, чтобы оценить, что вам сначала нужно оценить элемент 9999989th и т. Д. Что делать после, скажем, оценка 9999994-го элемента для того, чтобы закончить оценку 9999999-го элемента, идет в стек, и есть ваш переполнение стека (что также является своего рода утечкой пространства, я полагаю).

Обе эти проблемы могут быть решены путем форсирования элементов списка u либо по мере его создания, либо при его перемещении. Поскольку вы сказали, что не хотите, чтобы кто-то решал проблему утечки пространства, я оставлю эту часть упражнением, хотя есть особенно гладкий и, вероятно, неочевидный способ сделать это.

---

Edited добавить: Пятно, но, возможно, слишком умный затруднительное я имел в виду, просто изменить последнюю строку

putStrLn $ show $ foldr ((:) $!) [] u !! n 

Вероятно, понимание того, как это работает достаточное упражнение само по себе.

Более простой подход заключается в ответе макс талдыкина или написании пользовательской функции индексирования, которая заставляет элементы, которые он пропускает, прежде чем их отбрасывать.

Answer 2

Вот код, который следует ответ Рейд Бартона:

{-# LANGUAGE BangPatterns #-} 
import System.Environment (getArgs) 

u :: [Int] 
u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11] 
     ++ go u' u'' u''' 
    where u' = drop 15 u 
      u'' = drop 10 u 
      u''' = drop 5 u 
      go ((!a):as) ((!b):bs) ((!c):cs) 
      = a + b - c 
      : go as bs cs 

Он использует BangPatterns расширение, чтобы заставить оценку санков. (Я также добавил аннотацию типа использовать Int с вместо Integer с, что немного быстрее.)

Вы можете видеть, что он работает в постоянном пространстве (1M in use является соответствующая часть продукции):

$ ./xx 99999999 +RTS -t 
50000001 
<<ghc: 8000065016 bytes, 15319 GCs, 36596/44312 avg/max bytes residency (2 samples), 1M in use, 0.00 INIT (0.00 elapsed), 2.82 MUT (2.78 elapsed), 0.01 GC (0.06 elapsed) :ghc>>