Codice senza forma di Scala per Project Eulero # 1

Question

Sono nuovo di informi e ho provato a praticare una programmazione a livello di tipo. Ho preso Problem #1 from Project Euler come prima sfida.

ho iniziato scrivendo regolare codice 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) 
} 

Poi, mi si avvicinò con questo lavoro implementazione informe utilizzando 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) 
} 

successiva, ho voluto cambiare la funzione in modo che io non è necessario creare manualmente un elenco. Invece accetta un "limite" come argomento come il normale codice di scala. Mi sono inventato questo:

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

Sono rimasto bloccato qui. Il compilatore mi sta dicendo che ha trovato _0. Immagino che stia raccogliendo l'istanza da def default.

Qualche consiglio su come posso risolvere questo problema? Ho la sensazione che la mia strategia per risolvere questo problema potrebbe essere un po 'strana anche. Ogni suggerimento su come posso rendere questo codice informe più idiomatico è molto apprezzato.

La mia strategia originale era di creare un hylomorphism. Ho notato che c'è uno unfold example in the shapeless git ma la sua complessità mi sfugge al momento.

Answer 1

Trovo un po 'più facile pensare a questo problema in modo induttivo (almeno a livello di testo). In primo luogo siamo in grado di definire una classe tipo di supporto che restituisce N se N è un multiplo di uno dei numeri in M, e _0 altrimenti:

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

E ora abbiamo solo bisogno di una classe tipo di sommare tutti questi valori da _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 
    } 
} 

E poi abbiamo finito:

import nat._, test.typed 

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

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

Che compila come previsto.

Vale la pena notare che esistono altri modi per risolvere questo problema. È possibile creare una classe di tipi che fornisca intervalli di Nat e quindi piegarlo con uno Poly2 utilizzando IfMultiple. Si potrebbe anche definire una classe di tipo IsMultiple che testimonia semplicemente che N è un multiplo di uno dei numeri in M - il mio primo tentativo rapido ha fatto questo, ma ho incontrato problemi di ambiguità, quindi sono andato con la versione simile sopra. L'implementazione qui è abbastanza semplice, tuttavia, e a meno che tu non abbia altre applicazioni per es. Nat intervalli, penso che sia una soluzione abbastanza ragionevole.