Суммирование по спискам произвольных уровней вложенности в F #

Я пытаюсь создать функцию F #, которая будет возвращать сумму списка ints произвольной вложенности. То есть. это будет работать для a list<int>, a list<list<int>>и a list<list<list<list<list<list<int>>>>>>.

В Хаскеле я бы написал что-то вроде:

class HasSum a where
    getSum :: a -> Integer

instance HasSum Integer where
    getSum = id

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

что позволило бы мне сделать:

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

Как я могу добиться этого в F #?

ОБНОВИТЬ

Я нашел более простую версию с использованием оператора ($)вместо члена. Вдохновленный 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

Остальная часть объяснения все еще применима, и это полезно ...

Я нашел способ сделать это возможным:

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

Это основано на использовании SRTP с ограничениями членов: static member Sumограничение требует, чтобы тип вызывал член, Sum который возвращает int. При использовании SRTP должны быть общие функции inline.

Это не сложная часть. Твердая часть «добавление» Sumэлемента к существующему типу , как intи List, не допускается. Но мы можем добавить его к новому типу SumOperationsи включить в ограничение, (^t or ^a) где ^tоно всегда будет SumOperations.

• getSum0объявляет Sumограничение члена и вызывает его.
• getSum передает SumOperationsв качестве параметра первого типаgetSum0

Строка static member inline Sum(x : float ) = int xбыла добавлена, чтобы убедить компилятор использовать общий динамический вызов функции, а не только значение по умолчанию static member inline Sum(x : int )при вызовеList.sumBy

Как вы можете видеть, это немного запутанно, синтаксис сложен, и было необходимо обойти некоторые причуды в компиляторе, но в конце концов это стало возможным.

Этот метод можно расширить для работы с массивами, кортежами, параметрами и т. Д. Или любой их комбинацией, добавив дополнительные определения в 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

Вот версия времени выполнения, будет работать со всеми коллекциями .net. Тем не менее, обменивается ошибками компилятора в ответе AMieres на исключения во время выполнения и AMieres 'также в 36 раз быстрее.

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)