Вопросы Теги

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

Мне было просто любопытно на предмет некоторых точных деталей реализации списков в Haskell (GHC-определенные ответы прекрасны) - они наивные связанные списки, или у них есть какая-либо специальная оптимизация? Более конкретно:

  1. Сделать length и (!!) (например), должны выполнить итерации через список?
  2. Если так, их значения, кэшируемые всегда (т.е. если я звоню length дважды, это должно будет выполнить итерации оба раза)?
  3. Действительно получает доступ к обратной стороне списка, включают итерацию через целый список?
  4. Бесконечные списки являются и перечисляют мемоизованные понимания? (т.е. для fib = 1:1:zipWith (+) fib (tail fib), каждый оценит быть вычисленным рекурсивно, или это будет полагаться на предыдущее вычисленное значение?)

Любые другие интересные детали реализации очень ценились бы.Заранее спасибо!

41
задан shosti 22 April 2010 в 07:35
поделиться

3 ответа

Списки не имеют специальной оперативной обработки в Haskell. Они определены примерно так: 

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

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

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

35
ответ дан 27 November 2019 в 00:49
поделиться

Насколько мне известно (я не знаю, насколько это связано с GHC)

  1. длина и (!!) НЕОБХОДИМО перебирать список.

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

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

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

    , то length xs будет вычисляться дважды.

    Но если вместо этого у вас есть 

     foo xs = bar len ++ baz len 
, где len = length xs

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

  3. Да.

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

10
ответ дан 27 November 2019 в 00:49
поделиться

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

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-simple : 

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)
    }

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

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

{{1 }}
10
ответ дан 27 November 2019 в 00:49
поделиться
Другие вопросы по тегам:

Похожие вопросы: