以递归类型更新值 - 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 []情况下.

我将稍微修改你的代码,因为我们可以提取一些常见的模式.首先,让我们采用底层的树形结构,使其更通用,以便它可以适合任何类型的东西,而不仅仅是Item:

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

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

如果我们考虑你想要的算法,我们可以推断一个熟悉的模式.您有一个包含多个项目的结构,并且您需要一种能够访问每个项目并可选择更改它的算法.听起来很像List.map.这是一个常见的习惯用法,调用我们的通用函数是个好主意map:

map : (a -> b) -> Node a -> Node b
map f (Node item children) =
  Node (f item) (List.map (map f) 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