Сравнение производительности
Чтобы почувствовать, насколько разностные списки могут улучшить вашу производительность, рассмотрите следующую функцию. Она просто в обратном направлении считает от некоторого числа до нуля, но производит записи в журнал в обратном порядке, как функция gcdReverse, чтобы числа в журнале на самом деле считались в прямом направлении.
finalCountDown :: Int –> Writer (DiffList String) ()
finalCountDown 0 = tell (toDiffList ["0"])
finalCountDown x = do
finalCountDown (x-1)
tell (toDiffList [show x])
Если мы передаём ей значение 0, она просто записывает это значение в журнал. Для любого другого числа она сначала вычисляет предшествующее ему число в обратном направлении до 0, а затем добавляет это число в конец журнала. Поэтому если мы применим функцию finalCountDown к значению 100, строка "100" будет идти в журнале последней.
Если вы загрузите эту функцию в интерпретатор GHCi и примените её к большому числу, например к значению 500 000, то увидите, что она быстро начинает счёт от 0 и далее:
ghci> mapM_ putStrLn . fromDiffList .snd . runWriter $ finalCountDown 500000
0
1
2
...
Однако если вы измените её, чтобы она использовала обычные списки вместо разностных, например, так:
finalCountDown :: Int –> Writer [String] ()
finalCountDown 0 = tell ["0"]
finalCountDown x = do
finalCountDown (x-1)
tell [show x]
а затем скажете интерпретатору GHCi, чтобы он начал отсчёт:
ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000
вы увидите, что вычисления идут очень медленно.
Конечно же, это ненаучный и неточный способ проверять скорость ваших программ. Однако мы могли видеть, что в этом случае использование разностных списков начинает выдавать результаты незамедлительно, тогда как использование обычных занимает нескончаемо долгое время.
Ну, теперь в вашей голове наверняка засела песня «Final Countdown» группы Europe. Балдейте!