Summing over lists of arbitrary levels of nestedness in F#2020-02-13 haskell f#
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<list<int>> and a
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#?
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
that returns an
int. When using SRTPs generic functions
need to be
That is not the difficult part. The hard part is "adding"
Sum member to
an existing type like
List which is not allowed. But, we can add
it to a new type
SumOperations and include in the constraint
(^t or ^a)
^t is always going to be
Summember constraint and invokes it.
SumOperationsas the first type parameter to
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
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
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
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
| 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)
- F# recursive function that takes single point and index
- Best approach for designing F# libraries for use from both F# and C#
- (F#) Inbuilt function to filter a list if it does not contain a specific value
- How to split a sequence in F# based on another sequence in an idiomatic way
- F# – mapping a list with an accumulator
- Creating a haskell function that returns the sum of the squares in a list of lists of ints?
- Getting associated type synonyms with template Haskell
- fsharp get nth element from a list
- Split list into two equal lists in F#
- Why does F# prefer lists over arrays?