hgeometry-combinatorial-0.12.0.1: Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Algorithms.DivideAndConquer

Description

 
Synopsis

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.