The following shared step consumes exactly one input element per recursive call of The helper's input consists of nonempty runs. If its first run starts with
group1:prependRun :: Eq a => a -> [[a]] -> [[a]]
prependRun x xss = (x:same):rest
where
~(same,rest) = case xss of
[] -> ([],[])
run@(y:_):runs
| x == y -> (run,runs)
| otherwise -> ([],xss)
group1 :: Eq a => [a] -> [[a]]
group1 [] = []
group1 (x:xs) = prependRun x (group1 xs)x, prepend x to that run; otherwise create a new singleton run. Structural induction proves that these are the maximal equal runs in order. The irrefutable pair binding ~(same,rest) preserves lazy evaluation: the first output group exposes its initial x without inspecting the recursively grouped tail. Thus even an infinite constant input can expose the first group and each finite prefix of that group. Finite inputs take linear time when equality tests take constant time.Use the same step from part (a):The right fold obeys
groupFold :: Eq a => [a] -> [[a]]
groupFold = foldr prependRun []groupFold [] = [] and groupFold (x:xs) = prependRun x (groupFold xs), exactly the recursive equations already proved. Both implementations give the bottom value for an entirely undefined input spine. Their equal behaviour on finite partial lists, together with definable continuity, establishes equality on infinite lazy lists as well. The helper's irrefutable binding is what lets the first run be produced without demanding that all subsequent runs already exist.A call can instead produce an entire run and recurse on the unused input:Here
groupRuns :: Eq a => [a] -> [[a]]
groupRuns [] = []
groupRuns (x:xs) = (x:ys) : groupRuns zs
where (ys,zs) = span (== x) xsspan returns the longest matching prefix of a list and the remaining suffix of a list. Thus x:ys is the first maximal run, while zs begins the next run or is empty. Each recursive call produces one outer output element. The lazy pair binding permits output of the first constructor before the run's endpoint is known. Every finite input position is scanned a bounded number of times, so the time complexity is for unit-cost equality, including output construction.[ref]The list unfold operation has the following type signature and definition:The seed is the unprocessed suffix of a list. An empty seed terminates the unfold; otherwise
unfoldr :: (s -> Maybe (a,s)) -> s -> [a]
unfoldr step s = case step s of
Nothing -> []
Just (x,s') -> x : unfoldr step s'
groupUnfold :: Eq a => [a] -> [[a]]
groupUnfold = unfoldr next
where
next [] = Nothing
next (x:xs) = Just (x:ys,zs)
where (ys,zs) = span (== x) xsnext returns the first maximal run and precisely the seed for the next call. Substituting the definition of unfoldr recovers part (c)'s equations, proving correctness. The Just pair and first group constructor can be produced before span finishes, retaining the same lazy evaluation behaviour.Share the recursive pair and inspect the predicate once:For a finite list, structural induction establishes that
partition :: (a -> Bool) -> [a] -> ([a],[a])
partition _ [] = ([],[])
partition p (x:xs)
| p x = (x:yes,no)
| otherwise = (yes,x:no)
where ~(yes,no) = partition p xsyes and no are the two required filtered subsequences. The guard evaluates p x once and prepends x to exactly one output, preserving input order in both. Fully consuming both results uses predicate applications and additional work. Sharing the recursive result avoids making separate recursive traversals. This is a stable list partition.Choose the first unclassified element as the next equivalence class representative:Assume the
equiv :: Eq a => [a] -> [[a]]
equiv [] = []
equiv (x:xs) = (x:same) : equiv rest
where ~(same,rest) = partition (== x) xsEq instance is an equivalence relation. The stable list partition collects every later occurrence equivalent to x, and rest contains none of that equivalence class. Induction therefore gives exactly one group per class, preserving order within each group and ordering groups by their first occurrence. For distinct classes, each input element is tested against at most representatives: the cost is and in the all-distinct worst case; a single class takes .The equality-only grouping lower bound shows that this worst case is unavoidable in the unrestricted equality-oracle model. On an all-distinct input, an untested pair could instead be equal without changing any observed comparison. Certifying that all elements belong to different classes therefore requires all pairwise equality tests.
A compatible
Ord instance supplies a total order, so use comparison sort to put equal values together in time and then group adjacent equals in linear time. To preserve the first-occurrence group ordering of part (f), first tag every element with its original index and stable sorting by value. Group the sorted records by value; stability preserves their internal input order. Each group's first record carries its smallest original index. Sort the groups by that index and finally remove the tags. The second sort has at most records, so the total remains time and storage. Merely returning the value-sorted groups could reorder the classes, so the index step matters when preserving the exact earlier convention. The stronger interface evades the equality-only lower bound by permitting order comparisons. Articles by others on the same topic
There are currently no matching articles.