Code Scala Shapeless pour Project Euler # 2

Question

J'ai commencé ma solution Shapeless à Project Euler Problem #2.

Je peux résumer ensemble tous les même bobards jusqu'à la Nth même un avec ce 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 
    } 
} 

Maintenant, je peux faire:

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

Voilà comment je reçois tous les même bobards: Je commence par la séquence 2, 3, ..., et je résume tous les trois nombres de Fibonacci.

Maintenant, je suis coincé. Je voudrais avoir des fonctionnalités similaires à takeWhile, donc je peux écrire une fonction qui accepte un limit et retourne la somme de mes fibs pairs dont les termes ne dépassent pas cette limite. Des idées?

Voici mon effort pour ce que j'ai essayé jusqu'à présent:

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'idée était de soustraire récursive la limite de la sortie jusqu'à ce que la sortie est inférieure à la limite. Je peux définitivement sentir que quelque chose est éteint. Je ne pense pas avoir besoin de Diff du tout .. J'ai aussi essayé d'autres variations, mais je reste coincé. Quand je compile, je reçois l'erreur diverging implicit expansion for fibsN.

EDIT:

Je pensais peut-être que je peux construire une HList de mon Fibs, et utiliser Selector avec une classe de types de prédicats pour simuler un takeWhile. Pensées?

Answer 1

Je trouve que la meilleure façon d'aborder ce genre de problème est de parcourir les nombres naturels tout en réfléchissant à l'information dont j'ai besoin de suivre.

Sur le papier j'utiliser quelque chose comme ceci:

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 

Ici C Indique le nombre actuel dans la séquence i.e. Fibonacci. le plus grand qui est inférieur ou égal à N. P est le nombre de Fibonacci avant cela, et L est la somme actuelle des mêmes que nous avons vu jusqu'à présent.

Nous pouvons traduire cela en une classe de type:

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

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

Maintenant il y a quatre cas, nous devons gérer. D'abord, je vais vous donner celui qui doit avoir la priorité la plus basse afin d'obtenir la résolution implicite droite:

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

Tel est le cas où Succ[N] est pas un nombre de Fibonacci. Cela ne nous oblige pas à mettre à jour les valeurs que nous suivons. Le cas suivant est un peu plus complexe:

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

Tel est le cas où Succ[N] est un nombre de Fibonacci impair. Dans ce cas, nous devons mettre à jour C et P, mais pas L.

Notre dernier cas Succ[N] est celui où Succ[N] est un nombre Fibonacci pair. Je donnerai ici avec le cas de 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 
} 

nous pouvons enfin définir une classe d'aide qui sera plus facile de vérifier notre travail:

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] 

Et puis:

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) 

La dernière ligne prend environ vingt secondes à compiler sur ma machine, mais cela fonctionne.