Haskell складывает плохую производительность с (++)
У меня есть этот код:
import Data.List
newList_bad lst = foldl' (\acc x -> acc ++ [x*2]) [] lst
newList_good lst = foldl' (\acc x -> x*2 : acc) [] lst
Эти функции возвращают списки с каждым элементом, умноженным на 2:
*Main> newList_bad [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> newList_good [1..10]
[20,18,16,14,12,10,8,6,4,2]
В ghci:
*Main> sum $ newList_bad [1..15000]
225015000
(5.24 secs, 4767099960 bytes)
*Main> sum $ newList_good [1..15000]
225015000
(0.03 secs, 3190716 bytes)
ЗачемnewList_bad
функция работает в 200 раз медленнее, чемnewList_good
? Я понимаю, что этоне является хорошим решением для этой задачи. Но почему этот невинный код работает так медленно?
Что это "4767099960 байт "?? Для этой простой операции Haskell использовал 4 GiB ??
После компиляции:
C:\1>ghc -O --make test.hs
C:\1>test.exe
225015000
Time for sum (newList_bad [1..15000]) is 4.445889s
225015000
Time for sum (newList_good [1..15000]) is 0.0025005s