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


-- | Provides folds which try to combine elements in a balanced way.
--   
--   Provides folds which try to combine elements in a balanced way. These
--   can be useful for constructing balanced binary trees, or more stable
--   summation.
@package treefold
@version 0.2.0.0


-- | This module provides strict versions of the functions from
--   <a>Data.TreeFold</a>.
module Data.TreeFold.Strict

-- | A strict version of <a>treeFold</a>.
--   
--   <pre>
--   &gt;&gt;&gt; (treeFold (:*:) Empty . map Leaf) [1,2,3,4]
--   (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--   
--   &gt;&gt;&gt; (treeFold (:*:) Empty . map Leaf) [1,2,3,4,5]
--   ((Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)) :*: Leaf 5
--   
--   &gt;&gt;&gt; treeFold (+) 0 (replicate 10 9.9)
--   99.0
--   </pre>
treeFold :: (a -> a -> a) -> a -> [a] -> a

-- | A strict version of <a>treeFoldMap</a>.
--   
--   <pre>
--   &gt;&gt;&gt; treeFoldMap Leaf (:*:) Empty [1,2,3,4]
--   (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--   </pre>
treeFoldMap :: (b -> a) -> (a -> a -> a) -> a -> [b] -> a

-- | A strict version of <a>treeFoldNonEmpty</a>.
treeFoldNonEmpty :: (a -> a -> a) -> NonEmpty a -> a

-- | A strict version of <a>treeFoldMapNonEmpty</a>.
treeFoldMapNonEmpty :: (b -> a) -> (a -> a -> a) -> NonEmpty b -> a


-- | This module provides folds which try to combine elements in a balanced
--   way. These can be useful for constructing balanced binary trees, or
--   more stable summation.
--   
--   Adapted from <a>here</a>.
--   
--   For a strict version see <a>Data.TreeFold.Strict</a>.
module Data.TreeFold

-- | Reduces a list of values using a binary operation, trying as much as
--   possible to balance. For instance, given the above binary tree type,
--   the operation:
--   
--   <pre>
--   &gt;&gt;&gt; (treeFold (:*:) Empty . map Leaf) [1,2,3,4]
--   (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--   </pre>
--   
--   Will construct a balanced binary tree, whereas the equivalent using a
--   normal fold:
--   
--   <pre>
--   &gt;&gt;&gt; foldr ((:*:) . Leaf) Empty [1,2,3,4]
--   Leaf 1 :*: (Leaf 2 :*: (Leaf 3 :*: (Leaf 4 :*: Empty)))
--   </pre>
--   
--   Will construct a right-heavy tree.
--   
--   <pre>
--   &gt;&gt;&gt; (treeFold (:*:) Empty . map Leaf) [1,2,3,4,5]
--   ((Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)) :*: Leaf 5
--   </pre>
--   
--   Other uses for this function include more stable floating-point
--   summation. The following sum algorithm:
--   
--   <pre>
--   &gt;&gt;&gt; treeFold (+) 0 (replicate 10 9.9)
--   99.0
--   </pre>
--   
--   Will have O(log n) error growth for summing n numbers, in comparison
--   to O(n) for:
--   
--   <pre>
--   &gt;&gt;&gt; sum (replicate 10 9.9)
--   99.00000000000001
--   </pre>
--   
--   For a strict version of this function see <a>treeFold</a>.
treeFold :: (a -> a -> a) -> a -> [a] -> a

-- | Perform a tree fold after a map.
--   
--   <pre>
--   &gt;&gt;&gt; treeFoldMap Leaf (:*:) Empty [1,2,3,4]
--   (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--   </pre>
--   
--   For a strict version of this function see <a>treeFoldMap</a>.
treeFoldMap :: (b -> a) -> (a -> a -> a) -> a -> [b] -> a

-- | Perform a tree fold on a non empty input. For a strict version of this
--   function see <a>treeFoldNonEmpty</a>.
treeFoldNonEmpty :: (a -> a -> a) -> NonEmpty a -> a

-- | Perform a tree fold after a map on non-empty input. For a strict
--   version of this function see <a>treeFoldMapNonEmpty</a>.
treeFoldMapNonEmpty :: (b -> a) -> (a -> a -> a) -> NonEmpty b -> a


-- | This module provides folds which try to combine elements in a balanced
--   way. These can be useful for constructing balanced binary trees, or
--   more stable summation.
--   
--   Adapted from <a>here</a>.
--   
--   This is a version of <a>Data.TreeFold</a> which works on any
--   <a>Foldable</a> container, rather than just lists.
module Data.TreeFold.Foldable

-- | A version of <a>treeFold</a> which works on any <a>Foldable</a>.
treeFold :: Foldable f => (a -> a -> a) -> a -> f a -> a

-- | A version of <a>treeFoldMap</a> which works on any <a>Foldable</a>.
treeFoldMap :: Foldable f => (b -> a) -> (a -> a -> a) -> a -> f b -> a


-- | This module provides parallel versions of the functions from
--   <a>Data.TreeFold</a>.
module Data.TreeFold.Parallel

-- | A parallel version of <a>treeFold</a>.
--   
--   <pre>
--   &gt;&gt;&gt; (treeFold (:*:) Empty . map Leaf) [1,2,3,4]
--   (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--   
--   &gt;&gt;&gt; (treeFold (:*:) Empty . map Leaf) [1,2,3,4,5]
--   ((Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)) :*: Leaf 5
--   
--   &gt;&gt;&gt; treeFold (+) 0 (replicate 10 9.9)
--   99.0
--   </pre>
treeFold :: (a -> a -> a) -> a -> [a] -> a

-- | A parallel version of <a>treeFoldNonEmpty</a>.
treeFoldNonEmpty :: (a -> a -> a) -> NonEmpty a -> a

-- | A parallel version of <a>treeFoldMap</a>.
--   
--   <pre>
--   &gt;&gt;&gt; treeFoldMap Leaf (:*:) Empty [1,2,3,4]
--   (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--   </pre>
treeFoldMap :: (b -> a) -> (a -> a -> a) -> a -> [b] -> a

-- | A parallel version of <a>treeFoldMapNonEmpty</a>.
treeFoldMapNonEmpty :: (b -> a) -> (a -> a -> a) -> NonEmpty b -> a