计算递归类型别名列表中的元素

Question

根据 elm-compiler 存储库中的递归类型别名提示，一种解决方案产生类型签名：

type alias Comment =
  { message : String
  , upvotes : Int
  , downvotes : Int
  , responses : Maybe Responses
  }

type Responses = Responses (List Comment)

（其中 responses 已扩展为在此处键入 Maybe Responses 以允许空响应列表）。

我对计算此类列表中的元素数量很感兴趣，尽管我当前的解决方案似乎比需要的复杂得多。

count : List Comment -> Int
count comments =
    let
        responses =
            List.concatMap (\c -> flatList c) comments
    in
    List.length responses


flatList : Comment -> List Comment
flatList root =
    let
        rest =
            case root.children of
                Just responseList ->
                    List.concatMap (\child -> flatList child) <| unwrapResponses responseList
                Nothing ->
                    []
    in
    root :: rest

unwrapResponses : Responses -> List Comment
unwrapResponses responses =
    case responses of
        Responses comments ->
            comments

实际上，这解开每个 Responses 子列表并递归地展平它。然后，对于每个父 Comments，我们将每个平面 Responses 列表连接在一起，最后得到这个列表的长度。

因为我对这个扁平化列表没有用处，所以我更愿意在列表中重复计算每个 List.length，然后对结果进行折叠或求和（或者，使用其他一些方法检索总元素数）。但是，我不确定如何在不返回 flatList 结果的情况下生成这样的解决方案。

Answer 1

听起来你需要一个专门的评论折叠功能。折叠是使用接受元素和某种累加器值的函数访问结构中的每个元素的想法，这样您就可以一步一步地保持某种状态。

旁注：我建议您将注释 responses 定义为 Responses 而不是 Maybe Responses，因为空列表和 Nothing 确实代表同样的事情。

您可以为这样的评论列表定义 foldl：

foldl : (Comment -> b -> b) -> b -> List Comment -> b
foldl f =
    List.foldl
        (\c acc ->
            case c.responses of
                Responses responses ->
                    foldl f (f c acc) responses
        )

这意味着它将首先使用您的函数访问评论节点，然后 children 从左到右，一路累积结果。

要使用它来确定长度，您只需忽略注释并沿途增加一个计数器：

length : List Comment
length =
    foldl (\_ acc -> acc + 1) 0

您会看到 definition of List.length 的实现使用与 foldl 相同的想法。

计算递归类型别名列表中的元素

Counting elements in recursive type alias lists

recursion

elm