48

Haskell のリストの正確な実装の詳細に興味がありました (GHC 固有の回答は問題ありません)。それらは単純なリンク リストですか、それとも特別な最適化がありますか? すなわち：

  1. (たとえば) リストを反復処理する必要がありますlengthか?(!!)
  2. その場合、それらの値は何らかの方法でキャッシュされますか (つまり、length2 回呼び出した場合、両方を繰り返す必要がありますか)?
  3. リストの最後にアクセスするには、リスト全体を反復処理する必要がありますか?
  4. 無限リストとリスト内包表記はメモ化されていますか? (つまり、 for のfib = 1:1:zipWith (+) fib (tail fib)場合、各値は再帰的に計算されますか、それとも以前に計算された値に依存しますか?)

その他の興味深い実装の詳細は大歓迎です。前もって感謝します！

4

3 に答える 3

43

Haskell では、リストには特別な操作上の取り扱いはありません。それらは次のように定義されます。

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

[a]for List a、[]for Nil、および(:)forという特別な表記法があり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) (指数関数的) 時間でアクセスされます。関数をdata-memocombinators のようなメモ化ライブラリと共有するように説得できます。

于 2010-04-22T08:53:19.553 に答える
12

私の知る限り（これがGHC固有のものであるかどうかはわかりません）

  1. lengthリストを(!!)反復処理する必要があります。

  2. リストに特別な最適化はないと思いますが、すべてのデータ型に適用される手法があります。

    あなたがのようなものを持っているなら

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

    その後、length xs2回計算されます。

    しかし、代わりにあなたが持っている場合

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

    その後、1回だけ計算されます。

  3. はい。

  4. はい、名前付きの値の一部が計算されると、その名前がスコープ外になるまで保持されます。（言語はこれを必要としませんが、これは実装が動作することを私が理解する方法です。）

于 2010-04-22T08:03:20.267 に答える
11

もしそうなら、それらの値は何らかの方法でキャッシュされていますか (つまり、length を 2 回呼び出した場合、2 回反復する必要がありますか)?

GHC は完全な Common Subexpression Elimination を実行しません。例えば：

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

aaaaaaaaa2 回呼び出すことに注意してくださいGHC.List.$wlen。

(実際には、xに保持する必要があるためaaaaaaaaa、 よりも 2 倍以上遅くなりbbbbbbbbbます。)

于 2010-04-22T08:54:45.370 に答える