Как списки, реализованные в Haskell (GHC)?

Ответ 1

В Haskell списки не имеют специального режима работы. Они определяются так же, как:

data List a = Nil | Cons a (List a)

Просто с некоторыми специальными обозначениями: [a] для List a, [] для Nil и (:) для Cons. Если вы определили одно и то же и переопределили все операции, вы получите точно такую ​​же производительность.

Таким образом, списки Haskell связаны друг с другом. Из-за лени они часто используются в качестве итераторов. sum [1..n] работает в постоянном пространстве, потому что неиспользуемые префиксы этого списка собирают мусор, когда сумма прогрессирует, а хвосты не генерируются до тех пор, пока они не понадобятся.

Что касается №4: все значения в 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) (которое является экспоненциальным). Вы можете убедить функции, которые будут использоваться в библиотеке memoization, например data-memocombinators.

Ответ 2

Насколько я знаю (я не знаю, насколько это специфично для GHC)

• length и (!!) Необходимо выполнить итерацию по списку.

• Я не думаю, что для списков есть специальные оптимизации, но есть метод, который применяется ко всем типам данных.

  Если у вас есть что-то вроде

  foo xs = bar (length xs) ++ baz (length xs)
  

  тогда length xs будет вычислен дважды.

  Но если вместо этого вы

  foo xs = bar len ++ baz len
    where len = length xs
  

  то он будет вычисляться только один раз.

• Да.

• Да, когда часть именованного значения вычисляется, она сохраняется до тех пор, пока имя не выйдет из области видимости. (Этот язык не требует этого, но я так понимаю, что реализации ведут себя.)

Ответ 3

Если это так, то их значения кэшируются каким-либо образом (т.е. если я дважды вызываю длину, будет ли он итерации оба раза)?

GHC не выполняет полное ограничение общего подвыражения. Например:

{-# NOINLINE aaaaaaaaa #-}
aaaaaaaaa :: [a] -> Int
aaaaaaaaa x = length x + length x

{-# NOINLINE bbbbbbbbb #-}
bbbbbbbbb :: [a] -> Int
bbbbbbbbb x = l + l where l = length x

main = bbbbbbbbb [1..2000000] `seq` aaaaaaaaa [1..2000000] `seq` return ()

Дает на -ddump-simpl:

Main.aaaaaaaaa [NEVER Nothing] :: forall a_adp.
                                  [a_adp] -> GHC.Types.Int
GblId
[Arity 1
 NoCafRefs
 Str: DmdType Sm]
Main.aaaaaaaaa =
  \ (@ a_ahc) (x_adq :: [a_ahc]) ->
    case GHC.List.$wlen @ a_ahc x_adq 0 of ww_anf { __DEFAULT ->
    case GHC.List.$wlen @ a_ahc x_adq 0 of ww1_Xnw { __DEFAULT ->
    GHC.Types.I# (GHC.Prim.+# ww_anf ww1_Xnw)
    }
    }

Main.bbbbbbbbb [NEVER Nothing] :: forall a_ado.
                                  [a_ado] -> GHC.Types.Int
GblId
[Arity 1
 NoCafRefs
 Str: DmdType Sm]
Main.bbbbbbbbb =
  \ (@ a_adE) (x_adr :: [a_adE]) ->
    case GHC.List.$wlen @ a_adE x_adr 0 of ww_anf { __DEFAULT ->
    GHC.Types.I# (GHC.Prim.+# ww_anf ww_anf)
    }

Обратите внимание, что aaaaaaaaa дважды вызывает GHC.List.$wlen.

(На самом деле, поскольку x необходимо сохранить в aaaaaaaaa, оно больше, чем на 2 раза медленнее, чем bbbbbbbbb.)