Summing over lists of arbitrary levels of nestedness in F#

Question

I'm trying to create an F# function that will return the sum of a list of ints 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

Link to runnable code.

How can I achieve this in F#?

Answer 1

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

Running your example:

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

Answer 2

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)