项目欧拉斯卡拉无形代码＃1

Question

我是新来的无形，一直在尝试一些类型的水平编程。我把​​作为我的第一个挑战。

我开始编写正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) 
} 

接下来，我想改变的功能，使我不需要手动创建列表。相反，它接受一个“限制”作为像普通斯卡拉代码一样的参数。我想出了这个：

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。我注意到有一个unfold example in the shapeless git，但它的复杂性此刻逃脱了我。

Answer 1

我觉得在归纳上（至少在类型级别）考虑这个问题要容易一些。首先，我们可以定义一个辅助类型的类返回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范围，然后使用IfMultiple与Poly2进行折叠。你也可以定义一个IsMultiple类型的类，只是目击N是M中的一个数字的倍数 - 我的第一个快速尝试做到了这一点，但我碰到了含糊不清的问题，所以我去了上面的类似版本。然而，这里的实现相当简单，除非你有其他的应用程序，例如Nat范围，我认为这是一个非常合理的解决方案。