Problem 70b

Generate a string representation of a multiway tree in depth-first order. Insert the special character ^ whenever the move is a backtrack to the previous level.

By this rule, the tree below is represented as: afg^^c^bd^e^^^

a) Write a function to convert a multiway tree to a string representation.

b) Write a function to convert a string representation to a multiway tree.

Example

type MTree a = MNode a (List (MTree a))

mtree70 = MNode 'a' 
          [ MNode 'f' [ MNode 'g' [] ]
          , MNode 'c' []
          , MNode 'b' [ MNode 'd' [], MNode 'e' [] ]
          ]

s70 = "afg^^c^bd^e^^^"

s70 == treeToString <| stringToTree s70

Unit Test

import Html
import List
import Maybe
import String


type MTree a = MNode a (List (MTree a))

stringToTree : String -> MTree Char
stringToTree s =
    -- your implemenation goes here
    MNode 'X' []


treeToString : MTree Char -> String
treeToString tree =
    "Your implementation goes here"


main =
    Html.text
        (if (test) then
            "Your implementation passed all tests."
         else
            "Your implementation failed at least one test."
        )


test : Bool
test =
    List.all ((==) True)
      [ mtree70 == stringToTree string70
      , string70 == treeToString mtree70
      , aT == stringToTree aS
      , aS == treeToString aT
      ]


aS = "af^c^b^^"
aT = MNode 'a' 
          [ MNode 'f' [] 
          , MNode 'c' []
          , MNode 'b' []
          ]

string70 = "afg^^c^bd^e^^^"
mtree70 = MNode 'a' 
          [ MNode 'f' [ MNode 'g' [] ]
          , MNode 'c' []
          , MNode 'b' [ MNode 'd' [], MNode 'e' [] ]
          ]

Hints

1. This problem is similar to Problem 69.
2. Traverse the tree in pre-order with a function that returns two values, the tree value and the unused portion of the string.
3. Treating the root node differently that the rest of the tree may result in simpler functions.
4. List.intersperse, List.fromChar, List.cons and List.uncons may come in handy

Solution

Solution