Using custom recursive data type in haskell -> TRIE-CodePudding

I am learning Haskell and I just got a problem that seems to be quite hard.

I have a custom recursive data type for Trie.

data Trie keytype valuetype = TNode (Maybe valuetype) [Edge keytype valuetype]
            deriving (Show, Eq)

type Edge e a = (e, Trie e a)

And I am trying to implement functions that work with it. I found how to traverse it incorrect order.

isTrieValid :: Ord e => Trie e a -> [e]
isTrieValid (TNode _ []) = []
isTrieValid (TNode _ ((edge, TNode maybe innerlist):children)) =  edge : printChildren innerlist     printChildren children
       where  
              printChildren :: Ord e => [Edge e valuetype] -> [e]
              printChildren [] = []
              printChildren ((edge_name, TNode _ innerlist):xs) =edge_name : printChildren innerlist    printChildren xs

Which for eg. for following trie returns all "keys" (edge names) -> "abbce"

trie1 = TNode (Just 42) [('a', TNode (Just 16) []),
         ('b', TNode Nothing
               [('b', TNode (Just 1) []),
                ('c', TNode (Just 5) []),
                ('e', TNode (Just 2) [])
               ])
        ]

Now I am trying to make functions that will find elements based on "key" like this:

trieLookup :: Ord e => [e] -> Trie e a -> Maybe a

But I am witnessing two problems. First is, if I traverse the Trie with recursion I am not sure how to handle the first element. Because there is no "key" for the first element what shall I return? I thought an empty string would work but I want the whole "Ord" type class to be used for keys, so that raises a type error.

And next function which I was trying to make will check the Trie validity.

isTrieValid :: Ord e => Trie e a -> Bool

What I understood is, that Trie must have this quality to be considered valid.

All elements following the current element are ordered by the first element (order by Ord e)
No two successors have the same key

So whole TRIE is valid if the root node is valid and all subtrees/subtriees (not sure how to write it) are also valid.

I wanted to make a function that would check validity for one node and then replicate it on all nodes using the function above, but I failed.

Thanks for any help.

CodePudding user response：

I would suggest... maybe not to put the whole homework assignment from your university here for others to solve it for you? You are cheating and it is unfair for other students.

The teacher will surely find out about this and will punish you (and maybe other students as well).

CodePudding user response：

I suggest changing your Trie type. All the properties of isTreeValid are easily maintained by using Data.Map k v instead of [Edge k v].

And I don't really understand what problem you're talking about with trieLookup. It seems quite simple that if the input key ([e]) is empty, you return the value at the root, and otherwise you descend further into the tree. At what point does the question of what how to treat the root arise? If you need help with that function, include your attempt to solve it and describe what's wrong or where it needs work.