在编译时添加两个相同大小的列表

Question

在Idris中,我可以通过以下方式添加两个相同大小的向量:

module MatrixMath

import Data.Vect

addHelper : (Num n) => Vect k n -> Vect k n -> Vect k n
addHelper = zipWith (+)

在REPL上编译后:

*MatrixMath> :l MatrixMath.idr 
Type checking ./MatrixMath.idr

然后我可以用两个大小为3的向量来调用它:

*MatrixMath> addHelper [1,2,3] [4,5,6]
[5, 7, 9] : Vect 3 Integer

但是,当我尝试调用addHelper两个不同大小的向量时,它将无法编译:

*MatrixMath> addHelper [1,2,3] [1]
(input):1:20:When checking argument xs to constructor Data.Vect.:::
        Type mismatch between
                Vect 0 a (Type of [])
        and
                Vect 2 n (Expected type)

        Specifically:
                Type mismatch between
                        0
                and
                        2

我怎么能在Scala中写这个？

Answer 1

对于这种问题,无形状往往是正确的转向.Shapeless已经具有类型级数字(shapless.Nat)和具有编译时已知大小(shapeless.Sized)的集合的抽象.

实现的第一个看法可能是这样的

import shapeless.{ Sized, Nat }
import shapeless.ops.nat.ToInt
import shapeless.syntax.sized._

def Vect[A](n: Nat)(xs: A*)(implicit toInt : ToInt[n.N]) =
  xs.toVector.sized(n).get

def add[A, N <: Nat](left: Sized[Vector[A], N], right: Sized[Vector[A], N])(implicit A: Numeric[A]) =
  Sized.wrap[Vector[A], N]((left, right).zipped.map(A.plus))

它的用法:

scala> add(Vect(3)(1, 2, 3), Vect(3)(4, 5, 6))
res0: shapeless.Sized[Vector[Int],shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]] = Vector(5, 7, 9)

scala> add(Vect(3)(1, 2, 3), Vect(1)(1))
<console>:30: error: type mismatch;
  // long and misleading error message about variance
  // but at least it failed to compile

虽然这看起来很有效,但它是一个严重的缺点 - 您必须确保提供的长度和参数数量匹配,否则您将收到运行时错误.

scala> Vect(1)(1, 2, 3)
java.util.NoSuchElementException: None.get
  at scala.None$.get(Option.scala:347)
  at scala.None$.get(Option.scala:345)
  at .Vect(<console>:27)
  ... 33 elided

我们可以比这更好.您可以Sized直接使用而不是其他构造函数.此外,如果我们add使用两个参数列表定义,我们可以获得更好的错误消息(它不像Idris提供的那样好,但它可以使用):

import shapeless.{ Sized, Nat }

def add[A, N <: Nat](left: Sized[IndexedSeq[A], N])(right: Sized[IndexedSeq[A], N])(implicit A: Numeric[A]) =
  Sized.wrap[IndexedSeq[A], N]((left, right).zipped.map(A.plus))

// ...

add(Sized(1, 2, 3))(Sized(4, 5, 6))
res0: shapeless.Sized[IndexedSeq[Int],shapeless.nat._3] = Vector(5, 7, 9)

scala> add(Sized(1, 2, 3))(Sized(1))
<console>:24: error: polymorphic expression cannot be instantiated to expected type;
 found   : [CC[_]]shapeless.Sized[CC[Int],shapeless.nat._1]
    (which expands to)  [CC[_]]shapeless.Sized[CC[Int],shapeless.Succ[shapeless._0]]
 required: shapeless.Sized[IndexedSeq[Int],shapeless.nat._3]
    (which expands to)  shapeless.Sized[IndexedSeq[Int],shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]]
       add(Sized(1, 2, 3))(Sized(1))

但我们可以走得更远.Shapeless还提供了元组之间的转换Sized,所以我们可以写:

import shapeless.{ Sized, Nat }
import shapeless.ops.tuple.ToSized

def Vect[A, P <: Product](xs: P)(implicit toSized: ToSized[P, Vector]) =
  toSized(xs)

def add[A, N <: Nat](left: Sized[Vector[A], N], right: Sized[Vector[A], N])(implicit A: Numeric[A]) =
  Sized.wrap[Vector[A], N]((left, right).zipped.map(A.plus))

这工作,大小是从提供的元组推断:

scala> add(Vect(1, 2, 3), Vect(4, 5, 6))
res0: shapeless.Sized[Vector[Int],shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]] = Vector(5, 7, 9)

scala> add(Vect(1, 2, 3))(Vect(1))
<console>:27: error: type mismatch;
 found   : shapeless.Sized[scala.collection.immutable.Vector[Int],shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]]]
 required: shapeless.Sized[Vector[Int],shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]]
       add(Vect(1, 2, 3))(Vect(4, 5, 6, 7))

不幸的是,该示例中的语法仅适用于称为参数自适应的功能,其中scalac会自动将多个参数Vect转换为我们需要的元组.由于这个"功能"也可能导致非常讨厌的错误,我发现自己几乎总是禁用它-Yno-adapted-args.使用这个标志,我们必须自己明确地编写元组:

scala> Vect(1, 2, 3)
<console>:26: warning: No automatic adaptation here: use explicit parentheses.
        signature: Vect[A, P <: Product](xs: P)(implicit toSized: shapeless.ops.tuple.ToSized[P,Vector]): toSized.Out
  given arguments: 1, 2, 3
 after adaptation: Vect((1, 2, 3): (Int, Int, Int))
       Vect(1, 2, 3)
           ^
<console>:26: error: too many arguments for method Vect: (xs: (Int, Int, Int))(implicit toSized: shapeless.ops.tuple.ToSized[(Int, Int, Int),Vector])toSized.Out
       Vect(1, 2, 3)
           ^

scala> Vect((1, 2, 3))
res1: shapeless.Sized[scala.collection.immutable.Vector[Int],shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]] = Vector(1, 2, 3)

scala> add(Vect((1, 2, 3)))(Vect((4, 5, 6)))
res2: shapeless.Sized[Vector[Int],shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]] = Vector(5, 7, 9)

此外,我们只能使用长度达22,scala不支持更大的元组.

scala> Vect((1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23))
<console>:26: error: object <none> is not a member of package scala
       Vect((1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23))

那么,我们可以获得更好的语法吗？事实证明,我们可以.无形可以为我们做包装,而不是使用HList:

import shapeless.ops.hlist.ToSized
import shapeless.{ ProductArgs, HList, Nat, Sized }

object Vect extends ProductArgs {
  def applyProduct[L <: HList](l: L)(implicit toSized: ToSized[L, Vector]) =
    toSized(l)
}

def add[A, N <: Nat](left: Sized[Vector[A], N])(right: Sized[Vector[A], N])(implicit A: Numeric[A]) =
  Sized.wrap[Vector[A], N]((left, right).zipped.map(A.plus))

它有效:

scala> add(Vect(1, 2, 3))(Vect(4, 5, 6))
res0: shapeless.Sized[Vector[Int],shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]] = Vector(5, 7, 9)

scala> add(Vect(1, 2, 3))(Vect(1))
<console>:27: error: type mismatch;
 found   : shapeless.Sized[scala.collection.immutable.Vector[Int],shapeless.Succ[shapeless._0]]
 required: shapeless.Sized[Vector[Int],shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]]
       add(Vect(1, 2, 3))(Vect(1))
                              ^

scala> Vect(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
res2: shapeless.Sized[scala.collection.immutable.Vector[Int],shapeless.Succ[shapeless.Succ[... long type elided... ]]] = Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)

你可以从那里走得更远Sized,例如在你自己的课堂上

import shapeless.ops.hlist.ToSized
import shapeless.{ ProductArgs, HList, Nat, Sized }

object Vect extends ProductArgs {
  def applyProduct[L <: HList](l: L)(implicit toSized: ToSized[L, Vector]): Vect[toSized.Lub, toSized.N] =
    new Vect(toSized(l))
}

class Vect[A, N <: Nat] private (val self: Sized[Vector[A], N]) extends Proxy.Typed[Sized[Vector[A], N]] {
  def add(other: Vect[A, N])(implicit A: Numeric[A]): Vect[A, N] =
    new Vect(Sized.wrap[Vector[A], N]((self, other.self).zipped.map(A.plus)))
}

// ...

scala> Vect(1, 2, 3) add Vect(4, 5, 6)
res0: Vect[Int,shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]] = Vector(5, 7, 9)

scala> Vect(1, 2, 3) add Vect(1)
<console>:26: error: type mismatch;
 found   : Vect[Int,shapeless.Succ[shapeless._0]]
 required: Vect[Int,shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless._0]]]]
       Vect(1, 2, 3) add Vect(1)

从本质上讲,所有归结为使用Sized和Nat类型约束.

Answer 2

Shapeless可以帮助您：

import shapeless._
import syntax.sized._

def row(cols : Seq[String]) = cols.mkString("\"", "\", \"", "\"")

def csv[N <: Nat](hdrs : Sized[Seq[String], N], rows : List[Sized[Seq[String], N]]) =
    row(hdrs) :: rows.map(row(_))

val hdrs = Sized("Title", "Author") // Sized[IndexedSeq[String], _2]
val rows = List(                  // List[Sized[IndexedSeq[String], _2]]
  Sized("Types and Programming Languages", "Benjamin Pierce"),
  Sized("The Implementation of Functional Programming Languages", "Simon Peyton-Jones")
)

 // hdrs and rows statically known to have the same number of columns
val formatted = csv(hdrs, rows)

请注意该方法如何通过csv进行约束，与您在示例中通过 进行约束的方式相同。SizedN <: NatNum n

我从 Shapeless Examples复制了这段代码，如果它不按原样编译，我很可能会错过一些东西。