Elm

Question

我正在关注 this article 变形，我正在尝试为这样的递归数据类型定义折叠函数

type Node anyType
    = Leaf Id (Maybe anyType)
    | Tree Id (List (Node anyType))

我写的是这样的：

foldTree fLeaf fTree acc node =
let
    recurse =
        foldTree fLeaf fTree
in
case node of
    Leaf id v -> 
        let
            newAcc = fLeaf acc (id, v)
        in
            newAcc

    Tree id l ->
        let
            newAcc = fTree acc id
            
                
        in
            l |> List.foldl recurse newAcc

如果我不推断 foldTree 的类型，函数会编译，但它似乎不可用：

collectIds node = 
let
    fLeaf acc (id,v) = id :: acc
    fTree acc id = id :: acc
in

foldTree fLeaf fTree [] node

抛出以下内容：

TYPE MISMATCH - The 1st argument to `foldTree` is not what I expect:

173|     foldTree fLeaf fTree [] node
              #^^^^^#
This `fLeaf` value is a:

#List a# -> ( a, b ) -> #List a#

But `foldTree` needs the 1st argument to be:

#Node anyType# -> ( Id, Maybe anyType ) -> #Node anyType#

自动推断 foldTree 的类型使其不可编译并抛出以下内容：

-- Auto Inferred
foldTree : (c -> (Id, Maybe anyType) -> a) -> (c -> Id -> b) -> c -> Node anyType -> d

TYPE MISMATCH - Something is off with the 1st branch of this `case` expression:

126|                 newAcc
                     #^^^^^^#
This `newAcc` value is a:
#a#

But the type annotation on `foldTree` says it should be:

    #d#

#Hint#: Your type annotation uses `a` and `d` as separate type variables. Your
code seems to be saying they are the same though. Maybe they should be the same
in your type annotation? Maybe your code uses them in a weird way?

如果我尝试按照提示进行操作，仍然无法编译

foldTree : (c -> (Id, Maybe anyType) -> a) -> (c -> Id -> b) -> c -> Node anyType -> a

TYPE MISMATCH - This function cannot handle the argument sent through the (|>) pipe:

134|                 l |> List.foldl recurse newAcc 
                          #^^^^^^^^^^^^^^^^^^^^^^^^^#
The argument is:

    List #(Node anyType)#

But (|>) is piping it to a function that expects:

    List #c#

#Hint#: Your type annotation uses type variable `c` which means ANY type of value
can flow through, but your code is saying it specifically wants a `Node` value.
Maybe change your type annotation to be more specific? Maybe change the code to
be more general?

Read <https://elm-lang.org/0.19.1/type-annotations> for more advice!Elm
TYPE MISMATCH - The 1st argument to `foldl` is not what I expect:

134|                 l |> List.foldl recurse newAcc 
                                     #^^^^^^^#
This `recurse` value is a:

    c -> Node anyType -> #a#

But `foldl` needs the 1st argument to be:

    c -> Node anyType -> #Node anyType#

#Hint#: Your type annotation uses type variable `a` which means ANY type of value
can flow through, but your code is saying it specifically wants a `Node` value.
Maybe change your type annotation to be more specific? Maybe change the code to
be more general?

我卡住了。精确地遵循文章中的类型似乎也不起作用。我知道文章中的代码是 F#，我正在使用 Elm，但我认为在这种情况下它应该是 100% 可翻译的。

我哪里错了？

提前致谢！

Answer 1

您已将参数翻转为 List.foldl。 fold 函数首先取值，其次是累加器，而您的 recurse 函数首先取累加器，其次是值。

解决这个问题的简单方法是扩展递归函数并在将其传递给 foldTree 时翻转参数：

recurse v a = foldTree fLeaf fTree a v

此外，有趣的是，注释 recurse 的类型将使它编译，但显然会产生错误的结果。我没有进一步了解原因，因为这是错误的，但你应该从中吸取的教训是始终注释你的顶级函数。这将为您提供更好的错误消息，但也可以防止您的代码意外编译但产生错误结果。

Elm - 折叠递归类型与列表不编译

Elm - fold on recursive type with list does not compile

recursion

functional-programming

fold

multiway-tree