I've started on my Shapeless solution to Project Euler Problem #2.
I can sum together all the even fibs up to the Nth even one with this 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
}
}
Now I can do:
val (evenFibs0, evenFibs1) = (Fibs(0), Fibs(1))
typed[_2](evenFibs0)
typed[_10](evenFibs1)
This is how I get all even fibs: I start with the sequence 2, 3, ... , and I sum up every third Fibonacci number.
Now, I am stuck. I'd like to have functionality similar to takeWhile, so I can write a function that accepts a limit and returns the sum of my even fibs whose terms don't exceed that limit. Any ideas?
Here's my effort for what I've tried so far:
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
}
}
The idea was to recursively subtract the limit by the output until the output is less than the limit. I can definitely smell something is off. I don't think I need Diff at all.. I've tried some other variations too, but I keep getting stuck. When I compile, I get the error diverging implicit expansion for fibsN.
EDIT:
I was thinking maybe I can construct an HList of my Fibs, and use Selector with a predicate typeclass to simulate a takeWhile. Thoughts?
I find that the best way to approach this kind of problem is to step through the natural numbers while thinking about the information I need to keep track of.
On paper I'd use something like this:
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
Here C tracks the current number in the Fibonacci sequence—i.e. the largest one that's less than or equal to N. P is the Fibonacci number before that, and L is the current sum of the even ones we've seen so far.
We can translate this into a type class:
import shapeless._, ops.nat.{ Mod, Sum }, nat.{ _0, _1, _2 }
trait EvenFibs[N <: Nat] {
type L <: Nat
type C <: Nat
type P <: Nat
}
Now there are four cases we need to handle. First I'll give the one that needs to have the lowest priority in order to get the implicit resolution right:
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
}
}
This is the case where Succ[N] is not a Fibonacci number. It doesn't require us to update any of the values we're keeping track of. The next case is a little more complex:
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
}
}
This is the case where Succ[N] is an odd Fibonacci number. In this case we need to update C and P, but not L.
Our last Succ[N] case is the one where Succ[N] is an even Fibonacci number. I'll give it here with the base case:
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
}
Lastly we can define a helper class that will make it easier to check our work:
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]
And then:
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)
The last line takes about twenty seconds to compile on my machine, but it works.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments