patternMinor
Simple prefix tree
Viewed 0 times
prefixsimpletree
Problem
I've written a simple function for building a prefix tree (and searching):
I'm new to Haskell. Can anyone help me to make this function better/faster?
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 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" treeI'm new to Haskell. Can anyone help me to make this function better/faster?
Solution
At first glance, here are some suggestions-
-
(\x -> head x) can be written as just "head".
-
(\x -> 0
-
Use more built in stuff- There is already a built in groupBy and sortBy functions, you won't have to cast to a map and back. There is already a built in Tree/Forest library, you don't need to create your own.
-
This is more for my (a reader of your code) sanity than you: Wrtie out the function types! :) It took me a while to see what each function was doing, and a type signature would have made it obvious right away. It also helps the compiler give you more meaningfull error messages. Remember, you too will be a reader of your own code in a few months also, you will thank yourself.
-
(\x -> head x) can be written as just "head".
-
(\x -> 0
-
Use more built in stuff- There is already a built in groupBy and sortBy functions, you won't have to cast to a map and back. There is already a built in Tree/Forest library, you don't need to create your own.
-
This is more for my (a reader of your code) sanity than you: Wrtie out the function types! :) It took me a while to see what each function was doing, and a type signature would have made it obvious right away. It also helps the compiler give you more meaningfull error messages. Remember, you too will be a reader of your own code in a few months also, you will thank yourself.
Context
StackExchange Code Review Q#36107, answer score: 3
Revisions (0)
No revisions yet.