HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Simple prefix tree

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
prefixsimpletree

Problem

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  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?

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.

Context

StackExchange Code Review Q#36107, answer score: 3

Revisions (0)

No revisions yet.