Compacts lists of nameservers "a.y.z", "b.y.z" into z(y(a,b))

CompactNameServers.hs

import qualified Data.List.Utils as U
import Data.List (sort, groupBy, intercalate)
import Data.Function (on)

-- -------------------------------------------------
-- example data
-- -------------------------------------------------
examples :: [(Domain, [NameServer])]
examples = [("pachube.com",["7.f.c",
                            "5.f.c",
                            "0.b.c",
                            "6.b.x",
                            "6.b.x.z",
                            "1.f.c",
                            "2.f.c",
                          "9.8.f.c",
                              "f.c",
                            "3.b.i",
                            "4.b.i", 
                                "m",
                              "M.m"])]
exampleNSes :: [NameServer]
exampleNSes = snd $ head examples

-- -------------------------------------------------
-- program
-- -------------------------------------------------
-- split something like "a.b.com" into ["a", "b", "com"]
splitNS :: NameServer -> [String]
splitNS ns = reverse $ U.split "." ns

-- these types are to make the following function type declarations more readable
type Domain = String
type NameServer = String
type NSPiece = String  -- a nameserver piece, like "www" or "com" or "google"
type NSSeq = [NSPiece]   -- a sequence of nameserver pieces ["www", "google", "com"]

-- the tree we'll build from the list of domains.
data NSTree a = Node a [NSTree a] 

-- Have NSTree support "show" function.
instance (Show a) =>  Show (NSTree a) where
  show (Node s []) = show s
  show (Node s xs) = show s ++ quote "(" ")" (intercalate "," (map show xs))
    where quote l r m = l ++ m ++ r

-- build a tree from list of domains
makeTrees :: [NSSeq] -> [NSTree NSPiece]
makeTrees [] =  []
makeTrees seqs = map makeTree gs
   where gs = groupBy ((==) `on` head) $ sort seqs
         makeTree :: [NSSeq] -> NSTree NSPiece
         makeTree full@((h:_):_) = Node h $ makeTrees $ filter (not . null) $ map tail full

-- As a demo, take the example nameservers, make them into a list of trees, 
-- print the trees out as strings.
main = putStrLn $ unlines $ map show $ makeTrees $ map splitNS exampleNSes

Limitations: Does not preserve address b.c when there is also a child sequence a.b.c. This is easily addressed by having a boolean on each node indicating the node is also an endpoint, or by having all endpoints have a child of Terminal.