Summieren über Listen beliebiger Verschachtelungsebenen in F #

Ich versuche, eine F # -Funktion zu erstellen, die die Summe einer Liste von ints mit beliebiger Verschachtelung zurückgibt. Dh. es wird für a list<int>, a list<list<int>>und a funktionieren list<list<list<list<list<list<int>>>>>>.

In Haskell würde ich so etwas schreiben wie:

class HasSum a where
    getSum :: a -> Integer

instance HasSum Integer where
    getSum = id

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

was mich tun lassen würde:

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

Wie kann ich dies in F # erreichen?

AKTUALISIEREN

Ich habe eine einfachere Version gefunden, bei der ein Operator ($)anstelle eines Mitglieds verwendet wurde. Inspiriert von 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

Der Rest der Erklärung gilt immer noch und es ist nützlich ...

Ich habe einen Weg gefunden, dies zu ermöglichen:

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

Führen Sie Ihr Beispiel aus:

let list v = List.replicate 6 v

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

Dies basiert auf der Verwendung von SRTPs mit Elementeinschränkungen: Für static member Sumdie Einschränkung muss der Typ ein Element mit dem Namen an haben, das ein Sum zurückgibt int. Bei der Verwendung von SRTPs müssen generische Funktionen vorhanden sein inline.

Das ist nicht der schwierige Teil. Der schwierige Teil ist das "Hinzufügen" eines SumMitglieds zu einem vorhandenen Typ wie intund Listwas nicht erlaubt ist. Wir können es jedoch einem neuen Typ hinzufügen SumOperationsund in die Einschränkung aufnehmen, (^t or ^a) wo ^tes immer sein wird SumOperations.

• getSum0deklariert die SumMember-Einschränkung und ruft sie auf.
• getSum wird SumOperationsals erster Typparameter an übergebengetSum0

Die Zeile static member inline Sum(x : float ) = int xwurde hinzugefügt, um den Compiler davon zu überzeugen, einen generischen dynamischen Funktionsaufruf zu verwenden und nicht nur standardmäßig static member inline Sum(x : int )beim AufrufList.sumBy

Wie Sie sehen können, ist die Syntax etwas kompliziert, und es war notwendig, einige Macken im Compiler zu umgehen, aber am Ende war es möglich.

Diese Methode kann erweitert werden, um mit Arrays, Tupeln, Optionen usw. oder einer beliebigen Kombination davon zu arbeiten, indem weitere Definitionen hinzugefügt werden zu 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

Hier ist die Laufzeitversion, würde mit allen .net-Sammlungen funktionieren. Der Austausch von Compilerfehlern in AMieres 'Antwort gegen Laufzeitausnahmen und AMieres' ist jedoch ebenfalls 36x schneller.

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)