Scala Formloser Code für Projekt Euler # 2

Question

Ich habe mit meiner Shapeless-Lösung zu Project Euler Problem #2 begonnen.

kann ich Summe zusammen, alle noch fibs bis zum Nth auch ein mit diesem Code:

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

Jetzt kann ich tun:

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

Dies ist, wie ich alles selbst fibs erhalten: Ich beginne mit der Sequenz 2, 3, ... und fasse jede dritte Fibonacci-Zahl zusammen.

Jetzt bin ich fest. Ich hätte gerne eine ähnliche Funktionalität wie takeWhile, also kann ich eine Funktion schreiben, die eine limit akzeptiert und die Summe meiner geraden Flops zurückgibt, deren Bedingungen diese Grenze nicht überschreiten. Irgendwelche Ideen?

Hier ist meine Mühe für das, was ich bisher ausprobiert habe:

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

Die Idee, die Grenze durch die Ausgabe rekursiv zu subtrahieren war, bis der Ausgang kleiner als der Grenzwert ist. Ich kann definitiv riechen, dass etwas aus ist. Ich glaube nicht, dass ich überhaupt Diff brauche. Ich habe auch einige andere Varianten ausprobiert, aber ich bleibe stecken. Wenn ich kompilieren, erhalte ich die Fehler diverging implicit expansion for fibsN.

EDIT:

Ich dachte, vielleicht kann ich ein HList meiner Fibs, konstruieren und Selector mit einem Prädikat typeclass verwenden, um eine takeWhile zu simulieren. Gedanken?

Answer 1

Ich finde, dass der beste Weg, um diese Art von Problem zu nähern ist, durch die natürlichen Zahlen zu gehen, während über die Informationen nachzudenken, die ich verfolgen muss.

Auf dem Papier würde ich so etwas wie folgt verwenden:

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 

Hier C verfolgt die aktuelle Nummer in der Fibonacci-Folge-d.h. der größte, der kleiner oder gleich N ist. P ist die Fibonacci-Nummer davor, und L ist die aktuelle Summe der geraden, die wir bisher gesehen haben.

Wir können diese in eine Typklasse übersetzen:

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

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

Jetzt gibt es vier Fälle, die wir behandeln müssen. Zunächst werde ich den einen geben, der die niedrigste Priorität hat, um muss die implizite Auflösung richtig zu machen:

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

Dies ist der Fall, in der Succ[N] keine Fibonacci-Zahl ist. Es erfordert nicht, dass wir irgendeinen der Werte aktualisieren, die wir verfolgen. Der nächste Fall ist ein wenig komplexer:

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

Dies ist der Fall, in dem Succ[N] eine ungerade Fibonacci-Zahl. In diesem Fall müssen wir C und P, aber nicht L aktualisieren.

Unser letzter Succ[N] Fall ist der, wo Succ[N] eine gerade Fibonacci-Nummer ist. Ich werde es hier mit dem Basisfall:

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 
} 

Schließlich können wir eine Hilfsklasse definieren, die es einfacher zu überprüfen unsere Arbeit machen:

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] 

Und dann:

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) 

Die letzte Zeile dauert etwa zwanzig Sekunden, um auf meinem Computer zu kompilieren, aber es funktioniert.