更新递归类型的值 - elm lang

Question

我有一个树状文本节点结构，它可能有另一个文本节点作为子节点，我需要更新其中的一个值。更新位于该树深处（或根本不在该树中）的文本节点的最简单方法是什么？

在非不可变语言中，我会简单地更改该项目的值，仅此而已，但在像 Elm 这样的不可变语言中，这非常棘手。

type alias Item =
  { id: String
  , text: String
  , children: ChildItems
  }

type ChildItems = ChildItems (List Item)

type alias Model =
  { rootItem: Item
  }

updateItem: Item -> Item -> Item
updateItem: rootItem item =
   -- TODO

...

update model =
  case msg of
    UpdateItem item updatedText ->
      let
        updatedItem = { item | text = updatedText }
      in
        ({ model | rootItem = (updateItem model.rootItem updatedItem) }, Cmd.none)

这是我想出来的

updateItem: Item.Item -> Item.Item -> Item.Item
updateItem rootItem updatedItem =
  if rootItem.id == updatedItem.id then
    updatedItem
  else
    case rootItem.children of
      Item.ChildItem [] ->
        rootItem

      Item.ChildItem children ->
        let
          updatedChildren =
            case children of
              [] ->
                []

              children ->
                List.map (\item ->
                  updateItem rootItem item) children
        in
          { rootItem | children = Item.ChildItem updatedChildren }

但我遇到 Maximum call stack size exceeded 错误

Answer 1

你得到堆栈溢出的原因是因为你返回 rootItem 而不是 Item.ChildItems [] 情况下的 []。

我将稍微修改一下您的代码，因为我们可以提取一些常见的模式。首先，让我们采用底层 tree-ish 结构并使其更通用，以便它可以适应任何类型的事物，而不仅仅是 Item:

type Node a
  = Node a (List (Node a))

这给了我们一个结构，它总是有一个根节点，并且可以有任意数量的 children，每个人也可以有任意数量的 children.

如果我们考虑您要使用的算法，我们可以推断出一个熟悉的模式。您有一个包含多个项目的结构，并且您想要一个访问每个项目并有选择地更改它的算法。这听起来很像 List.map。这是一个很常见的习语，调用我们的广义函数 map:

是个好主意

map : (a -> b) -> Node a -> Node b
map f (Node item children) =
  Node (f item) (List.map (map f) children)

（旁注：我们刚刚偶然发现 functors！）

由于我采用了 children 的想法并将其放入 Node 类型，我们需要像这样修改别名 Item：

type alias Item =
  { id: String
  , text: String
  }

现在我们有了一个 Item，如果 id 匹配某个值，那么有一个可以更新它的函数会很有帮助。由于以后你可能会有更多的更新功能要执行，所以最好将查找和 ID 匹配部分与你实际要执行的功能分开：

updateByID : String -> (Item -> Item) -> Item -> Item
updateByID id f item =
  if item.id == id then
    f item
  else
    item

现在要在树中的任何位置对与 id 匹配的项目执行更新，您可以简单地执行以下操作：

map (updateByID "someID" (\x -> { x | text = "Woohoo!" })) rootNode

更新递归类型的值 - elm lang

Update value in a recursive type - elm lang

recursion

elm