Scala Shapeless Proje Euler Kodu # 2

Question

Project Euler Problem #2 numaralı My Shapeless çözümüme başladım.

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

Şimdi Yapabileceğim:

ben bu kodla bile Nth bir taneye kadar hep birlikte hatta beyaz yalanlar özetleyebilirim

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

Bu benim bütün çift beyaz yalanlar almak nasıl: 2., 3. sıra ile başlıyorum ve her üç Fibonacci numarasını toplarım.

Şimdi sıkışmış durumdayım. takeWhile'a benzer bir işlevselliğe sahip olmak istiyorum, bu yüzden limit kabul eden bir işlevi yazabilirim ve şartları bu sınırı aşmayan çift fib'lerimi döndürürüm. Herhangi bir fikir?

İşte ben bugüne kadar ne denedim benim çaba:

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

fikri çıktı sınırından daha az olana kadar yinelemeli çıkışı ile sınırını çıkarmak amaçlanmıştır. Kesinlikle bir şeyin kokusunu alabiliyorum. Hiç Diff'a ihtiyacım olduğunu sanmıyorum. Diğer bazı varyasyonları da denedim, ama takılmaya devam ediyorum. Düşündüm de belki

Ben benim Fibs bir HList inşa ve takeWhile taklit eden bir yüklem typeclass ile Selector kullanabilirsiniz: Ben derlemek, ben hatayı diverging implicit expansion for fibsN.

EDIT olsun. Düşünceler?

Answer 1

Bu tür bir probleme yaklaşmanın en iyi yolunun, takip etmem gereken bilgileri düşünürken doğal sayılar boyunca ilerlemektir.

Kağıt üzerinde böyle bir şey kullanmak istiyorum: Burada C

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 

Fibonacci dizisi-yani mevcut sayısını izler. N'dan daha az veya eşit olan en büyük olanı. P bundan önceki Fibonacci numarasıdır ve L şimdiye kadar gördüğümüzün bile geçerli toplamıdır.

Biz bir tür sınıfa bu çevirebilir:

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

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

Şimdi işlemek için gereken dört durum vardır.

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

Bu Succ[N] Fibonacci sayı değil böyledir: Önce örtülü çözünürlük hakkını almak için en düşük önceliğe sahip olması gerekir birini vereceğiz. Takip ettiğimiz değerleri güncellememizi gerektirmez.

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

Bu Succ[N] tek Fibonacci sayısıdır durumdur: Bir sonraki örnek biraz daha karmaşıktır. Bu durumda, C ve P'u güncellememiz gerekir, ancak L.

Son Succ[N] durumumuz, Succ[N] numaralı numaranın bir Fibonacci numarasıdır.

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 
} 

Son olarak biz bir yardımcı sınıf tanımlayabilirsiniz daha kolay çalışmalarımızı kontrol etmek yapacaktır: o zaman

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] 

Ve:

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) 

Ben baz vaka ile burada vereceğiz

Son satır, makinemi derlemek için yaklaşık yirmi saniye sürer, ancak çalışır.