haskell - 如何在 Haskell 中扩展矩阵

Question

我一直在尝试创建一个函数，该函数返回给定矩阵并添加一行和一列，其数字是旁边行/列中数字的总和 数字列中数字的总和...

例如

(1 2
 3 4)

到

(1 2 3
 3 4 7
4 6 10)

我的第一个想法是这样的

> extend1 :: Int -> Array (Int,Int) Int
> extend1 ((a,b),(c,d))  = n where
>                 n = array ((a,b),(c,d),(n,n))

因为我必须使用“数组”。现在我不知道如何继续下去。是好还是完全错了？

Answer 1

使用您对元组的表示并且不太关注一般性，这是您问题的解决方案。

type Square2 a = ((a,a), (a,a))
type Square3 a = ((a,a,a), (a,a,a), (a,a,a))

extend1 :: Num a => Square2 a -> Square3 a
extend1 ((a,b), (c,d)) = 
  ( (a,  b,  ab  )
  , (c,  d,  cd  )
  , (ac, bd, abcd) ) 

  where
    ab   = a  + b
    cd   = c  + d
    ac   = a  + c
    bd   = b  + d
    abcd = ab + cd

请注意我如何使用从输入模式和 where 子句中的定义中剔除的变量定义。还要注意我在构建全新输出的同时如何破坏和使用输入——一些元素被重用，但结构本身被破坏了。最后请注意我如何选择元组内部的类型为常量并受 Num 类型类约束，这允许我使用 (+) 进行加法。

一个类似的函数，泛化并使用 Arrays 有一个类似的类型

extend1A :: Num a => Array (Int,Int) a -> Array (Int, Int) a

我们失去了知道 Array 的确切大小的能力，但它表明我们的函数采用某个大小的 Array 并返回另一个 具有相同索引且包含相同 Num 约束类型的数组。

array 函数将一组边界作为其第一个参数。我们需要根据输入数组的 bounds 更新那些

extend1A ary0 = array bounds1 ... where
  ((minX, minY), (maxX, maxY)) = bounds ary0
  (maxX1, maxY1) = (succ maxX, succ maxY)
  bounds1 = ((minX, minY, (maxX1, maxY1))

然后 array 将“assocs”列表作为其第二个参数。我们可以将任何 Array ix a 视为(大致)等价于 assocs [(ix, a)] 的列表，其中列出的值表示“在索引处 ix 值为 a”。为此，我们必须知道我们之前管理的 ix 类型的 bounds。

要使用旧数组的信息更新数组，我们可以修改旧数组的 assocs 以包含新信息。具体来说，这意味着 extend1A 看起来有点像

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where
  priorInformation = assocs ary0
  extraInformation = ...
  ((minX, minY), (maxX, maxY)) = bounds ary0
  (maxX1, maxY1) = (succ maxX, succ maxY)
  bounds1 = ((minX, minY, (maxX1, maxY1))

如果 extraInformation 为空 ([])，则 extend1A ary 在所有索引上都等于 ary在输入范围内 ary 和 undefined 在其范围之外。我们需要在extraInformation中填写求和信息。

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where
  priorInformation = assocs ary0 
  extraInformation = xExtension ++ yExtension ++ totalExtension
  xExtension = ...
  yExtension = ...
  totalExtension = ...
  ((minX, minY), (maxX, maxY)) = bounds ary0
  (maxX1, maxY1) = (succ maxX, succ maxY) 
  bounds1 = ((minX, minY, (maxX1, maxY1))

如果我们想分三 block 扩展数组，extend1中ab和cd标记的xExtension >，extend1中ac和bd标记的yExtension和totalExtension标记通过 abcd 在 extend1 中，我们可以依次计算每个部分。

totalExtension 是最简单的——它只是 priorInformation 中每个 (i,a) 对的“值分量”的总和。它也可以是 xExtension 或 yExtension 的“值组件”之和，但为了尽可能明显正确，我们将选择第一个选项并将其安装在右下角。

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where
  priorInformation = assocs ary0
  extraInformation = xExtension ++ yExtension ++ totalExtension
  sumValues asscs = sum (map snd asscs)
  xExtension = ...
  yExtension = ...
  totalExtension = [((maxX1, maxY1), sumValues priorInformation)]
  ((minX, minY), (maxX, maxY)) = bounds ary0
  (maxX1, maxY1) = (succ maxX, succ maxY)
  bounds1 = ((minX, minY), (maxX1, maxY1))

请注意，我们可以使用 where 子句来定义新函数，例如 sumValues，它会反复出现。

然后我们可以将扩展计算为对 priorInformation 的列表理解。我们需要对旧关联收集一种特殊的总和——对一个索引固定的所有值求和。

xExtension = [( (maxX1, yix)
              , sumValues (filter (\((_, j), _) -> j == yix) priorInformation)
              )
             | yix <- [minY .. maxY]
             ]

yExtension = [( (xix, maxY1)
              , sumValues (filter (\((i, _), _) -> i == xix) priorInformation)
              )
             | xix <- [minX .. maxX]
             ]

然后我们就完成了。它效率不高，但所有部分协同工作。

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where
  priorInformation = assocs ary0
  extraInformation = xExtension ++ yExtension ++ totalExtension
  xExtension = [( (maxX1, yix)
                , sumValues (filter (\((_, j), _) -> j == yix) priorInformation)
                )
               | yix <- [minY .. maxY]
               ]
  yExtension = [( (xix, maxY1)
                , sumValues (filter (\((i, _), _) -> i == xix) priorInformation)
                )
               | xix <- [minX .. maxX]
               ]
  totalExtension = [((maxX1, maxY1), sum xExtension)]
  ((minX, minY), (maxX, maxY)) = bounds ary0
  (maxX1, maxY1) = (succ maxX, succ maxY)
  bounds1 = ((minX, minY), (maxX1, maxY1))