項目歐拉斯卡拉無形代碼＃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範圍，我認爲這是一個非常合理的解決方案。