问题 Project Euler＃1的Scala无形代码

我是新手，一直在尝试练习某种类型的编程。我拿了项目欧拉的问题＃1 作为我的第一个挑战。

我开始编写常规的scala代码：

object ProjectEuler1 {
  def e1(limit: Int) = (1 until limit).foldLeft(0) {
    case (acc, x) if x % 3 * x % 5 == 0 => acc + x
    case (acc, _)                       => acc
  }
  val out = e1(10)
  assert(out == 23)
}

然后，我想出了这个工作无形的实现 poly：

object ProjectEuler1Shapeless extends App {
  import shapeless._
  import nat._
  import ops.nat._
  import poly._
  import test.typed

  trait eLP extends Poly1 {
    implicit def default[A <: Nat] = at[A] { _ => _0 }
  }
  object e extends eLP {
    implicit def match3[A <: Nat](implicit ev: Mod.Aux[A, _3, _0]) = at[A](identity)
    implicit def match5[A <: Nat](implicit ev: Mod.Aux[A, _5, _0]) = at[A](identity)
  }

  object sum extends Poly2 {
    implicit def sum[A <: Nat, B <: Nat, Z <: Nat](implicit s: Sum.Aux[A, B, Z],
                                                   z: Witness.Aux[Z]) =
      at[A, B] { (_, _) => z.value }
  }

  type _23 = Succ[_22]
  val l = _1 :: _2 :: _3 :: _4 :: _5 :: _6 :: _7 :: _8 :: _9 :: HNil
  val out = l.map(e).foldLeft(_0)(sum)
  typed[_23](out)
}

接下来，我想更改功能，以便我不需要手动创建列表。相反，它接受“限制”作为参数，如常规的scala代码。我想出了这个：

object ProjectEuler1Shapeless2 extends App {
  import shapeless._
  import nat._
  import ops.nat._
  import test.typed

  class E1[I <: Nat, N <: Nat]
  trait ELP0 {
    implicit def default[I <: Nat, M <: Nat] = new E1[I, _0]
  }
  trait ELP1 extends E1LP0 {
    implicit def match3[A <: Nat](implicit ev: Mod.Aux[A, _3, _0]) = new E1[A, A]
    implicit def match5[A <: Nat](implicit ev: Mod.Aux[A, _5, _0]) = new E1[A, A]
  }
  object E1 extends E1LP1 {
    implicit def combine[I <: Nat, L <: Nat, M <: Nat](implicit e1: E1[I, L],
                                                       m: E1[Succ[I], M],
                                                       sum: Sum[L, M]) =
      new E1[Succ[Succ[I]], sum.Out]
  }
  def e1[N <: Nat](limit: Nat)(implicit e: E1[limit.N, N], w: Witness.Aux[N]): N = w.value

  val f1 = e1(1)
  typed[_0](f1)

  val f2 = e1(2)
  typed[_0](f2)

  val f3 = e1(3)
  typed[_3](f3) // Does not compile!
}

我被困在这里了。编译器告诉我它找到了 _0。我猜它正在从中获取实例 def default。

有关如何解决此问题的任何提示？我有一种感觉，我解决这个问题的策略也可能有点奇怪。关于如何使这个无形代码更加惯用的任何指示都非常感谢。

我最初的策略是创造一个hylomorphism。我注意到有一个在无形的git中展开的例子但它的复杂性目前让我无法逃脱。

11824

2017-07-21 16:29

起源

答案:

我发现在感应上（至少在类型级别）思考这个问题要容易一些。首先，我们可以定义一个返回的辅助类型类 N 如果 N 是其中一个数字的倍数 M，和 _0 除此以外：

import shapeless._, nat._0, ops.nat.Mod

trait IfMultiple[N <: Nat, M <: HList] { type Out <: Nat }

trait LowPriorityIfMultiple {
  type Aux[N <: Nat, M <: HList, Out0 <: Nat] = IfMultiple[N, M] {
    type Out = Out0
  }

  implicit def isMultiple1[N <: Nat, H <: Nat, T <: HList](implicit
    ifMultiple: IfMultiple[N, T]
  ): Aux[N, H :: T, ifMultiple.Out] = new IfMultiple[N, H :: T] {
    type Out = ifMultiple.Out
  }
}

object IfMultiple extends LowPriorityIfMultiple {
  implicit def ifMultiple0[N <: Nat]: Aux[N, HNil, _0] =
    new IfMultiple[N, HNil] {
      type Out = _0
    }

  implicit def ifMultiple2[N <: Nat, H <: Nat, T <: HList](implicit
    mod: Mod.Aux[N, H, _0]
  ): Aux[N, H :: T, N] = new IfMultiple[N, H :: T] {
    type Out = N
  }
}

现在我们只需要一个类型类来添加所有这些值 _0 至 N - _1：

import nat._1, ops.nat.Sum

trait SumOfMultiples[N <: Nat, M <: HList] extends DepFn0 { type Out <: Nat }

object SumOfMultiples {
  type Aux[N <: Nat, M <: HList, Out0 <: Nat] = SumOfMultiples[N, M] {
    type Out = Out0
  }

  def apply[N <: Nat, M <: HList](implicit
    som: SumOfMultiples[N, M]
  ): Aux[N, M, som.Out] = som

  implicit def sum0[M <: HList]: Aux[_1, M, _0] =
    new SumOfMultiples[_1, M] {
      type Out = _0
      def apply(): _0 = _0
    }

  implicit def sumN[P <: Nat, M <: HList, NV <: Nat, PT <: Nat, NT <: Nat](implicit
    ifMultiple: IfMultiple.Aux[P, M, NV],
    som: Aux[P, M, PT],
    sum: Sum.Aux[NV, PT, NT],
    wit: Witness.Aux[NT]
  ): Aux[Succ[P], M, NT] = new SumOfMultiples[Succ[P], M] {
    type Out = NT
    def apply(): NT = wit.value
  }
}

然后我们完成了：

import nat._, test.typed

val result = SumOfMultiples[_10, _3 :: _5 :: HNil]

typed[Succ[_22]](result())

哪个编译符合预期。

值得注意的是，还有其他方法可以解决这个问题。您可以创建一个可提供的类型类 Nat 范围，然后用a折叠 Poly2 运用 IfMultiple。你也可以定义一个 IsMultiple 类型类只是见证 N 是其中一个数字的倍数 M - 我第一次快速尝试这样做了，但我遇到了歧义问题，所以我选择了上面的类似版本。这里的实现相当简单，除非你有其他应用程序，例如 Nat 范围，我认为这是一个非常合理的解决方案。

2017-07-21 21:54

这很漂亮。正是我想要的，而且非常有教育意义。关于如何用Shapeless模仿思维的一个很好的教训。我一定会用这个答案作为解决未来问题的参考。 - beefyhalo

不能 sumN 使用 P 和 Succ[P] 代替 Succ[P] 和 Succ[Succ[P]] 还是有什么我想念的？ - beefyhalo

@beefyhalo啊，这是可能的 - 在今天的会议上写这篇文章。 - Travis Brown

哇！照常。特拉维斯，你有什么无形的问题吗？ - Peter Schmitz

答案:

import shapeless._, nat._0, ops.nat.Mod

trait IfMultiple[N <: Nat, M <: HList] { type Out <: Nat }

trait LowPriorityIfMultiple {
  type Aux[N <: Nat, M <: HList, Out0 <: Nat] = IfMultiple[N, M] {
    type Out = Out0
  }

  implicit def isMultiple1[N <: Nat, H <: Nat, T <: HList](implicit
    ifMultiple: IfMultiple[N, T]
  ): Aux[N, H :: T, ifMultiple.Out] = new IfMultiple[N, H :: T] {
    type Out = ifMultiple.Out
  }
}

object IfMultiple extends LowPriorityIfMultiple {
  implicit def ifMultiple0[N <: Nat]: Aux[N, HNil, _0] =
    new IfMultiple[N, HNil] {
      type Out = _0
    }

  implicit def ifMultiple2[N <: Nat, H <: Nat, T <: HList](implicit
    mod: Mod.Aux[N, H, _0]
  ): Aux[N, H :: T, N] = new IfMultiple[N, H :: T] {
    type Out = N
  }
}