s_and_d.hs

-- Clustering algorithm v2

destroy _     E     = E
destroy 1 (L _)     = E
destroy _ (L x)     = L x
destroy n x@(N l r) | count x == n = E
                    | count x  > n = N (destroy n l) (destroy n r)
                    | otherwise    = x

search _ E          = []
search 1 (L x)      = [L x]
search _ (L x)      = []
search n x@(N l r)  | count x == n = [x]
                    | count x  > n = search n l ++ search n r
                    | otherwise    = []

expand n = takeWhile (> 0) $ concatMap ex [0..] where ex x = [n-x,n+x]

scanner (t,_) n = (destroy n t, search n t)

cluster n t = concatMap (map leaves . snd) $ scanl scanner (t,[]) (expand (count t `div` n))