module Data.Weighting.GSC where
import Data.List (foldl')
import Data.Clustering.Hierarchical (Dendrogram(..))
gsc :: Fractional d => Dendrogram d a -> Dendrogram d (a, d)
gsc (Leaf x) = Leaf (x,1)
gsc dendro = let (wsum, nsum, r) = go wfinal undefined [] dendro
wfinal = (wsum / fromIntegral nsum)
in r
where
position (Leaf _) = 0
position (Branch d _ _) = d
go wfinal _ cs (Branch d l r) =
let (wl, nl, l') = go wfinal d ((el / wl) : cs) l
(wr, nr, r') = go wfinal d ((er / wr) : cs) r
el = d position l
er = d position r
wsum = wl + wr + el + er
nsum = nl + nr
in wsum `seq` nsum `seq` (wsum, nsum, Branch d l' r')
go wfinal d cs (Leaf x) =
let w = foldl' (\curw c -> curw + curw * c) d (tail cs)
in (0, 1 :: Int, Leaf (x, w / wfinal))