Why does putStrLn slow down with each iteration?

Question

I have made a small Game of Life program which iterates through generations by itself. The issue is that with each iteration, the putStrLn function slows down considerably, and I'm not able to figure out why. Here is the code:

import Control.Concurrent

data CellState = Dead | Alive

data Position = Position Integer Integer

type Generation = Position -> CellState

is_alive :: CellState -> Bool
is_alive Alive = True
is_alive Dead = False

neighbors :: Position -> [Position]
neighbors (Position x y) =
  [(Position (x-1) (y-1)), (Position x (y-1)),  (Position (x+1) (y-1)), (Position (x+1) y),
  (Position (x+1) (y+1)), (Position x (y+1)), (Position (x-1) (y+1)), (Position (x-1) y)]

alive_neighbors :: Generation -> Position -> Int
alive_neighbors generation position = length (filter is_alive (map generation (neighbors position)))

evolution :: Generation -> Generation
evolution generation position =
  case (alive_neighbors generation position) of
  2 -> if (is_alive (generation position)) then Alive else Dead
  3 -> Alive
  _ -> Dead

visualize_generation generation = map (visualize_line generation) [1..10]

visualize_line :: Generation -> Integer -> String
visualize_line generation y = concat (map (visualize_cell generation y) [1..10])

visualize_cell generation y x =
  case (generation (Position x y)) of
  Alive -> ['0']
  Dead -> ['.']

{-
bar (Position 1 2) = Alive
bar (Position 2 3) = Alive
bar (Position 3 3) = Alive
bar (Position 3 2) = Alive
bar (Position 3 1) = Alive
bar (Position x y) = Dead
-}

bar (Position 1 3) = Alive
bar (Position 2 3) = Alive
bar (Position 3 3) = Alive
bar (Position x y) = Dead

life :: Generation -> IO ()
life bar_ = do cls
               mapM_ putStrLn (visualize_generation bar_)
               threadDelay 1000000 
               life (evolution bar_)

cls = putStr "\ESC[2J"

I initially expected that each new generation for some reason calculated all the previous generations as well, but it doesn't seem to be the case. I would expect the computation time of the evolution function to increase if that was the case, not the putStrLn function to print slowly. Any ideas as to what can be slowing the putStrLn function down so much for each generation?

Answer 1

(Disclaimer: this is only a guess, and I might be wrong. I did not run experiments to confirm this.)

This is the price to pay to represent the grid as you do, using a function

type Generation = Position -> CellState

This is an elegant way to represent the state, but it's not very efficient in the long run. When your algorithm runs, it creates a lot of closures:

generation0 = \position -> ....
generation1 = \position -> .... use generation0
generation2 = \position -> .... use generation1
generation3 = \position -> .... use generation2
...

Even if you only need the last generation, the data for all the previous generation is still kept in memory because it is used (indirectly) by the last generation. Hence, you never free memory, which is already bad.

Worse, every time you use generation N, this will call generation N-1 multiple times (8), which in turn will call generation N-2 multiple times (8), and so on until generation 0. This causes an exponential blow up.

To fix this, you need to change your data representation to something more efficient. Some matrix-like type could work, I think.