CODEWITHSUNDEEP
haskellsyntaxtreefunctional-programming
MIRMIX
MIRMIX

Reputation: 1080

tree with defined Type in haskell

I am trying to construct a tree from pre/postoreder traversals . My tree type is below:

        data Tree = Emptytree | Node Integer [Tree]

I am new in functional programming. So I come across with some difficulties while tying construct my base cases and recursion.My function will be something like this:

           ListToTree :: [Integer] -> [Integer] -> Tree

I construct some algorithms but I can not make it to fit to Language requirements. My algorithm is quite simple:I take each element of first list (preorder traversal list) then I check it position in the second list. Let me give an example:

                1                       
             /     \    
          2          5
         /  \
       3      4

Preorder of this Tree traversal is as you know [1,2,3,4,5]

Postorder of this Tree traversal is as you know [3,4,2,5,1]

Firstly I look to the first element of first list it is 1 then I look it is position it in 2nd list it is last so I add this to my tree. Then I check next element of tree it is 2 in the second list it on the left of 1 it means it is child of it. Then 3 is on the left of 2 (in the second list) it means it is also the son of 2 then i look to 4 it is on the left of 2 it is son of 2, and lastly 5 it is on the left of 1 it is child of one (because it is on the right of 2 it is not a child of 2).

I tried to implement it . I write helper function which determines if Node has a child or not. I use also counter in my function So actually my function is like this:

           ListToTree :: Integer -> [Integer] -> [Integer] -> Tree
           {-First Stands for counter ,2nd preorder, 3rd postorder-}

MY base condition are:

                 1. is about if list are Emptytree return Emptytree
                 2. is about if counter== length-1 return Node element [Emptytree]

My main problematic part is in my recursive part: 

  ListToTree counter a b  
    | hasChild b counter == 1 = Node ( Element ) [ListToTree (1+counter) a b]
    | hasChild b counter == 0 = Node ( Element ) [Emptytree]
        {-My problematic part if node has no Child what I must change here-}
        {-Or what are your suggestions-}

I need help in improving my algorithm Any kind of help or comments will be highly appreciated.

Upvotes: 2

Views: 862

Answers (2)

Chris Kuklewicz
Chris Kuklewicz

Reputation: 8153

Given the pre-order and post-order are [Integer], there may be zero or one or many trees that returns these traversals. For instances the traversals [1,1,1] and [1,1,1] have two possible trees. With 'mLast' and 'splits' helper function, it is possible to define a short 'listToTrees' which handles possible 'Forest' parsings. Then it is easy to define 'listToTree' as a special case that produces possible single 'Tree' parsings.

module PPT where

import Data.List

data Tree a = Emptytree | Node a (Forest a)
    deriving Show

-- | A list of sibling trees, in left to right order
type Forest a = [Tree a]

-- | Returns a list of all valid trees that produce the given pre-order and post-order traversals.
--
-- If the input cannot be parsed into a Tree then results is an empty list.
listToTree :: [Integer] -> [Integer] -> [Tree Integer]
listToTree [] [] = [Emptytree]  -- base case
listToTree [] _ = []            -- detect length mismatch
listToTree (x:xs) yAll = case mLast yAll of
    Just (ys, y) | x==y -> map (Node x) (listToTrees xs ys) -- pre-order start == post-order end
    _ -> []

-- | Given pre-order and post-order traversals of a forest, return a list of possible parsings.
listToTrees :: [Integer] -> [Integer] -> [Forest Integer]
listToTrees [] [] = [ [] ]      -- base case
listToTrees [] _ = []           -- detect length mismatch
listToTrees (x:xs) ys = concatMap build (splits x ys) -- for each copy of 'x' in ysAll
  where
      build (belowX', _x', rightOfX') =
          let (belowX, rightOfX) = splitAt (length pre) xs
          in [ Node x kids : sibs
             | kids <- listToTrees belowX belowX'
             , sibs <- listToTrees rightOfX rightOfX' ]

-- | Safely split a non-empty into the initial portion and the last portion
mLast :: [a] -> Maybe ([a], a)
mLast [] = Nothing
mLast ys = Just (init ys, last ys)

-- | At each position for the given element 'x', split the input list 'ys' into (pre, x, post)
-- portions.  The output has a tuple for each copy of 'x' in the input list 'ys'.
--
-- This could be better optimized to avoid (++), or changed to a zipper
splits :: Eq a => a -> [a] -> [ ([a], a, [a]) ]
splits x ysIn = unfoldr go ([], ysIn)
  where
    go (pres, ys) =
        case span (x /=) ys of
            (_, []) -> Nothing
            (pre, x':post) -> Just ((pres ++ pre, x', post), (pres++pre++[x'], post))

-- | test1 has a single possible parsing
test1 :: ([Integer], [Integer])
test1 = ( [1, 2, 3, 4, 5]
        , [3, 4, 2, 5, 1] )

-- | test2 has two possible parsings
test2 :: ([Integer], [Integer])
test2 = ( [1, 2, 1, 2]
        , [2, 1, 2, 1] )

main :: IO ()
main = do
    mapM_ print (uncurry listToTree test1)
    mapM_ print (uncurry listToTree test2)

Upvotes: 1

yokto
yokto

Reputation: 753

The beautiful thing about haskell is that you don't usually need a counter. It is usually sufficient to just do patter matching.

I will give the solution for [Tree] since that requires less cases. If you want a solution for a single Tree you can just introduce some cases in a wrapper function.

listToTree :: [Integer] -> [Integer] -> [Tree]
listToTree [] [] = []
listToTree (x:xs) ys = go where
    fstSubTreePost = takeWhile (/=x) ys -- all the elems of 1. subtree except x
    fstSubTreeLength = length fstSubTreePost
    fstSubTreePre = take fstSubTreeLength xs
    -- this will recursively compute the first subtree
    fstTree = Node x (listToTree fstSubTreePre fstSubTreePost)
    -- the next line will recursively compute the rest of the subtrees
    rest = listToTree (drop fstSubTreeLength xs) (drop (fstSubTreeLength+1) ys)
    go = fstTree : rest

Upvotes: 1

Related Questions