如何做一個三角形陣列在Haskell

我要像做如何做一個三角形陣列在Haskell

array ((0,0), (25, 25)) [((i,j), 1) | i <- [0..25], j <- [i..25]]

您可以通過數組索引看，只被定義時i <= j。但是，當我嘗試在ghci中打印出來時，我得到一個錯誤，因爲它嘗試打印類似(1,0)的數據，因爲數組邊界。

((1,0),*** Exception: (Array.!): undefined array element

我可以在陣列是正方形，把類似0的這些項，但我認爲這將是最理想的。有沒有辦法將這個數組的邊界設置爲「三角形」？

來源

2017-01-02 Mike Flynn

'NEWTYPE三角A =三角（陣列（INT，INT）一）'，編寫自定義的'Show'實例，並確保你的代碼永遠不會意外訪問數組的未定義部分。不過，你不會從類型檢查中得到很多幫助。 –

或者，您也可以定義一種新的['Ix']（https://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Ix.html）索引 – Alec

如果您想避免浪費了一半的空間，你可以使用一維數組，並計算索引爲「dij =（i *（i-1））'div' 2 + j」。 –

簡單上三角索引可以被定義爲：

import Data.Ix (Ix, range, index, inRange) 

data UpperTriagIndex = Int :. Int 
    deriving (Show, Ord, Eq) 

instance Ix UpperTriagIndex where 
    range (a :. b, c :. d) = concatMap (\i -> (i :.) <$> [max i b..d]) [a..c] 
    inRange (a :. b, c :. d) (i :. j) = a <= i && i <= c && b <= j && j <= d 

    index [email protected](a :. b, c :. d) [email protected](i :. j) 
    | inRange pr ix = f a - f i + j - i 
    | otherwise  = error "out of range!" 
    where f x = let s = d + 1 - max x b in s * (s + 1) `div` 2

一個可以驗證range和index往返即使陣列是不正方形。例如：

\> let pr = (0 :. 0, 3 :. 5) in index pr <$> range pr 
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17] -- [0..17]

和：

\> import Data.Array (array, (!)) 
\> let f i j = (i :. j, "row: " ++ show i ++ ", col: " ++ show j) 
\> let a = array ((0 :. 0), (3 :. 3)) [f i j | i <- [0..3], j <- [i..3]] 
\> a ! (2 :. 3) 
"row: 2, col: 3"

來源

2017-01-02 19:06:49

如何做一個三角形陣列在Haskell

回答

相關問題