| 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
- chunksOf :: Foldable1 f => Int -> f a -> NonEmpty (NonEmpty a)
- chunksOf' :: Foldable f => Int -> f a -> [NonEmpty a]
- 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.
chunksOf :: Foldable1 f => Int -> f a -> NonEmpty (NonEmpty a) Source #
Creates chunks of the given size. The last one may be shorter
pre: n > 0
>>>chunksOf 3 (0 :| [1..10])(0 :| [1,2]) :| [3 :| [4,5],6 :| [7,8],9 :| [10]]
chunksOf' :: Foldable f => Int -> f a -> [NonEmpty a] Source #
Creates chunks of the given size. The last one may be shorter
pre: n > 0
>>>chunksOf' 3 [1..10][1 :| [2,3],4 :| [5,6],7 :| [8,9],10 :| []]
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.