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?


At first glance, here are some suggestions-

  1. (\x -> head x) can be written as just "head".

  2. (\x -> 0 < length x) can be written as "(0 <) . length (this is point free notation, which I prefer, although some people may prefer your way.

  3. 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.

  4. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.