# Summing over lists of arbitrary levels of nestedness in F#

I'm trying to create an F# function that will return the sum of a list of `int`s of arbitrary nestedness. Ie. it will work for a `list<int>`, a `list<list<int>>` and a `list<list<list<list<list<list<int>>>>>>`.

In Haskell I would write something like:

``````class HasSum a where
getSum :: a -> Integer

instance HasSum Integer where
getSum = id

instance HasSum a => HasSum [a] where
getSum = sum . map getSum
``````

which would let me do:

``````list :: a -> [a]
list = replicate 6

nestedList :: [[[[[[[[[[Integer]]]]]]]]]]
nestedList =
list \$ list \$ list \$ list \$ list \$
list \$ list \$ list \$ list \$ list (1 :: Integer)

sumNestedList :: Integer
sumNestedList = getSum nestedList
``````

How can I achieve this in F#?

## UPDATE

I found a simpler version using an operator `(\$)` instead of a member. Inspired by https://stackoverflow.com/a/7224269/4550898 :

``````type SumOperations = SumOperations

let inline getSum b = SumOperations \$ b // <-- puting this here avoids defaulting to int

type SumOperations with
static member inline (\$) (SumOperations, x  : int     ) = x
static member inline (\$) (SumOperations, xl : _   list) = xl |> List.sumBy getSum
``````

## The rest of the explanation still applies and it is useful...

I found a way to make it possible:

``````let inline getSum0< ^t, ^a when (^t or ^a) : (static member Sum : ^a -> int)> a : int =
((^t or ^a) : (static member Sum : ^a -> int) a)

type SumOperations =
static member inline Sum( x : float   ) = int x
static member inline Sum( x : int     ) =  x
static member inline Sum(lx : _   list) = lx |> List.sumBy getSum0<SumOperations, _>

let inline getSum x = getSum0<SumOperations, _> x

2                  |> getSum |> printfn "%d" // = 2
[ 2 ; 1 ]          |> getSum |> printfn "%d" // = 3
[[2; 3] ; [4; 5] ] |> getSum |> printfn "%d" // = 14
``````

``````let list v = List.replicate 6 v

1
|> list |> list |> list |> list |> list
|> list |> list |> list |> list |> list
|> getSum |> printfn "%d" // = 60466176
``````

This is based on using SRTPs with member constraints: `static member Sum`, the constraint requires the type to have a member called `Sum` that returns an `int`. When using SRTPs generic functions need to be `inline`.

That is not the difficult part. The hard part is "adding" `Sum` member to an existing type like `int` and `List` which is not allowed. But, we can add it to a new type `SumOperations` and include in the constraint `(^t or ^a)` where `^t` is always going to be `SumOperations`.

• `getSum0` declares the `Sum` member constraint and invokes it.
• `getSum` passes `SumOperations` as the first type parameter to `getSum0`

The line `static member inline Sum(x : float ) = int x` was added to convince the compiler to use a generic dynamic function call and not just default to `static member inline Sum(x : int )` when calling `List.sumBy`

As you can see is a bit convoluted, the syntax is complex and it was necessary to work around some quirks on the compiler but in the end it was possible.

This method can be extended to work with Arrays, tuples, options, etc. or any combination of them by adding more definitions to `SumOperations`:

``````type SumOperations with
static member inline (\$) (SumOperations, lx : _   []  ) = lx |> Array.sumBy getSum
static member inline (\$) (SumOperations, a  : ^a * ^b ) = match a with a, b -> getSum a + getSum b
static member inline (\$) (SumOperations, ox : _ option) = ox |> Option.map getSum |> Option.defaultValue 0

(Some 3, [| 2 ; 1 |]) |> getSum |> printfn "%d" // = 6
``````

https://dotnetfiddle.net/03rVWT

Here is the runtime version, would work with all .net collections. However, exchanges compiler errors in AMieres' answer for runtime exceptions and AMieres' is 36x faster too.

``````let list v = List.replicate 6 v

let rec getSum (input:IEnumerable) =
match input with
| :? IEnumerable<int> as l -> l |> Seq.sum
| e ->
e
|> Seq.cast<IEnumerable> // will runtime exception if not nested IEnumerable Types
|> Seq.sumBy getSum

1 |> list |> list |> list |> list |> list
|> list |> list |> list |> list |> list |> getSum // = 60466176
``````

Benchmarks

``````|    Method |        Mean |     Error |    StdDev |
|---------- |------------:|----------:|----------:|
| WeirdSumC |    76.09 ms |  0.398 ms |  0.373 ms |
| WeirdSumR | 2,779.98 ms | 22.849 ms | 21.373 ms |

// * Legends *
Mean   : Arithmetic mean of all measurements
Error  : Half of 99.9% confidence interval
StdDev : Standard deviation of all measurements
1 ms   : 1 Millisecond (0.001 sec)
``````

Related