CODEWITHSUNDEEP
listhaskelltreehigher-order-functions
user3276667
user3276667

Reputation: 87

Haskell: List to Rose Tree

Consider the following type to represent Rose trees:

data RTree a = No a [RTree a]

Consider the function 

tolist a = tolistAux 1 a
     where tolistAux n (No x l) = (x,n) : (concat (map (tolistAux (n+1)) l))

I need to define the inverse of the first function: unlist :: [(a,Int)] -> RTree a

such that unlist (tolist a) = a

Upvotes: 0

Views: 881

Answers (1)

user3276667
user3276667

Reputation: 87

Here is the solution I found.

I realized that if in (a,b), b==1 then I create a No a (...) Thus, I have a list and isolate this list into several lists that start with (a,1) by first subtracting 1 to b. Then, I create the tree using recursion (e,g a map function):

unlist ((x,1):t) = No x l3
where l1 = map (\(a,b) -> (a,b-1)) t
  l2 = isolate1 l1
  l3 = map unlist l2

isolate1 :: [(a,b)]->[[(a,b)]] --note that the result of isolate1 is a list of lists of pairs
isolate1 [] = []
isolate [x]=[[x]]
isolate1 ((a,b):t) = let (x:xs):ys = isolate1 t  
                     in |b==1 = ((a,b):x:xs):ys
                        |otherwise = [(a,b)]:(x:xs):ys

Glad to see more solutions :)

Upvotes: 1

Related Questions