Codice senza forma Scala per Project Euler # 2

Question

Ho iniziato la mia soluzione di Shapeless a Project Euler Problem #2.

Posso riassumere insieme tutti i anche frottole fino al Nth anche uno con questo codice:

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

Ora posso fare:

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

Questo è come ottenere tutti anche frottole: Comincio con la sequenza 2, 3, ..., e riassumo ogni terzo numero di Fibonacci.

Ora, sono bloccato. Mi piacerebbe avere funzionalità simili a takeWhile, quindi posso scrivere una funzione che accetta uno limit e restituisce la somma delle mie fib addirittura pari i cui termini non superano tale limite. Qualche idea?

Ecco il mio sforzo per quello che ho provato finora:

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

L'idea era quella di sottrarre in modo ricorsivo il limite per l'uscita fino a quando l'uscita è inferiore al limite. Posso sicuramente sentire l'odore di qualcosa. Non penso di aver bisogno del Diff .. Ho provato anche altre varianti, ma continuo a rimanere bloccato. Quando compilo, ottengo l'errore diverging implicit expansion for fibsN.

EDIT:

Stavo pensando forse posso costruire un HList della mia Fibs, e utilizzare Selector con un typeclass predicato per simulare un takeWhile. Pensieri?

Answer 1

Trovo che il modo migliore per affrontare questo tipo di problema è quello di passare attraverso i numeri naturali mentre si pensa alle informazioni di cui ho bisogno per tenere traccia di.

Sulla carta userei qualcosa di simile:

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 

Qui C tracce il numero corrente nella sequenza-cioè di Fibonacci. il più grande che è inferiore o uguale a N. P è il numero di Fibonacci prima di questo, e L è la somma corrente di quelli pari che abbiamo visto finora.

possiamo tradurre questo in una classe del tipo:

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

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

Ora ci sono quattro casi di cui abbiamo bisogno per gestire. In primo luogo darò quello che ha bisogno di avere la priorità più bassa, al fine di ottenere il giusto risoluzione implicita:

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

Questo è il caso in cui Succ[N] non è un numero di Fibonacci. Non ci richiede di aggiornare nessuno dei valori di cui teniamo traccia. Il caso successivo è un po 'più complessa:

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

Questo è il caso in cui Succ[N] è un numero di Fibonacci dispari. In questo caso è necessario aggiornare C e P, ma non L.

La nostra ultima custodia Succ[N] è quella in cui Succ[N] è un numero di Fibonacci pari. Darò qui con il caso base:

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 
} 

Infine possiamo definire una classe di supporto che renderà più facile per verificare il nostro lavoro:

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] 

E poi:

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) 

L'ultima riga impiega circa venti secondi per essere compilata sulla mia macchina, ma funziona.