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

标签： haskellf#

Answer 1

更新

我发现了一个使用运算符($)而不是成员的更简单的版本。灵感来自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这是不允许的。但是，我们可以将它添加到一个新类型并包含在 where is always going to beSumOperations的约束中。(^t or ^a)^tSumOperations

• 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