Sumowanie list dowolnych poziomów zagnieżdżenia w F #

Próbuję utworzyć funkcję F #, która zwróci sumę listy ints dowolnego zagnieżdżenia. To znaczy. będzie działać dla a list<int>, a list<list<int>>i a list<list<list<list<list<list<int>>>>>>.

W Haskell napisałbym coś takiego:

class HasSum a where
    getSum :: a -> Integer

instance HasSum Integer where
    getSum = id

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

co pozwoliłoby mi zrobić:

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

Jak mogę to osiągnąć w F #?

AKTUALIZACJA

Znalazłem prostszą wersję, używając operatora ($)zamiast członka. Inspirowany 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

Reszta wyjaśnienia nadal obowiązuje i jest przydatna ...

Znalazłem sposób, aby to umożliwić:

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

Uruchamianie Twojego przykładu:

let list v = List.replicate 6 v

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

Opiera się to na stosowaniu SRTP z ograniczeniami elementu: static member Sumograniczenie wymaga, aby typ miał wywoływany element Sum zwracający wartość int. Podczas korzystania z SRTP muszą to być funkcje ogólne inline.

To nie jest trudna część. Trudną częścią jest „dodawanie” Sumelementu do istniejącego typu, takiego jak inti Listktóry jest niedozwolony. Ale możemy dodać go do nowego typu SumOperationsi uwzględnić w ograniczeniu, (^t or ^a) gdzie ^tzawsze będzie SumOperations.

• getSum0deklaruje Sumograniczenie członka i wywołuje je.
• getSum przechodzi SumOperationsjako parametr pierwszego typu dogetSum0

Linia static member inline Sum(x : float ) = int xzostała dodana, aby przekonać kompilator do używania ogólnego dynamicznego wywołania funkcji, a nie tylko domyślnego static member inline Sum(x : int )podczas wywoływaniaList.sumBy

Jak widać jest nieco skomplikowana, składnia jest złożona i trzeba było obejść pewne dziwactwa na kompilatorze, ale ostatecznie było to możliwe.

Metodę tę można rozszerzyć do pracy z tablicami, krotkami, opcjami itp. Lub dowolną ich kombinacją, dodając więcej definicji do 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

Oto wersja środowiska wykonawczego, działająca ze wszystkimi kolekcjami .net. Wymienia jednak błędy kompilatora w odpowiedzi AMieres na wyjątki czasu wykonywania i AMieres również jest 36 razy szybszy.

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

Benchmarki

|    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)