Haskellの配列

Question

コンストラクタ配列を使用して、どのように配列がhaskellで作成されますか？つまり、最初の要素を作成するのでしょうか？その場合、関連リストをどのように読み取るのですか？例えば

我々は、次の2つのプログラムを検討している場合： -

ar :: Int->(Array Int Int) 
ar n = array (0,(n-1)) (((n-1),1):[(i,((ar n)!(i+1))) | i<-[0..(n-2)]]) 

ar :: Int->(Array Int Int) 
ar n = array (0,(n-1)) ((0,1):[(i,((ar n)!(i-1))) | i<-[1..(n-1)]]) 

は、これら2つの異なる時間の複雑さを持っているのだろうか？

Answer 1

実装にもよりますが、妥当な実装では、どちらも同じ複雑さ（配列サイズの線形）があります。 GHCのアレイの実装で

、我々はコード

array (l,u) ies 
    = let n = safeRangeSize (l,u) 
     in unsafeArray' (l,u) n 
         [(safeIndex (l,u) n i, e) | (i, e) <- ies] 

{-# INLINE unsafeArray' #-} 
unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e 
unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# -> 
    case newArray# n# arrEleBottom s1# of 
     (# s2#, marr# #) -> 
      foldr (fill marr#) (done l u n marr#) ies s2#) 

{-# INLINE fill #-} 
fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a 
-- NB: put the \s after the "=" so that 'fill' 
--  inlines when applied to three args 
fill marr# (I# i#, e) next 
= \s1# -> case writeArray# marr# i# e s1# of 
      s2# -> next s2# 

を見れば、我々は、メモリの最初の新しいチャンクが順次errorある（arrEleBottomが充填されているアレイに割り当てられていることがわかりますメッセージ "未定義の配列要素"）を呼び出し、リストに含まれている要素がリストに表示されている順序でそれぞれのインデックスに書き込まれます。一般的に

、それは建設上のアレイに書き込まれているもの箱入りの配列は、あなたの例ではリテラル1のようなことが必要なときに値を計算する方法を指定するサンク（明示的値を指定し、ですので、配列に書き込まれたその値への直接ポインタになります）。

このようなサンクの評価が強制されると、サンクがここのような他の配列要素を参照する場合、配列内のさらなるサンクの評価も強制されることがあります。ここでの特定の例では、サンクを強制すると、後ですべてのサンクを強制的にリスペンドします。他の配列要素を参照していないエントリが最後に到達するまで配列の前に移動します。最初の例では、強制される最初の配列要素がインデックス0にある場合、配列長に比例したサイズのサンクが作成され、それが縮小されるため、最初の配列要素を強制すると複雑さはO（n）それ以降のすべての要素は既に評価されており、それらを強制的にO（1）にします。第2の例では、状況は対称的であり、最後に最後の要素を強制的に合計評価コストが発生する。要素が異なる順序で要求される場合、すべてのサンクを評価するコストは、異なる要素の要求全体に分散されますが、合計コストは同じです。未評価のサンクを評価するコストは、次に評価されたサンクからの距離に比例し、間にあるすべてのサンクを評価することを含みます。

アレイのアクセスは一定時間です（キャッシュエフェクトは除きますが、配列を前方または後方に塗りつぶしても差がないはずですが、インデックスがランダムな順序であれば大きな違いになりますが、時間の複雑さには影響しません）、どちらも同じ複雑さを持っています。

しかし、ar nを使用して配列要素を定義すると、複数の配列が割り当てられる危険性があります（最適化なしでコンパイルした場合、GHCはこれを行います。 1つしか作成されていないことを確認するには、

ar n = result 
    where 
    result = array (0,n-1) (... result!index ...)