Scala Shapeless Code for Project Euler # 2

Question

Zacząłem od mojego Shapeless rozwiązania do Project Euler Problem #2.

mogę podsumować wspólnie wszystkie parzyste FIBS do Nth choćby jednego z tym kodem:

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

Teraz mogę zrobić:

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

ten sposób uzyskać wszystkie nawet FIBS: Zaczynam od sekwencji 2, 3, ... i podsumowuję co trzecią liczbę Fibonacciego.

Teraz utknąłem. Chciałbym mieć funkcjonalność podobną do takeWhile, więc mogę napisać funkcję, która akceptuje limit i zwraca sumę moich nawet kłamstw, których warunki nie przekraczają tego limitu. Jakieś pomysły?

Oto mój wysiłek na co starałem dotąd:

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

Ideą było rekursywnie odjąć limitu przez wyjście aż wyjściowa jest mniejsza niż limit. Mogę zdecydowanie poczuć, że coś jest nie tak. Nie sądzę, żebym potrzebował Diff w ogóle. Próbowałem też innych odmian, ale wciąż utknąłem. Kiedy mogę skompilować, pojawia się błąd diverging implicit expansion for fibsN.

EDIT:

Myślałam może uda mi się skonstruować HList z moich Fibs i korzystania Selector z typeclass kwantyfikatorów symulować takeWhile. Myśli?

Answer 1

Uważam, że najlepszym sposobem podejścia się do tego rodzaju problemu jest przebadanie się przez liczby naturalne podczas myślenia o informacjach, które muszę śledzić.

Na papierze bym użyć czegoś takiego:

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 

Tutaj C śledzi aktualny numer w sekwencji Fibonacciego-t j. największy, mniejszy lub równy N. P to numer Fibonacciego wcześniej, a L jest bieżącą sumą wartości równych, które widzieliśmy do tej pory.

Możemy przetłumaczyć to do klasy typu:

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

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

Obecnie istnieją cztery przypadki musimy obsłużyć. Pierwszy dam ten, który musi mieć najniższy priorytet w celu uzyskania niejawny rozdzielczości prawo:

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

Jest to przypadek, w którym Succ[N] nie jest liczbą Fibonacciego. Nie wymaga od nas aktualizacji żadnej z wartości, które śledzimy. Kolejna sprawa jest trochę bardziej skomplikowana:

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

Jest to przypadek, w którym Succ[N] jest nieparzysta liczba Fibonacciego. W takim przypadku musimy zaktualizować C i P, ale nie L.

Nasza ostatnia obudowa Succ[N] to taka, w której Succ[N] to parzysta liczba Fibonacciego. dam go tutaj z przypadku bazowego:

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 
} 

Wreszcie możemy zdefiniować klasę pomocniczą, że będzie to łatwiejsze do sprawdzenia naszej pracy:

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] 

, a następnie:

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) 

Ostatnia linia zajmuje około dwudziestu sekund, aby skompilować się na moim komputerze, ale działa.