对 F# 中任意级别嵌套的列表求和

Question

我正在尝试创建一个 F# 函数，该函数将返回int任意嵌套的s列表的总和。IE。它适用于 a list<int>、 alist<list<int>>和 a list<list<list<list<list<list<int>>>>>>。

在 Haskell 中，我会写一些类似的东西：

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# 中实现这一点？

Answer 1

更新

我找到了一个更简单的版本，使用运算符($)而不是成员。灵感来自/sf/answers/505698861/：

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成员约束并调用它。
• getSumSumOperations作为第一个类型参数 传递给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