如何在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"