score:10

I find it a little easier to think about this problem inductively (at the type level, at least). First we can define a helper type class that returns `N` if `N` is a multiple of one of the numbers in `M`, and `_0` otherwise:

``````import shapeless._, nat._0, ops.nat.Mod

trait IfMultiple[N <: Nat, M <: HList] { type Out <: Nat }

trait LowPriorityIfMultiple {
type Aux[N <: Nat, M <: HList, Out0 <: Nat] = IfMultiple[N, M] {
type Out = Out0
}

implicit def isMultiple1[N <: Nat, H <: Nat, T <: HList](implicit
ifMultiple: IfMultiple[N, T]
): Aux[N, H :: T, ifMultiple.Out] = new IfMultiple[N, H :: T] {
type Out = ifMultiple.Out
}
}

object IfMultiple extends LowPriorityIfMultiple {
implicit def ifMultiple0[N <: Nat]: Aux[N, HNil, _0] =
new IfMultiple[N, HNil] {
type Out = _0
}

implicit def ifMultiple2[N <: Nat, H <: Nat, T <: HList](implicit
mod: Mod.Aux[N, H, _0]
): Aux[N, H :: T, N] = new IfMultiple[N, H :: T] {
type Out = N
}
}
``````

And now we just need a type class to add up all these values from `_0` to `N - _1`:

``````import nat._1, ops.nat.Sum

trait SumOfMultiples[N <: Nat, M <: HList] extends DepFn0 { type Out <: Nat }

object SumOfMultiples {
type Aux[N <: Nat, M <: HList, Out0 <: Nat] = SumOfMultiples[N, M] {
type Out = Out0
}

def apply[N <: Nat, M <: HList](implicit
som: SumOfMultiples[N, M]
): Aux[N, M, som.Out] = som

implicit def sum0[M <: HList]: Aux[_1, M, _0] =
new SumOfMultiples[_1, M] {
type Out = _0
def apply(): _0 = _0
}

implicit def sumN[P <: Nat, M <: HList, NV <: Nat, PT <: Nat, NT <: Nat](implicit
ifMultiple: IfMultiple.Aux[P, M, NV],
som: Aux[P, M, PT],
sum: Sum.Aux[NV, PT, NT],
wit: Witness.Aux[NT]
): Aux[Succ[P], M, NT] = new SumOfMultiples[Succ[P], M] {
type Out = NT
def apply(): NT = wit.value
}
}
``````

And then we're done:

``````import nat._, test.typed

val result = SumOfMultiples[_10, _3 :: _5 :: HNil]

typed[Succ[_22]](result())
``````

Which compiles as expected.

It's worth noting that there are other ways you could solve this problem. You could create a type class that would provide `Nat` ranges and then fold over that with a `Poly2` using `IfMultiple`. You could also define an `IsMultiple` type class that just witnesses that `N` is a multiple of one of the numbers in `M`—my first quick attempt did this, but I ran into ambiguity issues, so I went with the similar version above. The implementation here is fairly straightforward, though, and unless you have other applications for e.g. `Nat` ranges, I think it's a pretty reasonable solution.