[haskell] F #에서 임의의 중첩 수준 목록을 합산

Program / 글쓴이

int임의의 중첩 목록의 합계를 반환하는 F # 함수를 만들려고합니다 . 즉. a list<int>, a list<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 #에서 어떻게 이것을 달성 할 수 있습니까?

답변

최신 정보

($)멤버 대신 연산자 를 사용하여 더 간단한 버전을 찾았습니다 . 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

이것은 회원 제약 SRTPs를 사용을 기반으로합니다 static member Sum, 제약라는 멤버가하는 유형을 필요로 Sum
하는 다시 표시를 int. SRTP를 사용할 때 일반 기능은이어야 inline합니다.

그것은 어려운 부분이 아닙니다. 어려운 부분은 Sum기존 유형과 유사 int하고 List허용되지 않는 멤버를 “추가” 하는 것입니다. 그러나 새로운 유형에 추가 할 수 있으며 항상
어디에 SumOperations있을지 제약 조건에 포함시킬 수 있습니다 .(^t or ^a)^tSumOperations

  • getSum0Sum멤버 제약 조건을 선언 하고 호출합니다.
  • getSum 통과 SumOperations하는 제 1 타입 파라미터로서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)

답변