Haskell在O（1）時間獲得Ix範圍的中間值

我在Haskell中玩this代碼kata，我在主題中遇到了這個問題。Haskell在O（1）時間獲得Ix範圍的中間值

查找索引爲單個數值的數組的中點很簡單，但Haskell的數組索引可以是Ix類型類的任何實例，包括例如元組（卡，Int，Word，Card）是Ix的一個實例，但不是Num的一個實例。

獲取數組中點的一種方法是查詢其長度，查詢索引列表，並將該列表的一半放下，但這需要O（n）時間。

有沒有人知道一種方法來索引做它在恆定時間？我覺得應該有一個，因爲Ix範圍應該用整數範圍進行投射。

來源

2010-09-08 Alex R

如果真的存在一個雙射，那麼爲什麼不映射到整數，計算中點，然後採取逆映射回它的索引類型？我不知道什麼樣的機制會允許Haskell這樣做，但似乎有可能？ – Gian 2010-09-08 14:28:24

「Ix」類中的函數'index'是bijection的一部分，將索引映射到整數，但另一個缺失，據我所知。 – yatima2975 2010-09-08 14:51:13

Ix typeclass僅要求從i類型的值注入到Int的值。 index與range在一起可以給我們逆映射：

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

正如你可以看到index'線性時間至少評估。我們也無法知道range b的工作時間。它以用戶在實例定義中定義的方式進行評估。所以在你的情況下需要優化（獲得一個數組的中點）可以發生當且僅當我們有某種類型的恆定時間工作的index'。由於Ix typeclass沒有給我們提供從Int到i的恆定時間映射，我們應該詢問用戶。考慮下面的代碼：

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-08 15:40:08 fizruk

Haskell在O（1）時間獲得Ix範圍的中間值

回答

相關問題