| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | GHC2021 |
HGeometry.Algorithms.DivideAndConquer
Description
Synopsis
- divideAndConquer :: (Foldable f, Monoid s) => (a -> s) -> f a -> s
- divideAndConquer1 :: (Foldable1 f, Semigroup s) => (a -> s) -> f a -> s
- divideAndConquer1With :: Foldable1 f => (s -> s -> s) -> (a -> s) -> f a -> s
- mergeSorted :: Ord a => NonEmpty a -> NonEmpty a -> NonEmpty a
- mergeSortedLists :: Ord a => [a] -> [a] -> [a]
- mergeSortedBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a -> NonEmpty a
- mergeSortedListsBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
Documentation
divideAndConquer :: (Foldable f, Monoid s) => (a -> s) -> f a -> s Source #
Divide and conquer strategy. See divideAndConquer1.
divideAndConquer1 :: (Foldable1 f, Semigroup s) => (a -> s) -> f a -> s Source #
Divide and conquer strategy
the running time satifies T(n) = 2T(n/2) + M(n),
where M(n) is the time corresponding to the semigroup operation of s on n elements.
divideAndConquer1With :: Foldable1 f => (s -> s -> s) -> (a -> s) -> f a -> s Source #
Divide and conquer strategy
the running time satifies T(n) = 2T(n/2) + M(n),
where M(n) is the time corresponding to the semigroup operation of s on n elements.
mergeSorted :: Ord a => NonEmpty a -> NonEmpty a -> NonEmpty a Source #
Merges two sorted non-Empty lists in linear time.
mergeSortedLists :: Ord a => [a] -> [a] -> [a] Source #
Merges two sorted lists in linear time.
mergeSortedBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a -> NonEmpty a Source #
Given an ordering and two nonempty sequences ordered according to that ordering, merge them.
running time: \(O(n*T)\), where \(n\) is the length of the list, and \(T\) the time required to compare two elements.
mergeSortedListsBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a] Source #
Given an ordering and two nonempty sequences ordered according to that ordering, merge them
running time: \(O(n*T)\), where \(n\) is the length of the list, and \(T\) the time required to compare two elements.