Scala bezkształtny kod dla projektu Euler # 1

Question

Jestem nowy, bezkształtny i próbowałem ćwiczyć niektóre poziomy programowania. Zrobiłem Problem #1 from Project Euler jako moje pierwsze wyzwanie.

zacząłem pisząc regularne kod 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) 
} 

Potem wymyślił ten pracuje realizacja bezkształtne użyciu 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) 
} 

Następnie chciałem zmienić funkcję tak, że nie trzeba ręcznie tworzyć listy. Zamiast tego akceptuje "limit" jako argument, jak zwykły kod scala. Wpadłem na to:

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! 
} 

Utknąłem tutaj. Kompilator mówi mi, że znalazł _0. Chyba odbiera instancję od def default.

Wszelkie wskazówki, jak mogę to naprawić? Mam wrażenie, że moja strategia rozwiązania tego problemu może być trochę dziwna. Wszelkie wskazówki na temat tego, w jaki sposób mogę uczynić ten bezkształtny kod bardziej idiomatycznym, są bardzo doceniane.

Moja oryginalna strategia polegała na stworzeniu hylomorfizmu. Zauważyłem, że jest unfold example in the shapeless git, ale jego złożoność ucieka mi w tej chwili.

Answer 1

Uważam, że nieco łatwiej jest myśleć o tym problemie indukcyjnie (przynajmniej na poziomie typu). Po pierwsze możemy zdefiniować klasę typu pomocnika, który zwraca N jeśli N jest wielokrotnością jednego z numerów w M i _0 inaczej:

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 
    } 
} 

A teraz musimy tylko klasę typu zsumować wszystkie te wartości z _0 do 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 
    } 
} 

A potem skończymy:

import nat._, test.typed 

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

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

Który kompiluje zgodnie z oczekiwaniami.

Warto zauważyć, że istnieją inne sposoby rozwiązania tego problemu. Można utworzyć klasę typów, która zapewni zakresy Nat, a następnie spasuj ją za pomocą Poly2, używając IfMultiple. Możesz również zdefiniować klasę typu IsMultiple, która świadczy o tym, że N jest wielokrotnością jednej z liczb w M - moja pierwsza szybka próba to zrobiła, ale napotkałem problemy z niejednoznacznością, więc poszedłem z podobną wersją powyżej. Jednak implementacja jest dość prosta i jeśli nie masz innych aplikacji dla np. Nat zakresy, myślę, że to całkiem rozsądne rozwiązanie.