| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Algorithms.DivideAndConquer
Synopsis
- divideAndConquer :: Monoid s => (a -> s) -> [a] -> s
- divideAndConquer1 :: Semigroup s => (a -> s) -> NonEmpty a -> s
- divideAndConquer1With :: (s -> s -> s) -> (a -> s) -> NonEmpty 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 :: Monoid s => (a -> s) -> [a] -> s Source #
Divide and conquer for
divideAndConquer1 :: Semigroup s => (a -> s) -> NonEmpty a -> s Source #
Divide and conquer strategy
the running time is: O(n*L) + T(n) = 2T(n/2) + M(n)
where M(n) is the time corresponding to the semigroup operation of s
divideAndConquer1With :: (s -> s -> s) -> (a -> s) -> NonEmpty a -> s Source #
Divide and conquer strategy
the running time is: O(n*L) + T(n) = 2T(n/2) + M(n)
where M(n) is the time corresponding to the merge operation s
mergeSortedLists :: Ord a => [a] -> [a] -> [a] Source #
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
mergeSortedListsBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a] Source #
Given an ordering and two nonempty sequences ordered according to that ordering, merge them