8

我总结了一个矩阵列表，foldl1 (+)因为我注意到它sum实际上将左上角元素的总和作为 1x1 矩阵返回。

$ stack exec --resolver lts-12.5 --package matrix -- ghci
GHCi, version 8.4.3: http://www.haskell.org/ghc/  :? for help
Prelude> import Data.Matrix
Prelude Data.Matrix> t = [identity 2, identity 2]  -- two 2x2 identity matrices
Prelude Data.Matrix> foldl1 (+) t
┌     ┐
│ 2 0 │
│ 0 2 │
└     ┘
Prelude Data.Matrix> sum t
┌   ┐
│ 2 │
└   ┘

这对我来说是出乎意料的，LYAH 建议sum = foldl1 (+)¹ 甚至 hlint 建议我使用sum而不是foldl1 (+)as is 'removes error on []'（附带问题：我如何优雅且[]安全地总结矩阵？）

为什么是sum /= foldl1 (+)矩阵，为什么通常不总是sum == foldl1 (+)？

或者，排除空列表的情况：

为什么不是sum == foldl neutralElement (+)？或具体sum == foldl (+) (zero 2 2)在[identity 2, identity 2]？

自己的工作：

Prelude Data.Matrix> :t sum
sum :: (Foldable t, Num a) => t a -> a
Prelude Data.Matrix> :info sum
class Foldable (t :: * -> *) where
  ...
  sum :: Num a => t a -> a
  ...
        -- Defined in ‘Data.Foldable’

来源sum是：

sum :: Num a => t a -> a
sum = getSum #. foldMap Sum

的实例化Matrix是：

instance Foldable Matrix where
foldMap f = foldMap f . mvect

instance Num a => Num (Matrix a) where
 fromInteger = M 1 1 . V.singleton . fromInteger
 negate = fmap negate
 abs = fmap abs
 signum = fmap signum

 -- Addition of matrices.
 {-# SPECIALIZE (+) :: Matrix Double -> Matrix Double -> Matrix Double #-}
 {-# SPECIALIZE (+) :: Matrix Int -> Matrix Int -> Matrix Int #-}
 (M n m v) + (M n' m' v')
   -- Checking that sizes match...
   | n /= n' || m /= m' = error $ "Addition of " ++ sizeStr n m ++ " and "
                               ++ sizeStr n' m' ++ " matrices."
   -- Otherwise, trivial zip.
   | otherwise = M n m $ V.zipWith (+) v v'

 -- Substraction of matrices.
 ...
 -- Multiplication of matrices.
 ...

¹ 在添加整数的情况下

4

3 回答 3

9

因为Data.Matrixfor 的实例通过返回一个 1x1 矩阵来实现，并Num通过添加which 将右侧矩阵截断为左侧矩阵的大小（如果左侧大于右侧则错误）。fromInteger+elementwise

sum是从foldl (+) 01x1 矩阵开始，0并将列表中的所有矩阵截断为该大小。foldl1 (+)不必从整数创建矩阵，因此结果是列表中最小矩阵的大小。

此外，sum = getSum #. foldMap Sum是默认Foldable实现，但它被列表实例覆盖为sum = foldl (+) 0.

如果操作数不是相同的形状，则（如上所示）版本 0.3.1.1 的实现会生成错误，但在 0.3.2.0 版本中它假定它们是相同的形状而不检查，而在 0.3.3.0 版本中Data.Matrix它+再次更改（根据评论）：

-- | Perform an operation element-wise.
--   The second matrix must have at least as many rows
--   and columns as the first matrix. If it's bigger,
--   the leftover items will be ignored.
--   If it's smaller, it will cause a run-time error.
--   You may want to use 'elementwiseUnsafe' if you
--   are definitely sure that a run-time error won't
--   arise.

实现似乎与当前版本 0.3.6.1 相同

于 2019-08-16T14:32:37.960 回答
2

我认为@pat 已经很好地回答了这个问题，但我会尝试回答附带问题：

我如何优雅地[]-安全地总结矩阵？

您不能安全地总结矩阵列表，因为您不确定列表中每个矩阵的大小是多少，除非您在类型级别拥有该大小信息。想象一个 type data Matrix (m :: Nat) (n :: Nat) e = ...，那么可以保证列表中的每个矩阵都具有完全相同的维度。我不确定通用数组库在该领域是否有任何工作，但我在OpenCV绑定和mapalgebra中看到了这种方法，并简要考虑在massiv中使用它。这种方法有一些缺点，但这对于这个问题并不重要。

另一种方法是不使用矩阵列表，而是使用 3D 数组，它本质上是相同大小的 2D 矩阵的页面序列。显然，matrix包不支持更高的维度，因此您无法使用该库来实现它。我会展示它是如何完成的massiv。考虑我们有这个 3D 数组a：

λ> a = makeArrayR D Par (Sz3 3 4 5) $ \(i :> j :. k) -> i + j * k
λ> a
Array D Par (Sz (3 :> 4 :. 5))
  [ [ [ 0, 0, 0, 0, 0 ]
    , [ 0, 1, 2, 3, 4 ]
    , [ 0, 2, 4, 6, 8 ]
    , [ 0, 3, 6, 9, 12 ]
    ]
  , [ [ 1, 1, 1, 1, 1 ]
    , [ 1, 2, 3, 4, 5 ]
    , [ 1, 3, 5, 7, 9 ]
    , [ 1, 4, 7, 10, 13 ]
    ]
  , [ [ 2, 2, 2, 2, 2 ]
    , [ 2, 3, 4, 5, 6 ]
    , [ 2, 4, 6, 8, 10 ]
    , [ 2, 5, 8, 11, 14 ]
    ]
  ]

然后我们可以foldlWithin用来折叠数组的任何维度，同时减少它的维度：

λ> foldlWithin Dim3 (+) 0 a
Array D Par (Sz (4 :. 5))
  [ [ 3, 3, 3, 3, 3 ]
  , [ 3, 6, 9, 12, 15 ]
  , [ 3, 9, 15, 21, 27 ]
  , [ 3, 12, 21, 30, 39 ]
  ]
λ> foldlWithin Dim1 (+) 0 a
Array D Par (Sz (3 :. 4))
  [ [ 0, 10, 20, 30 ]
  , [ 5, 15, 25, 35 ]
  , [ 10, 20, 30, 40 ]
  ]

请注意，没有机会引发异常或其他一些不可预测的行为，就像您在此处的任何时候遇到的那样（当然，将异步异常放在一边）。或者，可以获取数组的切片，然后单独添加它们，但是如果我们想避免异常，这种方法会涉及更多：

λ> a !?> 0
Array D Par (Sz (4 :. 5))
  [ [ 0, 0, 0, 0, 0 ]
  , [ 0, 1, 2, 3, 4 ]
  , [ 0, 2, 4, 6, 8 ]
  , [ 0, 3, 6, 9, 12 ]
  ]
λ> import Data.Maybe
λ> fromMaybe empty $ a !?> 0 >>= \acc0 -> foldlM (\acc pageIx -> (acc +) <$> (a !?> pageIx)) acc0 (1 ... 2)
Array D Par (Sz (4 :. 5))
  [ [ 3, 3, 3, 3, 3 ]
  , [ 3, 6, 9, 12, 15 ]
  , [ 3, 9, 15, 21, 27 ]
  , [ 3, 12, 21, 30, 39 ]
  ]

上面将产生Nothingifa没有索引的页面0through 2。另一方面，如果你对运行时异常没问题，那么这会更清楚一点，但不那么安全：

λ> foldlS (\acc pageIx -> acc + (a !> pageIx)) (a !> 0) (1 ... 2)
Array D Par (Sz (4 :. 5))
  [ [ 3, 3, 3, 3, 3 ]
  , [ 3, 6, 9, 12, 15 ]
  , [ 3, 9, 15, 21, 27 ]
  , [ 3, 12, 21, 30, 39 ]
  ]

或使用列表，如实际问题中所述：

λ> Prelude.foldl1 (+) $ Prelude.fmap (a !>) [0 .. 2]
Array D Par (Sz (4 :. 5))
  [ [ 3, 3, 3, 3, 3 ]
  , [ 3, 6, 9, 12, 15 ]
  , [ 3, 9, 15, 21, 27 ]
  , [ 3, 12, 21, 30, 39 ]
  ]

一个旁注。我注意到了SECIALIZEpragma 的使用，这让我相信你真的关心性能。一个小而重要的事实：matrix包在下面使用盒装向量作为Matrix数据类型，这总是会给您带来糟糕的性能，并且没有任何编译指示可以帮助您。

于 2019-08-18T19:15:19.897 回答
0

好的开始：

为什么通常不总是 sum == foldl1 (+)？

foldl1 (+) []
*** Exception: Prelude.foldl1: empty list

sum []
0

这是主要区别， sum 允许模式匹配[]和foldl1 (+)不匹配。

foldl1旨在与非空列表一起使用，因为有些函数对空列表没有意义，例如：

foldl1 max

max是什么[]？没有最大值，因为没有元素。

foldl1 max [5,4,2,3]
5
于 2019-08-16T13:46:53.063 回答