更新树中的值
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。是否按照
要求的一切
- 指定树中的唯一位置
- 允许在保留其余部分的同时修改焦点。
- 轻松重新组装树。
如果你想将修改与精确位置捆绑在一起,那么你只需要构建一个包含拉链和动作的类型。
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)
现在,给定函数 zipperMap
和 zipperUpdate
我们可以将它们应用于我们的状态。
让我们假设树上的动作表示如下
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
我有一些用树表示的状态
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。是否按照
要求的一切- 指定树中的唯一位置
- 允许在保留其余部分的同时修改焦点。
- 轻松重新组装树。
如果你想将修改与精确位置捆绑在一起,那么你只需要构建一个包含拉链和动作的类型。
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
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)
现在,给定函数 zipperMap
和 zipperUpdate
我们可以将它们应用于我们的状态。
让我们假设树上的动作表示如下
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