haskell - 如何在 Haskell 中创建三角数组

Question

我想做类似的事情

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 的内容，但我认为这不是最佳选择。有没有办法将这个数组的边界设置为“三角形”？

Answer 1

一个简单的上三角索引可以定义为:

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 pr@(a :. b, c :. d) ix@(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"