Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Compacts lists of nameservers "a.y.z", "b.y.z" into z(y(a,b))
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
@nbogie

This comment has been minimized.

Copy link
Owner Author

nbogie commented Mar 17, 2011

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.