Geek Answers Handbook

Where is the space leak when using scanl? (Haskell)

Consider this piece of code:

incState state i = map (+ i) state

main =
  sequence_ $ do
    n <- map last $ scanl incState (replicate 1000000 0) (repeat 1)
    return $ print $ n

When I run it, memory usage continues to increase without restriction as it prints numbers. Where is the memory leak here? It should only support a constant amount of memory; previous values stateshould be discarded whenever it prints something.

Even if sequence_either the list monad holds values n, it is only one integer per iteration. I see 6Gs of memory used after it counts to 100. A million integers should occupy a maximum of 10M.

+4
source share
2 answers

. last sum, .

, , :

main = mapM (print . last) $ scanl incState (replicate 5 0) (repeat 1)

. ,

scanl incState (map (+1) (replicate 5 0)) (repeat 1)

, , , , mapM .

(:) -> replicate 5 0 
 |     ^
 |     |_________________                     
 v                       |
scanl incState (map (+1) | ) (repeat 1)

last print, , . .

       0 : 0 : 0 : 0 : 0 : [] 
       ^
       |_________________                     
                         |
scanl incState (map (+1) | ) (repeat 1)

mapM .

       0 : 0 : 0 : 0 : 0 : [] 
       ^
       |________                    
                |
(:) -> map (+1) |
 |     ^
 |     |_________________                     
 v                       |
scanl incState (map (+1) | ) (repeat 1)

last print, , .

       0   : 0   : 0   : 0   : 0 : [] 
       ^     ^     ^     ^
       |     |     |     |     
       |+1 : |+1 : |+1 : |+1 : 1 : []
       ^
       |_________________                     
                         |
scanl incState (map (+1) | ) (repeat 1)

mapM .

       0   : 0   : 0   : 0   : 0 : [] 
       ^     ^     ^     ^
       |     |     |     |     
       |+1 : |+1 : |+1 : |+1 : 1 : []
       ^
       |________                    
                |
(:) -> map (+1) |
 |     ^
 |     |_________________                     
 v                       |
scanl incState (map (+1) | ) (repeat 1)

last print, , .

       0   : 0   : 0   : 0   : 0 : [] 
       ^     ^     ^     ^
       |     |     |     |     
       |+1 : |+1 : |+1 : |+1 : 1 : []
       ^     ^     ^     ^
       |     |     |     |     
       |+1 : |+1 : |+1 : |+1 : 2 : []
       ^
       |_________________                     
                         |
scanl incState (map (+1) | ) (repeat 1)

, , , .. , . , , print . sum, .

+7

Cirdec, , incState state i = map (+ i) state state, . , , last ( , ).

, , seq,

mapM_ (print . foldl' seq 0) $
   scanl (\s i-> map (+ i) s) (replicate 1000000 0) (repeat 1)


map f xs = foldr (\x r-> f x : r) [] xs 
         = foldr (\x r-> let y=f x in y `seq` (y:r)) [] xs

"" map ( SO , by @luqui, IIRC):

mapM_ (print . last) $ 
  scanl (\s i-> foldr (\x r-> let y=(+i) x in y `seq` (y:r)) [] s)
        (replicate 1000000 0) (repeat 1)

, , , , ; map last scanl ... replicate ... incState (, ), mapM_ print $ scanl (+) 0 (repeat 1). ( , ).

0

More articles:


All Articles