Search code examples
haskellmatrixsumfoldfoldable

Why isn't sum == foldl1 (+)?


I sum a list of matrices with foldl1 (+) because I noticed that sum actually returns the sum of the top left elements as a 1x1 matrix.

$ 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 │
└   ┘

This is unexpected for me, LYAH suggests sum = foldl1 (+)¹ and even hlint suggests I use sum instead of foldl1 (+) as is 'removes error on []' (side question: How do I elegantly and []-safely sum up matrices?)

Why is sum /= foldl1 (+) for Matrices, and why isn't generally always sum == foldl1 (+)?

Or, to exclude the case of the empty list:

Why isn't sum == foldl neutralElement (+)? or specifically sum == foldl (+) (zero 2 2) on [identity 2, identity 2]?

Own work:

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’

Source of sum is:

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

Instantiations of Matrix are:

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.
 ...

¹ in the context of adding integers


Solution

  • Because the Data.Matrix instance for Num implements fromInteger by returning a 1x1 matrix, and + by adding elementwise which truncates the right matrix to the size of the left one (or errors if the left is larger than the right).

    The sum is foldl (+) 0 which starts with a 1x1 matrix from the 0 and truncates all of the matrices in the list to that size. The foldl1 (+) does not have to make a matrix from an integer, so the result is the size of the smallest matrix in the list.

    Also, sum = getSum #. foldMap Sum is the default Foldable implementation, but it is overridden by the list instance to be sum = foldl (+) 0.

    The Data.Matrix implementation of + (as you show above) up to version 0.3.1.1 generates an error if the operands are not the same shape, but in version 0.3.2.0 it assumes they are the same shape without checking, and in version 0.3.3.0 it changed again (according to the comment):

    -- | 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.
    

    The implementation appears to be the same up to the current version 0.3.6.1