Searching rose tree in Haskell

Question

I'm trying to write a function searching for a given element in a rose tree and returning it's location.

It may be clearer when I show you what I already got:

Given a tree with a definition:

data Tree text = Node value [Tree value]

for example:

test = Node "1" [
          Node "11" [
               Node "111" [], 
               Node "112" [
                  Node "1121" [], Node "1122" [], Node "1123" []
               ]
          ], 
          Node "12" []
      ]


            1
      11         12
111      112    
     1121 1122 1123

I'm looking for a function search:

search :: String -> Tree String -> [Integer]

search 1123 test -> should return [1,2,3]
- first subtree of 1=11 -> 2nd subtree of 11=112, 3rd subtree of 112=1123

I know how to iterate through tree,

display (Node v xs) = v ++ concatMap display xs

But have no idea how can I assign integer value to every element of subtrees array and additionally pass it recursively from upper to lower parts of the tree. Can you guys direct me where/how to look for a solution? I'm very new to Haskell..

Daniel Fischer Daniel Fischer · Accepted Answer · 2012-06-02T18:26:44

The easiest way is to let the function return the list of all paths to a node with the desired data (there should only ever be at most one in the tree, I suppose, but that doesn't matter) first, and then use the first of these:

searchList :: (Eq a) => a -> Tree a -> [[Integer]]
searchList val (Node dat subs)
    | val == dat = [[]]  -- empty path
    | otherwise  = concat [map (c:) (searchList val t) | (c,t) <- zip [1 .. ] subs]

search :: Eq a => a -> Tree a -> [Integer]
search val t = case searchList val t of
                 (p:_) -> p
                 _ -> error "Value not found"

If Daniel Wagner's suspicion is correct and your trees are tries, you can search more efficiently, but the principle remains the same, however, since we now know that we either have one node with the desired data or none, the result is more appropriately a Maybe [Integer]:

import Data.List (isPrefixOf)
import Control.Monad -- for the MonadPlus instance of Maybe

searchTrie :: String -> Tree String -> Maybe [Integer]
searchTrie target (Node val subs)
    | val == target = Just []
    | val `isPrefixOf` target = case dropWhile smaller (zip [1 .. ] subs) of
                                  ((c,t):_) -> fmap (c:) $ searchTrie target t
                                  _ -> Nothing
    | otherwise = Nothing
      where
        smaller (_,Node v _) = v < take (length v) target

Searching rose tree in Haskell

1 Answers