5

Haskellでこのコードカタをいじっていたところ、このトピックの質問に出くわしました。

インデックスが単一の数値である配列の中点を見つけるのは簡単ですが、Haskellの配列インデックスは、たとえば、カードがインスタンスであるタプル（Int、Word、Card）を含む、Ix型クラスの任意のインスタンスにすることができます。 Ixですが、Numではありません。

配列の中点を取得する1つの方法は、その長さを照会し、インデックスのリストを照会し、そのリストの半分を削除することですが、これにはO（n）時間が必要です。

定数時間でインデックスを作成する方法を知っている人はいますか？Ix範囲は整数範囲でバイジェクトすることになっているので、1つあるべきだと思います。

4

1 に答える 1

4

Ixtypeclassは、typeの値から。の値iへの注入のみを必要としますInt。indexと一緒にrange逆マッピングを与えることができます：

index' :: (Ix i) => (i, i) -> Int -> i
index' b x = range b ! x

ご覧のとおりindex'、少なくとも線形時間で評価されます。また、どのくらいの期間機能するかを知ることもできませんrange b。これは、ユーザーがインスタンス定義で定義した方法で評価されます。index'したがって、あなたの場合に必要な最適化（配列の中点を取得）は、一定時間で機能するようなものがある場合にのみ実行できます。typeclassはからへのIx一定の時間マッピングを提供しないので、ユーザーにそれを求める必要があります。次のコードを検討してください。Inti

midpoint :: (Ix j) => (Int -> j) -> Array j e -> e
midpoint f a = a ! f middle
               where middle = rangeSize (bounds a) `div` 2

現在、配列の中点を取ることの複雑さは、ユーザー定義の複雑さに依存しますf。したがって、インデックスタイプの値を値iから一定時間で評価できInt、その逆も可能である場合、一定時間で中点を取得します。

ixmapからの関数も考慮してData.Ixください：

ixmap :: (Ix i, Ix j) => (i, i) -> (i -> j) -> Array j e -> Array i e
于 2010-09-08T15:40:08.527 に答える