CODEWITHSUNDEEP
haskellrecursionsyntaxtree
MIRMIX
MIRMIX

Reputation: 1080

Haskell N-ary tree construction

I am new in Haskell. I trying to learn implementation of N-ary trees in Haskell. I tried to construct N-ary tree and so I create my own data type

      data Tree = Empty | Node Integer [Tree] deriving Show

I want to construct my Tree from the list. I want to construct such Tree that going to take List elements one by one . If element is smaller it is going to be subtree of previous element else it going to be sibling.My problem is in the base cases and recursion parts. So I write such a code:

      arrin :: [Integer] -> Integer -> Integer {-this function takes an array -}
      arrin (x:xs) i                           {- and indexs and return the element-}  
        | i == 0    = x                    {-of that array which on that index -}
        | otherwise = arrin xs (i-1)  


      listToTree :: Integer -> [Integer] -> Tree
      listToTree _ [] = Empty {-First Input will be zero initially-}
      listToTree 11 _ = Empty {-Lets assume that the lenght of my list is 10-}
      listToTree 0 a = Node ( arrin a 0 ) [listToTree 1 a]
      listToTree num a  {-I need your help in this part what should i do-}
          | arrin a num > arrin a (num+1) = Node ( arrin a num ) [listToTree (num+1) a]
          | otherwise = Node ( arrin a num ) [Empty]

Any kind of comments and answers will be appreciated.

Upvotes: 0

Views: 1209

Answers (1)

yokto
yokto

Reputation: 753

Why does your function take an integer as first argument? Also it is not clear if the tree should end in "Node int []" or "Node int empty". If you are ready to accept [Tree] as output you don't even need empty which would probably only really be necessary for the empty list. In that case, the function could be as follows.

listToTree :: [Integer] -> [Tree]
listToTree [] = []
listToTree [x] = [Node x []]
listToTree (x1:x2:xs)
    | x2 < x1 = [Node x1 (listToTree (x2:xs))] -- subtree
    | otherwise = Node x1 [] : listToTree (x2:xs) -- sibling

Upvotes: 1

Related Questions