Списки не имеют специальной оперативной обработки в Haskell.Они определены так:
data List a = Nil | Cons a (List a)
Просто с некоторыми специальными обозначениями: [a] для List a, [] для Nil и (:) для Cons.Если бы вы определили одно и то же и переопределили все операции, вы получите одинаковую производительность.
Таким образом, списки Haskell являются односвязными.Из-за лени они часто используются как итераторы.sum [1..n] работает в постоянном пространстве, поскольку неиспользуемые префиксы этого списка отбираются мусором по мере увеличения суммы, а хвосты не генерируются до тех пор, пока они не потребуются.
Что касается # 4: all значения в Haskell запоминаются, за исключением того, что функции не сохраняют таблицу памятки для своих аргументов.Поэтому, когда вы определяете fib так, как вы это сделали, результаты будут кэшироваться, и к n-му числу Фибоначчи будет обращаться за O (n) время.Однако, если вы определили это, по-видимому, эквивалентным образом:
-- Simulate infinite lists as functions from Integer
type List a = Int -> a
cons :: a -> List a -> List a
cons x xs n | n == 0 = x
| otherwise = xs (n-1)
tailF :: List a -> List a
tailF xs n = xs (n+1)
fib :: List Integer
fib = 1 `cons` (1 `cons` (\n -> fib n + tailF fib n))
(Найдите время, чтобы заметить сходство с вашим определением)
Тогда результаты не будут разделены, и n-е число Фибоначчибудут доступны в O (FIB N) (экспоненциальный) времени.Вы можете убедить функции для совместного использования с библиотекой напоминаний, например data-memocombinators .