-- 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.1.0.0
-- | This module provides strict versions of the functions from
-- Data.TreeFold.
module Data.TreeFold.Strict
-- | A strict version of treeFold.
--
--
-- >>> (treeFold (:*:) Empty . map Leaf) [1,2,3,4]
-- (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--
-- >>> (treeFold (:*:) Empty . map Leaf) [1,2,3,4,5]
-- ((Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)) :*: Leaf 5
--
-- >>> treeFold (+) 0 (replicate 10 9.9)
-- 99.0
--
treeFold :: (a -> a -> a) -> a -> [a] -> a
-- | A strict version of treeFoldMap.
--
--
-- >>> treeFoldMap Leaf (:*:) Empty [1,2,3,4]
-- (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--
treeFoldMap :: (b -> a) -> (a -> a -> a) -> a -> [b] -> a
-- | A strict version of pairFold.
--
--
-- >>> pairFold (++) ["a","b","c","d","e"]
-- ["ab","cd","e"]
--
pairFold :: (a -> a -> a) -> [a] -> [a]
-- | A strict version of pairFoldMap.
--
--
-- >>> pairFoldMap (:[]) (++) "abcde"
-- ["ab","cd","e"]
--
pairFoldMap :: (b -> a) -> (a -> a -> a) -> [b] -> [a]
-- | A strict version of treeFoldNonEmpty.
treeFoldNonEmpty :: (a -> a -> a) -> NonEmpty a -> a
-- | A strict version of treeFoldMapNonEmpty.
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 here.
--
-- For a strict version see Data.TreeFold.Strict.
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:
--
--
-- >>> (treeFold (:*:) Empty . map Leaf) [1,2,3,4]
-- (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--
--
-- Will construct a balanced binary tree, whereas the equivalent using a
-- normal fold:
--
--
-- >>> foldr ((:*:) . Leaf) Empty [1,2,3,4]
-- Leaf 1 :*: (Leaf 2 :*: (Leaf 3 :*: (Leaf 4 :*: Empty)))
--
--
-- Will construct a right-heavy tree.
--
--
-- >>> (treeFold (:*:) Empty . map Leaf) [1,2,3,4,5]
-- ((Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)) :*: Leaf 5
--
--
-- Other uses for this function include more stable floating-point
-- summation. The following sum algorithm:
--
--
-- >>> treeFold (+) 0 (replicate 10 9.9)
-- 99.0
--
--
-- Will have O(log n) error growth for summing n numbers, in comparison
-- to O(n) for:
--
--
-- >>> sum (replicate 10 9.9)
-- 99.00000000000001
--
--
-- For a strict version of this function see treeFold.
treeFold :: (a -> a -> a) -> a -> [a] -> a
-- | Perform a tree fold after a map.
--
--
-- >>> treeFoldMap Leaf (:*:) Empty [1,2,3,4]
-- (Leaf 1 :*: Leaf 2) :*: (Leaf 3 :*: Leaf 4)
--
--
-- For a strict version of this function see treeFoldMap.
treeFoldMap :: (b -> a) -> (a -> a -> a) -> a -> [b] -> a
-- | Apply a combining function to pairs in a list.
--
--
-- >>> pairFold (++) ["a","b","c","d","e"]
-- ["ab","cd","e"]
--
--
-- For a strict version of this function see pairFold.
pairFold :: (a -> a -> a) -> [a] -> [a]
-- | Apply a combining function to pairs in a list, after a map.
--
--
-- >>> pairFoldMap (:[]) (++) "abcde"
-- ["ab","cd","e"]
--
--
-- For a strict version of this function see pairFoldMap.
pairFoldMap :: (b -> a) -> (a -> a -> a) -> [b] -> [a]
-- | Perform a tree fold on a non empty input. For a strict version of this
-- function see treeFoldNonEmpty.
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 treeFoldMapNonEmpty.
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 here.
--
-- This is a version of Data.TreeFold which works on any
-- Foldable container, rather than just lists.
module Data.TreeFold.Foldable
-- | A version of treeFold which works on any Foldable.
treeFold :: Foldable f => (a -> a -> a) -> a -> f a -> a
-- | A version of treeFoldMap which works on any Foldable.
treeFoldMap :: Foldable f => (b -> a) -> (a -> a -> a) -> a -> f b -> a
-- | This is a parallel version of Data.TreeFold: all the functions
-- here take a Strategy which specifies how to evaluate the fold
-- in parallel, and a number for the size of the chunks evaluated in
-- parallel. The number works like this. If you imagine the treefold as
-- being executed on a list of 32 elements like so:
--
--
-- 5_______________________________________________________________
-- /\
-- / \
-- / \
-- / \
-- / \
-- / \
-- / \
-- / \
-- / \
-- / \
-- / \
-- / \
-- / \
-- / \
-- / \
-- 4________________/______________________________\_______________
-- /\ /\
-- / \ / \
-- / \ / \
-- / \ / \
-- / \ / \
-- / \ / \
-- / \ / \
-- 3________/______________\________________/______________\_______
-- /\ /\ /\ /\
-- / \ / \ / \ / \
-- / \ / \ / \ / \
-- 2____/______\________/______\________/______\________/______\___
-- /\ /\ /\ /\ /\ /\ /\ /\
-- 1__/__\____/__\____/__\____/__\____/__\____/__\____/__\____/__\_
-- 0_/\__/\__/\__/\__/\__/\__/\__/\__/\__/\__/\__/\__/\__/\__/\__/\
--
--
-- Depending on what number you supply, the tree fold will run lazily
-- until it gets to the corresponding point in the diagram above. Then,
-- it will evaluate the subtrees in parallel according to the strategy
-- supplied. It will then start again on the list of evaluated values,
-- continuing until it gets to only one.
module Data.TreeFold.Parallel
-- | A parallel version of treeFold.
treeFold :: Strategy a -> Int -> (a -> a -> a) -> a -> [a] -> a
-- | A parallel version of treeFoldNonEmpty.
treeFoldNonEmpty :: Strategy a -> Int -> (a -> a -> a) -> NonEmpty a -> a
-- | A parallel version of treeFoldMap.
treeFoldMap :: Strategy a -> Int -> (b -> a) -> (a -> a -> a) -> a -> [b] -> a
-- | A parallel version of treeFoldMapNonEmpty.
treeFoldMapNonEmpty :: Strategy a -> Int -> (b -> a) -> (a -> a -> a) -> NonEmpty b -> a
rpar :: Strategy a