All three Haskell definitions have A list comprehension gives Each version retains the input order and needs no equality or Haskell Ord class constraint on the element type.
filter :: (a -> Bool) -> [a] -> [a]. A recursive list filter isfilter p [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xsfilter p xs = [x | x <- xs, p x]. A right fold givesfilter p = foldr (\x ys -> if p x then x:ys else ys) []Use merge sort, then project the second component of each pair. Under the ordinary Haskell Ord class instance for pairs, “ascending” means lexicographic order, requiring both component types to be ordered:If the intended convention is to sort only by the first component as a sort key, replace
sort :: (Ord a, Ord b) => [(a,b)] -> [b]
sort = map snd . mergeSort
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort left) (mergeSort right)
where (left,right) = splitAt (length xs `div` 2) xs
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ysx <= y by fst x <= fst y and specialize the merge routines to pairs. The weaker signature is then sort :: Ord a => [(a,b)] -> [b], and equal keys keep their original order. These conventions differ when first components tie; the question does not explicitly specify that tie rule.Merging two sorted lists consumes one head per comparison and takes time in their combined length, assuming constant-cost comparisons. Computing the length and splitting also takes time. The balanced recursion therefore satisfiesEach recursion level has total linear work, and there are levels. Thus merge sort takes worst-case time. The final
map snd adds , preserving the bound. Costs of comparing variable-size keys must be included separately.All three denote
iterate :: (a -> a) -> a -> [a], producing . With lazy evaluation, demanding and fully evaluating the first elements costs for f1 and f2, and worst-case for f3, under the unit-cost application assumption.In
f1 the next state is obtained with one new application of g. In f2, the shared binding xs points back to the already generated list; each new element maps g over a shared predecessor once. In f3, the recursive f3 g x is a fresh computation. Producing output position passes through separately constructed map layers, so a strict g causes applications. A non-strict function such as const 0 can avoid work, so the quadratic statement is a worst-case evaluation bound, not a lower bound for every possible g. Merely demanding the outer list spine without its elements is a different cost question. Articles by others on the same topic
There are currently no matching articles.