总结F#中任意级别的嵌套列表 [英] Summing over lists of arbitrary levels of nestedness in F#

问题描述

我正在尝试创建一个F#函数，该函数将返回任意嵌套的 int 列表的总和.IE.它将对 list< int> ， list< list< int> 和 list< list< list< list< list< list< list<int>>>>>> .

I'm trying to create an F# function that will return the sum of a list of ints of arbitrary nestedness. Ie. it will work for a list<int>, a list<list<int>> and a list<list<list<list<list<list<int>>>>>>.

在Haskell中，我会写类似的东西:

In Haskell I would write something like:

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#中实现这一目标?

How can I achieve this in F#?

推荐答案

UPDATE

我发现使用操作符($)而不是成员的更简单版本.受 https://stackoverflow.com/a/7224269/4550898 的启发:

UPDATE

I found a simpler version using an operator ($) instead of a member. Inspired by 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

其余说明仍然适用，并且很有用...

我找到了一种使之成为可能的方法:

The rest of the explanation still applies and it is useful...

I found a way to make it possible:

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:静态成员Sum ，约束要求该类型具有名为 Sum 的成员返回 int .使用SRTP通用功能时需要为 inline .

This is based on using SRTPs with member constraints: static member Sum, the constraint requires the type to have a member called Sum that returns an int. When using SRTPs generic functions need to be inline.

那不是困难的部分.困难的部分是添加" Sum 成员到现有的类型，例如 int 和 List ，这是不允许的.但是，我们可以添加将其更改为新的 SumOperations 类型，并将其包含在约束中(^ t或^ a)其中 ^ t 始终是 SumOperations .

That is not the difficult part. The hard part is "adding" Sum member to an existing type like int and List which is not allowed. But, we can add it to a new type SumOperations and include in the constraint (^t or ^a) where ^t is always going to be SumOperations.

• getSum0 声明 Sum 成员约束并调用它.
• getSum 将 SumOperations 作为第一个类型参数传递给 getSum0

• getSum0 declares the Sum member constraint and invokes it.
• getSum passes SumOperations as the first type parameter to getSum0

添加了行静态成员inline Sum(x:float)= int x 说服编译器使用通用动态函数调用，并不只是默认为静态成员内联Sum(x:int)调用 List.sumBy

The line static member inline Sum(x : float ) = int x was added to convince the compiler to use a generic dynamic function call and not just default to static member inline Sum(x : int ) when calling List.sumBy

如您所见，它有点令人费解，语法很复杂并且有必要解决在编译器上有一些怪癖，但最终还是有可能的.

As you can see is a bit convoluted, the syntax is complex and it was necessary to work around some quirks on the compiler but in the end it was possible.

通过将更多定义添加到 SumOperations :

This method can be extended to work with Arrays, tuples, options, etc. or any combination of them by adding more definitions to 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

这篇关于总结F#中任意级别的嵌套列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！