在Haskell中写这个Scala矩阵乘法

Question

可能重复:
你能在haskell中超载吗？

你能实现一个可以在两个矩阵上工作的Matrix类和*运算符吗？:

scala> val x = Matrix(3, 1,2,3,4,5,6)  
x: Matrix =   
[1.0, 2.0, 3.0]  
[4.0, 5.0, 6.0]  

scala> x*x.transpose  
res0: Matrix =   
[14.0, 32.0]  
[32.0, 77.0]  

所以人们不会说这很难,这就是Scala的实现(由Jonathan Merritt提供):

class Matrix(els: List[List[Double]]) {  

    /** elements of the matrix, stored as a list of  
      its rows */  
    val elements: List[List[Double]] = els  
    def nRows: Int = elements.length  
    def nCols: Int = if (elements.isEmpty) 0   
                     else elements.head.length  

    /** all rows of the matrix must have the same  
        number of columns */  
    require(elements.forall(_.length == nCols))  

    /* Add to each elem of matrix */
    private def addRows(a: List[Double],   
                        b: List[Double]):   
      List[Double] =   
        List.map2(a,b)(_+_)  

    private def subRows(a: List[Double],   
                        b: List[Double]):List[Double] =  
        List.map2(a,b)(_-_)  

    def +(other: Matrix): Matrix = {  
      require((other.nRows == nRows) &&   
              (other.nCols == nCols))  
      new Matrix(  
        List.map2(elements, other.elements)  
          (addRows(_,_))
      )  
    }  

    def -(other: Matrix): Matrix = {  
      require((other.nRows == nRows) &&   
              (other.nCols == nCols))  
      new Matrix(  
        List.map2(elements, other.elements)  
          (subRows(_,_))  
      )  
    }  

    def transpose(): Matrix = new Matrix(List.transpose(elements))    

    private def dotVectors(a: List[Double],   
                       b: List[Double]): Double = {  
      val multipliedElements =   
        List.map2(a,b)(_*_)  
      (0.0 /: multipliedElements)(_+_)  
    }  

    def *(other: Matrix): Matrix = {  
      require(nCols == other.nRows)  
      val t = other.transpose()  
      new Matrix(  
        for (row <- elements) yield {  
          for (otherCol <- t.elements)  
            yield dotVectors(row, otherCol)  
        }  
      )  

    override def toString(): String = {  
        val rowStrings =   
        for (row <- elements)   
          yield row.mkString("[", ", ", "]")  
        rowStrings.mkString("", "\n", "\n")  
    }  
}  

/* Matrix constructor from a bunch of numbers */
object Matrix {  
  def apply(nCols: Int, els: Double*):Matrix = {  
    def splitRowsWorker(  
      inList: List[Double],   
      working: List[List[Double]]):  
    List[List[Double]] =  
      if (inList.isEmpty)  
        working  
      else {  
        val (a, b) = inList.splitAt(nCols)  
        splitRowsWorker(b, working + a)  
      }  
    def splitRows(inList: List[Double]) =  
      splitRowsWorker(inList, List[List[Double]]())  
    val rows: List[List[Double]] =   
      splitRows(els.toList)  
    new Matrix(rows)  
  }  
}  

编辑我明白,严格来说答案是否定的:重载*是不可能没有定义+和其他或特殊技巧的副作用.该数字-前奏包最好地描述它:

在某些情况下,层次结构不够精细:通常将独立定义的操作集中在一起.例如,在财务应用程序中,可能需要类型"Dollar",或者在图形应用程序中,可能需要类型"Vector".添加两个向量或美元是合理的,但通常不合理地将它们相乘.但是当程序员为'(+)'定义方法时,程序员当前被迫为'(*)'定义一个方法.

Answer 1

使用智能构造器和存储尺寸将非常安全.当然,对于操作没有自然的实现,signum并且fromIntegral(或者对于后者,对角矩阵也可以是好的).

module Matrix (Matrix(),matrix,matrixTranspose) where

import Data.List (transpose)

data Matrix a = Matrix {matrixN :: Int, 
                        matrixM :: Int,
                        matrixElems :: [[a]]}
                deriving (Show, Eq)

matrix :: Int -> Int -> [[a]] -> Matrix a
matrix n m vals
  | length vals /= m            = error "Wrong number of rows"
  | any (/=n) $ map length vals = error "Column length mismatch"
  | otherwise = Matrix n m vals

matrixTranspose (Matrix m n vals) = matrix n m (transpose vals)

instance Num a => Num (Matrix a) where

  (+) (Matrix m n vals) (Matrix m' n' vals')
    | m/=m' = error "Row number mismatch"
    | n/=n' = error "Column number mismatch"
    | otherwise = Matrix m n (zipWith (zipWith (+)) vals vals')

  abs (Matrix m n vals) = Matrix m n (map (map abs) vals)

  negate (Matrix m n vals) = Matrix m n (map (map negate) vals)

  (*) (Matrix m n vals) (Matrix n' p vals')
    | n/=n' = error "Matrix dimension mismatch in multiplication"
    | otherwise = let tvals' = transpose vals'
                      dot x y = sum $ zipWith (*) x y
                      result = map (\col -> map (dot col) tvals') vals
                  in Matrix m p result

在ghci中测试它:

*Matrix> let a = matrix 3 2 [[1,0,2],[-1,3,1]]
*Matrix> let b = matrix 2 3 [[3,1],[2,1],[1,0]]
*Matrix> a*b
Matrix {matrixN = 3, matrixM = 3, matrixElems = [[5,1],[4,2]]}

由于我的Num实例是通用的,它甚至适用于开箱即用的复杂矩阵:

Prelude Data.Complex Matrix> let c = matrix 2 2 [[0:+1,1:+0],[5:+2,4:+3]]
Prelude Data.Complex Matrix> let a = matrix 2 2 [[0:+1,1:+0],[5:+2,4:+3]]
Prelude Data.Complex Matrix> let b = matrix 2 3 [[3:+0,1],[2,1],[1,0]]
Prelude Data.Complex Matrix> a
Matrix {matrixN = 2, matrixM = 2, matrixElems = [[0.0 :+ 1.0,1.0 :+ 0.0],[5.0 :+ 2.0,4.0 :+ 3.0]]}
Prelude Data.Complex Matrix> b
Matrix {matrixN = 2, matrixM = 3, matrixElems = [[3.0 :+ 0.0,1.0 :+ 0.0],[2.0 :+ 0.0,1.0 :+ 0.0],[1.0 :+ 0.0,0.0 :+ 0.0]]}
Prelude Data.Complex Matrix> a*b
Matrix {matrixN = 2, matrixM = 3, matrixElems = [[2.0 :+ 3.0,1.0 :+ 1.0],[23.0 :+ 12.0,9.0 :+ 5.0]]}

编辑:新材料

哦,你想要在(*)没有任何Num东西的情况下覆盖这个功能.这可能是o但你必须记住Haskell标准库已保留(*)在Num类中使用.

module Matrix where

import qualified Prelude as P
import Prelude hiding ((*))
import Data.List (transpose)

class Multiply a where
  (*) :: a -> a -> a

data Matrix a = Matrix {matrixN :: Int, 
                        matrixM :: Int,
                        matrixElems :: [[a]]}
                deriving (Show, Eq)

matrix :: Int -> Int -> [[a]] -> Matrix a
matrix n m vals
  | length vals /= m            = error "Wrong number of rows"
  | any (/=n) $ map length vals = error "Column length mismatch"
  | otherwise = Matrix n m vals

matrixTranspose (Matrix m n vals) = matrix n m (transpose vals)

instance P.Num a => Multiply (Matrix a) where
  (*) (Matrix m n vals) (Matrix n' p vals')
    | n/=n' = error "Matrix dimension mismatch in multiplication"
    | otherwise = let tvals' = transpose vals'
                      dot x y = sum $ zipWith (P.*) x y
                      result = map (\col -> map (dot col) tvals') vals
                  in Matrix m p result


a = matrix 3 2 [[1,2,3],[4,5,6]]
b = a * matrixTranspose

在ghci中测试:

*Matrix> b
Matrix {matrixN = 3, matrixM = 3, matrixElems = [[14,32],[32,77]]}

那里.现在,如果第三个模块想要同时使用它的Matrix版本(*)和Prelude版本,(*)那么当然必须导入一个或另一个合格的模块.但这只是照常营业.

我可以在没有Multiply类型类的情况下完成所有这些,但是这个实现使我们新的闪亮(*)开放在其他模块中进行扩展.

Answer 2

好吧,有很多关于这里发生了什么漂浮混乱的,它不是由事实哈斯克尔术语"类"确实帮助不以任何有意义的方式OO术语"类"排队.所以让我们试着仔细回答一下.这个答案从Haskell的模块系统开始.

在Haskell中,当您导入模块时Foo.Bar,它会创建一组新的绑定.对于x模块导出的每个变量Foo.Bar,您将获得一个新名称Foo.Bar.x.此外,您可以:

• 是否合格进口.如果您导入合格,则不会发生任何其他事 如果不这样做,则定义不带模块前缀的附加名称; 在这种情况下,只x定义了旧的.
• 是否更改资格前缀.如果导入as Alias,则Foo.Bar.x未定义名称,但名称Alias.x为.
• 隐藏某些名字.如果隐藏名称foo,则既不定义普通名称foo也不定义任何限定名称(如Foo.Bar.foo或Alias.foo).

此外,名称可以多次定义.例如,如果Foo.Bar并且Baz.Quux两者都导出变量x,并且我导入了两个模块而没有限定条件,则名称x引用两个 Foo.Bar.x和Baz.Quux.x.如果名称x从未在结果模块中使用,则忽略此冲突; 否则,编译器错误会要求您提供更多资格.

最后,如果您的导入都没有提到模块Prelude,则会添加以下隐式导入:

import Prelude

这导入Prelude没有限定条件,没有附加前缀,也没有隐藏任何名称.因此它定义了"裸"名称和名称前缀Prelude.,仅此而已.

这里结束了您需要了解的有关模块系统的基本知识.现在让我们讨论一下你需要了解的关于类型类的基本知识.

类型类包括类名,由该类绑定的类型变量列表,以及具有引用绑定变量的类型签名的变量集合.这是一个例子:

class Foo a where
    foo :: a -> a -> Int

类名是Foo绑定类型变量a,集合中只有一个变量,即foo带有类型签名a -> a -> Int.这个类声明某些类型有一个名为binary的二进制操作foo,它计算一个Int.任何类型可能稍后(甚至在另一个模块中)被声明为此类的实例:这涉及定义上面的二进制操作,其中绑定的类型变量a被替换为您为其创建实例的类型.作为一个例子,我们可以通过实例为整数实现这个:

instance Foo Int where
    foo a b = (a `mod` 76) * (b + 7)

这里结束了您需要了解的关于类型类的基本知识.我们现在可以回答您的问题.这个问题很棘手的唯一原因是因为它忽略了两种名称管理技术的交集:模块和类型类.下面我将讨论这对您的具体问题意味着什么.

该模块Prelude定义了一个名为的类类Num,它在变量集合中包含一个名为的变量*.因此,我们有几个名称选项*:

• 如果我们希望的类型签名碰巧遵循模式a -> a -> a,对于某些类型a,那么我们可以实现Num类型类.因此,我们Num使用新实例扩展了类; 此名称的名称Prelude.*和任何别名将扩展为适用于新类型.对于矩阵,这看起来像,例如,

  instance Num Matrix where
      m * n = {- implementation goes here -}
  

• 我们可能会定义一个不同的名称*.

  m |*| n = {- implementation goes here -}
  

• 我们可以定义名称*.此名称是否定义为新类型类的一部分并不重要.如果我们什么都不做,那么将至少有两个定义*,即当前模块中的一个定义和从中隐式导入的定义Prelude.我们有各种各样的方法来处理这个问题.最简单的是显式导入Prelude,并要求*不定义名称:

  import Prelude hiding ((*))
  

  您可以选择保留隐式导入Prelude,并*在使用它的任何地方使用限定.其他解决方案也是可能的.

我希望你从中脱颖而出的要点是:这个名字*绝不特别.它只是一个由其定义的名称Prelude,并且我们可用于命名空间控制的所有工具都可用.

Answer 3

您可以通过为Matrix定义Num类的实例来实现*作为矩阵乘法.但是代码不是类型安全的:*(和其他算术运算)在矩阵中定义它们并不是完全的,因为大小不匹配或者'/'不存在逆矩阵.

至于"层次结构未精确定义" - 还有Monoid类型类,完全适用于仅定义一个操作的情况.

有太多东西需要"添加",有时以相当异乎寻常的方式(想想排列组).Haskell设计者旨在为不同的数字表示保留算术运算,并将其他名称用于更奇特的情况.