欧拉项目 #2 的 Scala 无形代码

Question

我已经开始 Project Euler Problem #2 的 Shapeless 解决方案。

我可以用这段代码将所有偶数谎言汇总到 Nth偶数：

import shapeless._, nat._, ops.nat.Sum

trait Fibonacci[N <: Nat] { type Out <: Nat }

object Fibonacci {
  type Aux[N <: Nat, Out0 <: Nat] = Fibonacci[N] { type Out = Out0 }

  def apply[N <: Nat](i: Nat)(implicit fib: Aux[i.N, N], n: Witness.Aux[N]):N = n.value

  implicit val fib0 = new Fibonacci[_0] { type Out = _2 }
  implicit val fib1 = new Fibonacci[_1] { type Out = _3 }

  implicit def fibN[I <: Nat, L <: Nat, M <: Nat](implicit l: Aux[I, L],
                                                  m: Aux[Succ[I], M],
                                                  sum: Sum[L, M]) =
    new Fibonacci[Succ[Succ[I]]] { type Out = sum.Out }
}

trait Fibs[N <: Nat] { type Out <: Nat }

object Fibs {
  type Aux[N <: Nat, Out0 <: Nat] = Fibs[N] { type Out = Out0 }

  def apply[N <: Nat](i: Nat)(implicit fibs: Aux[i.N, N], n: Witness.Aux[N]):N = n.value

  implicit def fibs0(implicit f: Fibonacci[_0]) = new Fibs[_0] { type Out = f.Out }

  implicit def fibsN[N <: Nat, R <: Nat, Z <: Nat](implicit fib: Fibonacci.Aux[Succ[Succ[Succ[N]]], R],
                                                   fibs: Aux[N, Z],
                                                   sum: Sum[R, Z]) =
    new Fibs[Succ[N]] {
      type Out = sum.Out
    }
}

现在我可以做到：

val (evenFibs0, evenFibs1) = (Fibs(0), Fibs(1))
typed[_2](evenFibs0)
typed[_10](evenFibs1)

这就是我得到所有偶数谎言的方式：我从序列 2、3、... 开始，然后对每三个斐波那契数求和。

现在，我卡住了。我想要具有类似于 takeWhile 的功能，因此我可以编写一个函数来接受 limit 和 returns 我的偶数谎言的总和，其条款不超过该限制。有什么想法吗？

这是我迄今为止所做的努力：

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

trait LowPriorityFibs3 {
  type Aux[N <: Nat, M <: Nat, Out0 <: Nat] = EvenFibsWithLimit[N, M] { type Out = Out0 }

  implicit def fibs0[M <: Nat] = new EvenFibsWithLimit[_0, M] { type Out = _0 }

  implicit def fibsGT[N <: Nat, M <: Nat, O <: Nat](implicit f: EvenFibsWithLimit[N, M],
                                                    fib: Fibs.Aux[N, O],
                                                    l: ops.nat.LT[M, O]) = f
}

object EvenFibsWithLimit extends LowPriorityFibs3 {
  def apply[N <: Nat, O <: Nat](limit: Nat)(implicit fibs: Aux[N, limit.N, O],
                                            o: Witness.Aux[O]): O = o.value

  implicit def fibsN[N <: Nat, M <: Nat, O <: Nat](implicit f: EvenFibsWithLimit[N, M],
                                                   f2: Fibs.Aux[Succ[N], O],
                                                   d: ops.nat.Diff[M, O]) =
    new EvenFibsWithLimit[Succ[N], d.Out] {
      type Out = O
    }
}

想法是递归地用输出减去限制，直到输出小于限制。我绝对能闻到不对劲的味道。我认为我根本不需要 Diff ..我也尝试了一些其他变体，但我一直被卡住了。编译时，出现错误 diverging implicit expansion for fibsN.

编辑：

我在想也许我可以构建我的 Fibs 的 HList，并使用带有谓词类型类的 Selector 来模拟 takeWhile。想法？

Answer 1

我发现解决此类问题的最佳方法是在考虑我需要跟踪的信息的同时单步执行自然数。

在纸上我会使用这样的东西：

N  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
C  1  2  3  3  5  5  5  8  8  8  8  8 13 13 13
P  1  1  2  2  3  3  3  5  5  5  5  5  8  8  8
L  0  2  2  2  2  2  2 10 10 10 10 10 10 10 10

此处 C 跟踪斐波那契数列中的当前数字——即小于或等于 N 的最大的那个。 P 是之前的斐波那契数，L 是我们目前看到的偶数的当前总和。

我们可以把它翻译成一个类型 class:

import shapeless._, ops.nat.{ Mod, Sum }, nat.{ _0, _1, _2 }

trait EvenFibs[N <: Nat] {
  type L <: Nat
  type C <: Nat
  type P <: Nat
}

现在我们需要处理四种情况。首先，我将给出需要具有最低优先级的优先级以获得正确的隐式解决方案：

trait LowPriorityEvenFibs {
  type Aux[N <: Nat, L0 <: Nat, C0 <: Nat, P0 <: Nat] = EvenFibs[N] {
    type L = L0
    type C = C0
    type P = P0
  }

  implicit def ef3[N <: Nat](implicit
    ef: EvenFibs[N]
  ): Aux[Succ[N], ef.L, ef.C, ef.P] = new EvenFibs[Succ[N]] {
    type L = ef.L
    type C = ef.C
    type P = ef.P
  }
}

这是 Succ[N] 不是斐波那契数的情况。它不需要我们更新我们正在跟踪的任何值。下一个案例有点复杂：

trait MidPriorityEvenFibs extends LowPriorityEvenFibs {
  implicit def ef2[N <: Nat, L0 <: Nat, PP <: Nat, P0 <: Nat](implicit
    ef: Aux[N, L0, P0, PP],
    sum: Sum.Aux[PP, P0, Succ[N]]
  ): Aux[Succ[N], L0, Succ[N], P0] = new EvenFibs[Succ[N]] {
    type L = L0
    type C = Succ[N]
    type P = P0
  }
}

这是 Succ[N] 奇数斐波那契数的情况。在这种情况下，我们需要更新 C 和 P，而不是 L.

我们最后一个 Succ[N] 案例是 Succ[N] 是一个偶数斐波那契数。我将在这里给出基本情况：

object EvenFibs extends MidPriorityEvenFibs {
  implicit def ef0: Aux[_0, _0, _1, _1] = new EvenFibs[_0] {
    type L = _0
    type C = _1
    type P = _1
  }

  implicit def ef1[N <: Nat, L <: Nat, PP <: Nat, P0 <: Nat](implicit
    ef: Aux[N, L, P0, PP],
    sum: Sum.Aux[PP, P0, Succ[N]],
    mod: Mod.Aux[Succ[N], _2, _0],
    current: Sum[Succ[N], L]
  ): Aux[Succ[N], current.Out, Succ[N], P0] = new EvenFibs[Succ[N]] {
    type L = current.Out
    type C = Succ[N]
    type P = P0
  }

  def apply[N <: Nat](implicit ef: EvenFibs[N]): Aux[N, ef.L, ef.C, ef.P] = ef
}

最后我们可以定义一个帮助程序 class 来更容易地检查我们的工作：

class ComputeHelper[N <: Nat] {
  def value[L <: Nat, C <: Nat, P <: Nat](implicit
    ef: EvenFibs.Aux[N, L, C, P],
    wit: Witness.Aux[L]
  ): L = wit.value
}

def compute[N <: Nat]: ComputeHelper[N] = new ComputeHelper[N]

然后：

test.typed[_0](compute[_0].value)
test.typed[_0](compute[_1].value)
test.typed[_2](compute[_2].value)
test.typed[_2](compute[nat._3].value)
test.typed[_2](compute[nat._4].value)
test.typed[_2](compute[nat._5].value)
test.typed[_2](compute[nat._6].value)
test.typed[_2](compute[nat._7].value)
test.typed[nat._10](compute[nat._8].value)
test.typed[nat._10](compute[nat._9].value)

最后一行在我的机器上编译需要大约 20 秒，但它有效。

欧拉项目 #2 的 Scala 无形代码

Scala Shapeless Code for Project Euler #2

scala

type-level-computation

shapeless