更新树中的值

Update a value in a tree

我有一些用树表示的状态

type Tree state 
  = Branch (List (Tree state))
  | Leaf state

而且我有一个功能可以在给定一些操作后更新单个叶子

updateLeaf : action -> state -> state

我想要一种在某种结构中表示动作的方法

type Structure action = ...

它带有一个动作和一些方法来准确地知道要更新树中的哪个叶子。

例如,假设我有以下树:

Branch 
  [ Leaf "foo"
  , Leaf "bar"
  , Branch 
      [ Leaf "baz"
      , Branch []
      , Leaf "qux"
      ]
  ]

我得到一些动作说,"hello",我希望它以我的方式在 "baz" 上应用我的 updateLeaf 函数 only结束

Branch 
  [ Leaf "foo"
  , Leaf "bar"
  , Branch 
      [ Leaf "bazhello"
      , Branch []
      , Leaf "qux"
      ]
  ]

假设我的 updateLeaf 函数只是字符串连接或 (++)。此外,我需要它非常通用,因为在结构中会以某种方式跟踪它希望更新的叶子在树中的位置。

本质上我正在寻找的是以下功能:

updateTree 
  : (action -> state -> state)
 -> Structure action
 -> Tree state
 -> Tree state 

这将找出树中的哪个叶子应用给定的更新函数。

最后,我还需要它来处理地址转发。假设树的每一片叶子都表示为一个按钮

viewLeaf : Address action -> state -> Html
viewLeaf address state = 
  button 
    [ onClick address ... ]
    [ ... ]

并进一步假设点击按钮发送的动作将更新状态。

我希望能够定义以下函数

viewTree 
  : (Address action -> state -> Html)
 -> Address (Structure action) 
 -> Tree state
 -> Html

这样我就可以查看所有这些按钮,并且相应地转发地址,这样每个按钮只会影响它自己。 (我只对转发方面感兴趣,对视觉效果不感兴趣)。

非常感谢您的帮助

你要的是zipper。是否按照

要求的一切
  1. 指定树中的唯一位置
  2. 允许在保留其余部分的同时修改焦点。
  3. 轻松重新组装树。

如果你想将修改与精确位置捆绑在一起,那么你只需要构建一个包含拉链和动作的类型。

Learn You a Haskell 中有一个很好的关于拉链的部分。

一旦你理解了这个概念,它就很容易适用于许多其他数据结构。

A zipper 是一种导航和修改数据结构的方法。假设你有一棵树,你通过选择一个树枝沿着树走下去。 3 个步骤后,您遇到一片叶子,您可以修改它。现在你想 return 修改后的树,但是你有 3 层深,你如何退后一步?假设每次你在树中下一层,你都会留下面包屑的痕迹,这样你就可以倒退一步重建树。换句话说,你有一个元组 (tree, breadcrumbs) 而不是一棵树。

type Tree state = Branch (List (Tree state)) | Leaf state
-- Crumb contains 2 lists:
-- leafs/branches to the left of your focus
-- leafs/branches to the right of your focus
type Crumb state = Crumb (List (Tree state)) (List (Tree state))
type alias Zipper state = (Tree state, List (Crumb state))

tree : Tree String
tree = Branch [Leaf "foo",Leaf "bar",Branch [Leaf "baz",Branch [],Leaf "qux"]]

每次选择一个分支时,您都会将父节点和您未选择的所有其他分支放入面包屑中。然后你选择一个新分支,所以你在面包屑中使用它的父模式和你没有选择的所有新分支。因此,面包屑包含所有相关信息,以相反的顺序重建上一步。让我们实现在树中按名称向上和转到叶子:

import Graphics.Element exposing (show)

break : (a -> Bool) -> List a -> (List a, List a)
break p xs = case (List.head xs, List.tail xs) of
  (Nothing, Nothing) -> ([], [])
  (Just x, Just xs') -> if p x
                        then ([], xs)
                        else let (ys,zs) = break p xs'
                             in (x::ys,zs)

treeInit : Tree state -> Zipper state
treeInit t = (t, [])

treeUp : Zipper state -> Zipper state
treeUp (subtree, Crumb l r::bs) = (Branch <| l++[subtree]++r, bs)

treeTo : state -> Zipper state -> Zipper state
treeTo name (Branch subtrees, bs) =
  let (l, x::r) = break (\(Leaf name') -> name == name') subtrees
  in (x, Crumb l r::bs)

main = tree |> treeInit |> treeTo "foo" |> show

但这不允许将焦点从根移动到Leaf "baz"并且不允许修改它,所以让我们添加更多功能(注意我们所有的拉链功能都可能崩溃,我们会改变很快):

(!!) : List a -> Int -> a
xs !! i = case List.tail xs of
  Nothing -> Debug.crash "index out of bounds"
  Just xs' -> if i == 0
              then case List.head xs of Just x -> x
              else xs' !! (i-1)

treeToIndex : Int -> Zipper state -> Zipper state
treeToIndex i (Branch subtrees, bs) =
  (subtrees!!i, Crumb (List.take i subtrees) (List.drop (i+1) subtrees)::bs)

treeReplace : state -> Zipper state -> Zipper state
treeReplace new (Leaf old, bs) = (Leaf new, bs)

main = tree |> treeInit |> treeToIndex 2 |> treeTo "baz" |> treeReplace "xyzzy" |> show

如果存在大于分支大小的索引,或者您尝试从根向上移动,则整个函数链很容易崩溃,等等。相反,我们应该将结果包装在 Maybe 中,这样 Nothing 就不会崩溃,而是 returned。但是我们如何链接函数,既然它们 return Maybe (Zipper state),同时它们仍然接受 Zipper state?这是您使用 andThen 的地方,它的类型为 Maybe a -> (a -> Maybe b) -> Maybe b。下面是您的拉链的完整代码:

import Graphics.Element exposing (show)
import Maybe exposing (andThen)

type Tree state = Branch (List (Tree state)) | Leaf state
-- Crumb contains 2 lists:
-- leafs/branches to the left of your focus
-- leafs/branches to the right of your focus
type Crumb state = Crumb (List (Tree state)) (List (Tree state))
type alias Zipper state = (Tree state, List (Crumb state))

tree : Tree String
tree = Branch [Leaf "foo",Leaf "bar",Branch [Leaf "baz",Branch [],Leaf "qux"]]

break : (a -> Bool) -> List a -> (List a, List a)
break p xs = case (List.head xs, List.tail xs) of
  (Nothing, Nothing) -> ([], [])
  (Just x, Just xs') -> if p x
                        then ([], xs)
                        else let (ys,zs) = break p xs'
                             in (x::ys,zs)

treeInit : Tree state -> Zipper state
treeInit t = (t, [])

treeUp : Zipper state -> Maybe (Zipper state)
treeUp (subtree, bs) = case bs of
  [] -> Nothing
  Crumb l r::bs' -> Just (Branch <| l++[subtree]++r, bs')

treeTo : state -> Zipper state -> Maybe (Zipper state)
treeTo name node = case node of
  (Branch subtrees, bs) ->
    let (l, x::r) = break (\(Leaf name') -> name == name') subtrees
    in Just (x, Crumb l r::bs)
  _ -> Nothing

(!!) : List a -> Int -> Maybe a
xs !! i = case List.tail xs of
  Nothing -> Nothing
  Just xs' -> if i == 0
              then List.head xs
              else xs' !! (i-1)

treeToIndex : Int -> Zipper state -> Maybe (Zipper state)
treeToIndex i (Branch subtrees, bs) =
  let newTree = subtrees!!i
  in case newTree of
    Nothing -> Nothing
    Just newTree ->
      let newCrumb = Crumb (List.take i subtrees) (List.drop (i+1) subtrees)
      in Just (newTree, newCrumb::bs)

treeReplace : state -> Zipper state -> Maybe (Zipper state)
treeReplace new node = case node of
  (Leaf old, bs) -> Just (Leaf new, bs)
  _ -> Nothing

-- the function you're interested in most likely
treeUpdate : (state -> state) -> Zipper state -> Maybe (Zipper state)
treeUpdate f node = case node of
  (Leaf name, bs) -> Just (Leaf (f name), bs)
  _ -> Nothing

main = (tree |> treeInit |> treeToIndex 2)
       `andThen` treeTo "baz" `andThen` treeReplace "xyzzy"
       `andThen` treeUp `andThen` treeUp |> show

(请随时提出问题和说明,我会更新和改进此答案)

事实证明,拉链可以实现这一目标。我将演练解决方案。

使用下面的拉链

type alias Crumb a = 
  { left  : List (Tree a)
  , right : List (Tree a)
  }

type alias Zipper a = (Tree a, List (Crumb a))

只需实现以下功能

zipperMap : (Zipper a -> a -> b) -> Tree a -> Tree b 
zipperUpdate : Zipper a -> (a -> a) -> Tree a -> Tree a

这些可以实现如下

zipperMap : (Zipper a -> a -> b) -> Tree a -> Tree b 
zipperMap f tree = 
  let 
      applyZipper ((subtree, crumbs) as zipper) = 
        case subtree of 
          Leaf a ->
            Leaf (f zipper a)

          Branch subtrees ->
            subtrees 
            |> List.indexedMap (\index _ -> gotoIndex index zipper |> Maybe.map applyZipper)
            |> keepJusts
            |> Branch

  in 
      applyZipper (fromTree tree)



zipperUpdate : Zipper a -> (a -> a) -> Tree a -> Tree a
zipperUpdate zipper f tree = 
  zipperMap (\z a -> if z == zipper then f a else a) tree

其中 keepJusts 是从可能的列表中过滤掉空的东西

keepJusts : List (Maybe a) -> List a

gotoIndex进入一个zipper

中的第n个子树
gotoIndex : Int -> Zipper a -> Maybe (Zipper a)
gotoIndex index (tree, bs) = 
  case tree of
    Leaf _ ->
      Nothing

    Branch subtrees ->
      case nth index subtrees of 
        Nothing ->
          Nothing 

        Just newTree ->
          let 
              newCrumb = 
                { left  = List.take index subtrees
                , right = List.drop (index + 1) subtrees
                }
          in 
              Just (newTree, newCrumb :: bs) 

现在,给定函数 zipperMapzipperUpdate 我们可以将它们应用于我们的状态。

让我们假设树上的动作表示如下

type Action action state
  = ChildAction (Zipper state) action

我们可以如下实现我们的update功能

update : (action -> state -> state)
      -> Action action state
      -> Tree state 
      -> Tree state
update updateChild action state = 
  case action of 
    ChildAction zipper childAction -> 
      zipperUpdate zipper (updateChild childAction) state

我们可以实现我们的view功能如下

view : (Address action -> state -> Html) 
    -> Address (Action action state) 
    -> Tree state 
    -> Html
view viewChild address state = 
  let 
      viewZ zipper child = 
        let 
            childAddress = 
              Signal.forwardTo address (ChildAction zipper)

        in 
            viewChild childAddress child

  in 
      state
      |> zipperMap viewZ
      |> toList
      |> div []

其中 toList 将树转换为列表。虽然这只是一个示例,但它有助于说明如何使用这些东西。

有关更多详细信息,您可以查看功能齐全的示例here