I've written a simple function for building a prefix tree (and searching):
import qualified Data.List as L import qualified Data.Map as M data Tree a = Empty | Node a [Tree a] deriving (Show, Eq) partitionBy f = map snd . M.toList . M.fromListWith (++) . map (\x -> (f x, [x])) buildTree value dt = Node value (map (\x -> buildTree (head . head $ x) (map tail x)) . grps $ dt) where grps = partitionBy (\x -> head x) . filter (\x -> 0 < length x) treeToList (Node v lst) | length lst > 0 = [v] : foldl (\l x -> (map (v:) $ treeToList x) ++ l)  lst | otherwise = [[v]] searchTree tl  tree = Just (map (init tl ++) . treeToList $ tree) searchTree tl (x:xs) (Node _ lst) | length next_sub_trees > 0 = searchTree (tl ++ [x]) xs (head next_sub_trees) | otherwise = Nothing where next_sub_trees = filter (\ (Node v1 _) -> v1 == x) lst main = do let tree = buildTree ' ' ["hi", "hello", "me", "you", "mouse", "mek", "meee"] print tree print $ treeToList tree print $ searchTree "" "me" tree
I'm new to Haskell. Can anyone help me to make this function better/faster?