Simple BK-tree implementation in Haskell

BKTree.hs

data BKTree a = Node a [(Int, BKTree a)] deriving (Eq, Show)

lev :: Eq a => [a] -> [a] -> Int
lev [] b = length b
lev a [] = length a
lev a b = minimum [ lev (init a) b + 1
                  , lev a (init b) + 1
                  , lev (init a) (init b) + (if last a == last b then 0 else 1)
                  ]

add :: String -> BKTree String -> BKTree String
add word (Node w xs) =
	let d = lev w word
	    addAt [] = [(d, Node word [])]
	    addAt (node@(d', n):ns)
	    	| d' == d = (d', add word n) : ns
	    addAt (n:ns) = n : addAt ns
	in Node w (addAt xs)

search :: String -> Int -> BKTree String -> [String]
search word k (Node word' ns) =
	let d = lev word word'
	    relevantNodes = filter (\(d', _) -> abs (d' - d) <= k) ns
	    next = concatMap (search word k . snd) relevantNodes in
	if d <= k then word' : next
	else next

main = do
	let tree = Node "book" []
	let wordSet = ["books", "boo", "cake", "cape", "boon", "cook", "cart"]
	let tree' = foldl (flip add) tree wordSet

	print tree'
	print $ search "caqe" 1 tree'