Применение seq для улучшения времени выполнения в Haskell

Question

У меня есть следующее:

data Node = Node { position::Int
                 , zombies::Float
                 , connections::[Int]
                 }

moveZombie :: [Node] -> Node -> Node
moveZombie nodes (Node i _ cx) = zc `seq` Node i zc cx
  where zc = sum [zombies n / (fromIntegral $ length $ connections n) | i <- cx, let n = nodes !! i]

step :: Int -> [Node] -> [Node]
step 0 nodes = nodes
step k nodes = step (k-1) $ map (moveZombie nodes) nodes

Компиляция с включенным профилированием в GHC говорит мне, что центры затрат:

                               Individual
COST CENTRE            MODULE %time %alloc
moveZombie.zc          Main   60.3   90.4
moveZombie.zc.n        Main   37.6    0.0

Я попробовал следующее: moveZombie nodes (Node i _ cx) = zc `seq` Node i zc cx чтобы добиться строгой оценки и заставить программу работать быстрее, но безуспешно. Я знаю, что что-то не так с моим пониманием пути seq работает, но я не могу понять, что.

Я думаю, что мне нужно навязать строгую оценку step k nodes = step (k-1) $ map (moveZombie nodes) nodes но я в замешательстве.

Я знаю это:

1. seq a b сил a в слабую первую нормальную форму, при оценке b
2. Что выражение находится в слабой нормальной форме, если самое внешнее выражение является лямбда или конструктором данных

Есть ли какие-то указатели на то, чего я не понимаю?

Answer 1

Основной проблемой скорости является обработка "узлов" как списка - вашему алгоритму часто нужно извлекать элементы в случайных позициях, а это O(n) для каждого поиска в структуре данных связанного списка.

Замена "узлов" из [Node] на любую более подходящую структуру данных (Data.Map или Array) значительно улучшит сложность.