Refresh value in tree

Question

I have some state that is represented as a tree

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

and I have a function for updating individual leaves, taking into account some actions

 updateLeaf : action -> state -> state 

I need a way to represent actions in some structure

 type Structure action = ... 

which carries the action and some means to know exactly which leaf in the tree to update.

For example, suppose I have the following tree:

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

and I can say “hello” and I would like it to apply my updateLeaf function only on “baz” in such a way that in the end I got

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

Assuming my updateLeaf function is just a string concatenation or (++) . In addition, I will need this rather general, since the structure will somehow track the position in the tree of the sheet that he wants to update.

In essence, I am looking for the following function:

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

which will determine which leaf in the tree to apply this update function.

Finally, I also need it to work with address forwarding. Suppose each leaf of a tree is represented as a button

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

and further suppose that the actions sent by the button on the click are those that will update the state.

I would like to be able to define the following function

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

so that I can view all of these buttons, and the addresses are forwarded accordingly so that each button only affects itself. (I'm only interested in forwarding aspects, not visual effects).

Thank you very much for your help

Answer 1

It turns out that lightning allows you to achieve this. I will go through the decision.

Using the following lightning

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

Just need to implement the following functions

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

They can be implemented as follows

 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 (\za -> if z == zipper then fa else a) tree 

Where keepJusts filters nicks from the maybes list

 keepJusts : List (Maybe a) -> List a 

and gotoIndex goes into the nth subtree in lightning

 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) 

Now, given the zipperMap and zipperUpdate , we can apply them to our state.

Suppose actions on trees are represented as follows:

 type Action action state = ChildAction (Zipper state) action 

We can implement our update function as follows

 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 

And we can implement our view function as follows

 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 [] 

Where toList converts the tree to a list. Although this is just an example, it helps illustrate how you can work with such things.

For more details, you can see a fully functioning example here.

Answer 2

Do you want a zipper . Does everything you ask in terms

• indicating a unique location in the tree
• allows you to change focus while saving the rest.
• simple assembly of a tree.

If you want to associate the modifications with the exact location, you just need to create a type that includes a zipper and an action.

There's a good section on lightning in Teach you to Haskell .

Once you understand the concept, it is easily applicable to many other data structures.

Answer 3

A zipper is a way to navigate and change data structures. Suppose you have a tree and you go through the tree, choosing a branch. After 3 steps, you come across a sheet, and you can modify it. Now you want to return the changed tree, but you are 3 levels deep, how do you retreat? Suppose that every time you go down to the level of a tree, you leave a trail of crackers so that you can undo the step and restore the tree. In other words, instead of the whole tree, you have a tuple (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"]] 

Each time you select a branch, you disagree with the parent node and all other branches that you did not select in the breadcrumbs. Then you select a new branch, so you do not agree with its parent mode and all new branches that you did not select in the breadcrumbs. Therefore, breadcrumbs contain all the necessary information to restore the previous step in the reverse order. Let the movement up and transition to the sheet by name in the tree be implemented:

 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 px 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 lr::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 lr::bs) main = tree |> treeInit |> treeTo "foo" |> show 

But this does not allow you to move the focus from the root to the Leaf "baz" and does not allow it to be changed, so add a few more functions (note that all our functions with a zipper can fail, we will change this soon):

 (!!) : 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 

This whole chain of functions can easily work if there is an index larger than the size of the branch, or you are trying to jump from the root, etc. Instead, we should wrap the results in Maybe , so that instead of a failure, Nothing returned. But how do we bind the functions, now that they return Maybe (Zipper state) while they still accept the Zipper state ? Here you are using andThen , which is of type Maybe a -> (a -> Maybe b) -> Maybe b . The full code of your lightning is below:

 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 px 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 lr::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 lr::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 

(Feel free to ask questions and clarifications, and I will update and improve this answer)