-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | Fast algorithms for single, average/UPGMA and complete linkage clustering.
--   
--   This package provides a function to create a dendrogram from a list of
--   items and a distance function between them. Initially a singleton
--   cluster is created for each item, and then new, bigger clusters are
--   created by merging the two clusters with least distance between them.
--   The distance between two clusters is calculated according to the
--   linkage type. The dendrogram represents not only the clusters but also
--   the order on which they were created.
--   
--   This package has many implementations with different performance
--   characteristics. There are SLINK and CLINK algorithm implementations
--   that are optimal in both space and time. There are also naive
--   implementations using a distance matrix. Using the dendrogram
--   function from Data.Clustering.Hierarchical automatically
--   chooses the best implementation we have.
--   
--   Changes in version 0.4:
--   
--   
--   
- Specialize the distance type to Double for efficiency reasons.
--   It's uncommon to use distances other than Double.
--   
- Implement SLINK and CLINK. These are optimal algorithms in both
--   space and time for single and complete linkage, respectively, running
--   in O(n^2) time and O(n) space.
--   
- Reorganized internal implementation.
--   
- Some performance improvements for the naive implementation.
--   
- Better test coverage. Also, performance improvements for the test
--   suite, now running in 3 seconds (instead of one minute).
--   
--   
--   Changes in version 0.3.1.2 (version 0.3.1.1 was skipped):
--   
--   
--   
- Added tests for many things. Use cabal test =).
--   
--   
--   Changes in version 0.3.1:
--   
--   
--   
- Works with containers 0.4 (thanks, Doug Beardsley).
--   
- Removed some internal unnecessary overheads and added some
--   strictness.
--   
--   
--   Changes in version 0.3.0.1:
--   
--   
--   
- Listed changes of unreleased version 0.2.
--   
--   
--   Changes in version 0.3:
--   
--   
--   
- Added function cutAt.
--   
- Fixed complexity in Haddock comments.
--   
--   
--   Changes in version 0.2:
--   
--   
--   
- Added function elements.
--   
- Added separate functions for each linkage type. This may be useful
--   if you want to create a dendrogram and your distance data type isn't
--   an instance of Floating.
--   
@package hierarchical-clustering
@version 0.4.7

module Data.Clustering.Hierarchical.Internal.Types

-- | Data structure for storing hierarchical clusters. The distance between
--   clusters is stored on the branches. Distances between leafs are the
--   distances between the elements on those leafs, while distances between
--   branches are defined by the linkage used (see Linkage).
data Dendrogram a

-- | The leaf contains the item a itself.
Leaf :: a -> Dendrogram a

-- | Each branch connects two clusters/dendrograms that are d
--   distance apart.
Branch :: {-# UNPACK #-} !Distance -> Dendrogram a -> Dendrogram a -> Dendrogram a

-- | The linkage type determines how the distance between clusters will be
--   calculated. These are the linkage types currently available on this
--   library.
data Linkage

-- | The distance between two clusters a and b is the
--   minimum distance between an element of a and an
--   element of b.
SingleLinkage :: Linkage

-- | The distance between two clusters a and b is the
--   maximum distance between an element of a and an
--   element of b.
CompleteLinkage :: Linkage

-- | The same as CompleteLinkage, but using the CLINK algorithm.
--   It's much faster however doesn't always give the best complete linkage
--   dendrogram.
CLINK :: Linkage

-- | Unweighted Pair Group Method with Arithmetic mean, also called
--   "average linkage". The distance between two clusters a and
--   b is the arithmetic average between the distances of
--   all elements in a to all elements in b.
UPGMA :: Linkage

-- | This method is usually wrongly called "average linkage". The distance
--   between cluster a = a1 U a2 (that is, cluster a was
--   formed by the linkage of clusters a1 and a2) and an
--   old cluster b is (d(a1,b) + d(a2,b)) / 2. So when
--   clustering two elements to create a cluster, this method is the same
--   as UPGMA. However, in general when joining two clusters this method
--   assigns equal weights to a1 and a2, while UPGMA
--   assigns weights proportional to the number of elements in each
--   cluster. See, for example:
--   
--   
--   
--   
- http://www.cs.tau.ac.il/~rshamir/algmb/00/scribe00/html/lec08/node21.html,
--   which defines the real UPGMA and gives the equation to calculate the
--   distance between an old and a new cluster.
--   
--   
- http://github.com/JadeFerret/ai4r/blob/master/lib/ai4r/clusterers/average_linkage.rb,
--   code for "average linkage" on ai4r library implementing what we call
--   here FakeAverageLinkage and not UPGMA.
--   
FakeAverageLinkage :: Linkage

-- | A distance is simply a synonym of Double for efficiency.
type Distance = Double
instance GHC.Internal.Enum.Enum Data.Clustering.Hierarchical.Internal.Types.Linkage
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Clustering.Hierarchical.Internal.Types.Dendrogram a)
instance GHC.Classes.Eq Data.Clustering.Hierarchical.Internal.Types.Linkage
instance GHC.Internal.Data.Foldable.Foldable Data.Clustering.Hierarchical.Internal.Types.Dendrogram
instance GHC.Internal.Base.Functor Data.Clustering.Hierarchical.Internal.Types.Dendrogram
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Clustering.Hierarchical.Internal.Types.Dendrogram a)
instance GHC.Classes.Ord Data.Clustering.Hierarchical.Internal.Types.Linkage
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Clustering.Hierarchical.Internal.Types.Dendrogram a)
instance GHC.Internal.Show.Show Data.Clustering.Hierarchical.Internal.Types.Linkage
instance GHC.Internal.Data.Traversable.Traversable Data.Clustering.Hierarchical.Internal.Types.Dendrogram

-- | Implementations that are optimal in space and time.
module Data.Clustering.Hierarchical.Internal.Optimal

-- | O(n^2) time and O(n) space. Calculates a complete,
--   rooted dendrogram for a list of items using single linkage with the
--   SLINK algorithm. This algorithm is optimal in space and time.
--   
--   
--   
- Reference R. Sibson (1973). "SLINK: an optimally efficient
--   algorithm for the single-link cluster method". The Computer
--   Journal (British Computer Society) 16 (1): 30-34.
--   
singleLinkage :: [a] -> (a -> a -> Distance) -> Dendrogram a

-- | O(n^2) time and O(n) space. Calculates a complete,
--   rooted dendrogram for a list of items using complete linkage with the
--   CLINK algorithm. This algorithm is optimal in space and time.
--   
--   
--   
- Reference D. Defays (1977). "An efficient algorithm for a
--   complete link method". The Computer Journal (British Computer
--   Society) 20 (4): 364-366.
--   
completeLinkage :: [a] -> (a -> a -> Distance) -> Dendrogram a

module Data.Clustering.Hierarchical.Internal.DistanceMatrix

-- | O(n^3) time and O(n^2) space. Calculates a complete,
--   rooted dendrogram for a list of items using single linkage with the
--   naïve algorithm using a distance matrix.
singleLinkage :: [a] -> (a -> a -> Distance) -> Dendrogram a

-- | O(n^3) time and O(n^2) space. Calculates a complete,
--   rooted dendrogram for a list of items using complete linkage with the
--   naïve algorithm using a distance matrix.
completeLinkage :: [a] -> (a -> a -> Distance) -> Dendrogram a

-- | O(n^3) time and O(n^2) space. Calculates a complete,
--   rooted dendrogram for a list of items using UPGMA with the naïve
--   algorithm using a distance matrix.
upgma :: [a] -> (a -> a -> Distance) -> Dendrogram a

-- | O(n^3) time and O(n^2) space. Calculates a complete,
--   rooted dendrogram for a list of items using fake average linkage with
--   the naïve algorithm using a distance matrix.
fakeAverageLinkage :: [a] -> (a -> a -> Distance) -> Dendrogram a
instance GHC.Classes.Eq Data.Clustering.Hierarchical.Internal.DistanceMatrix.Cluster
instance GHC.Classes.Ord Data.Clustering.Hierarchical.Internal.DistanceMatrix.Cluster
instance GHC.Internal.Show.Show Data.Clustering.Hierarchical.Internal.DistanceMatrix.Cluster

module Data.Clustering.Hierarchical

-- | Data structure for storing hierarchical clusters. The distance between
--   clusters is stored on the branches. Distances between leafs are the
--   distances between the elements on those leafs, while distances between
--   branches are defined by the linkage used (see Linkage).
data Dendrogram a

-- | The leaf contains the item a itself.
Leaf :: a -> Dendrogram a

-- | Each branch connects two clusters/dendrograms that are d
--   distance apart.
Branch :: {-# UNPACK #-} !Distance -> Dendrogram a -> Dendrogram a -> Dendrogram a

-- | A distance is simply a synonym of Double for efficiency.
type Distance = Double

-- | List of elements in a dendrogram.
elements :: Dendrogram a -> [a]

-- | dendro `cutAt` threshold cuts the dendrogram dendro
--   at all branches which have distances strictly greater than
--   threshold.
--   
--   For example, suppose we have
--   
--   
--   dendro = Branch 0.8
--              (Branch 0.5
--                (Branch 0.2
--                  (Leaf 'A')
--                  (Leaf 'B'))
--                (Leaf 'C'))
--              (Leaf 'D')
--   
--   
--   Then:
--   
--   
--   dendro `cutAt` 0.9 == dendro `cutAt` 0.8 == [dendro] -- no changes
--   dendro `cutAt` 0.7 == dendro `cutAt` 0.5 == [Branch 0.5 (Branch 0.2 (Leaf 'A') (Leaf 'B')) (Leaf 'C'), Leaf 'D']
--   dendro `cutAt` 0.4 == dendro `cutAt` 0.2 == [Branch 0.2 (Leaf 'A') (Leaf 'B'), Leaf 'C', Leaf 'D']
--   dendro `cutAt` 0.1 == [Leaf 'A', Leaf 'B', Leaf 'C', Leaf 'D'] -- no branches at all
--   
cutAt :: Dendrogram a -> Distance -> [Dendrogram a]

-- | The linkage type determines how the distance between clusters will be
--   calculated. These are the linkage types currently available on this
--   library.
data Linkage

-- | The distance between two clusters a and b is the
--   minimum distance between an element of a and an
--   element of b.
SingleLinkage :: Linkage

-- | The distance between two clusters a and b is the
--   maximum distance between an element of a and an
--   element of b.
CompleteLinkage :: Linkage

-- | The same as CompleteLinkage, but using the CLINK algorithm.
--   It's much faster however doesn't always give the best complete linkage
--   dendrogram.
CLINK :: Linkage

-- | Unweighted Pair Group Method with Arithmetic mean, also called
--   "average linkage". The distance between two clusters a and
--   b is the arithmetic average between the distances of
--   all elements in a to all elements in b.
UPGMA :: Linkage

-- | This method is usually wrongly called "average linkage". The distance
--   between cluster a = a1 U a2 (that is, cluster a was
--   formed by the linkage of clusters a1 and a2) and an
--   old cluster b is (d(a1,b) + d(a2,b)) / 2. So when
--   clustering two elements to create a cluster, this method is the same
--   as UPGMA. However, in general when joining two clusters this method
--   assigns equal weights to a1 and a2, while UPGMA
--   assigns weights proportional to the number of elements in each
--   cluster. See, for example:
--   
--   
--   
--   
- http://www.cs.tau.ac.il/~rshamir/algmb/00/scribe00/html/lec08/node21.html,
--   which defines the real UPGMA and gives the equation to calculate the
--   distance between an old and a new cluster.
--   
--   
- http://github.com/JadeFerret/ai4r/blob/master/lib/ai4r/clusterers/average_linkage.rb,
--   code for "average linkage" on ai4r library implementing what we call
--   here FakeAverageLinkage and not UPGMA.
--   
FakeAverageLinkage :: Linkage

-- | Calculates a complete, rooted dendrogram for a list of items and a
--   linkage type. The following are the time and space complexities for
--   each linkage:
--   
--   
--   
- SingleLinkage O(n^2) time and O(n)
--   space, using the SLINK algorithm. This algorithm is optimal in both
--   space and time and gives the same answer as the naive algorithm using
--   a distance matrix.
--   
- CompleteLinkage O(n^3) time and O(n^2)
--   space, using the naive algorithm with a distance matrix. Use
--   CLINK if you need more performance.
--   
- Complete linkage with CLINK O(n^2) time and
--   O(n) space, using the CLINK algorithm. Note that this algorithm
--   doesn't always give the same answer as the naive algorithm using a
--   distance matrix, but it's much faster.
--   
- UPGMA O(n^3) time and O(n^2) space,
--   using the naive algorithm with a distance matrix.
--   
- FakeAverageLinkage O(n^3) time and
--   O(n^2) space, using the naive algorithm with a distance
--   matrix.
--   
dendrogram :: Linkage -> [a] -> (a -> a -> Distance) -> Dendrogram a
