For each segment retain its total weight , largest possibly-empty prefix weight , largest possibly-empty suffix weight , and largest possibly-empty internal contiguous weight . The maximum-subarray segment summary combines adjacent segments asAn empty segment has all four values zero. For a singleton of weight , use . The recursive procedure splits into halves, computes their summaries and applies these four formulas; the root's is the desired maximum weight.
To return an actual subsequence, attach half-open endpoints to each of . A prefix endpoint starts at its segment's left boundary, and a suffix endpoint ends at its right boundary, including empty prefixes and suffixes. Store the interval belonging to whichever candidate wins a maximum. The crossing candidate joins a left suffix to a right prefix, which meet at the split point; the other candidates keep their child endpoints. Choose an empty interval on ties at weight zero. Return the root's winning interval as a slice of the original input. This augmentation still has constant-size state and constant-time combinations.
For correctness, a prefix either stays inside the left half or consists of the entire left half and a right prefix. The suffix argument is symmetric. An optimal contiguous segment either lies in one half or crosses the split, in which case it consists of a left suffix and a right prefix. Each upper bound in the formulas is attained by its recorded candidate, proving exactness. Empty candidates ensure that an all-negative input returns the empty subsequence.
There are tree nodes, each using a constant number of additions and comparisons. The divide-and-conquer algorithm therefore takes time and stack space, plus the cost of copying the returned slice if a copy is required. In the stated example it selects zero-based interval of weight 8. Carrying all four summary values avoids rescanning the halves at each split.
Maintain the two largest entries of each segment, counting repeated values as separate entries. A singleton returns its value and a sentinel for its missing runner-up. Split a longer segment into two nonempty halves, recursively obtain and , and combine them byFor example, an implementation on an indexed sequence can use:The result is
top2(lo, hi):
if hi-lo == 1: return (a[lo], -infinity)
mid = (lo+hi)//2
(mL,sL) = top2(lo,mid)
(mR,sR) = top2(mid,hi)
if mL >= mR: return (mL, max(sL,mR))
else: return (mR, max(mL,sR))top2(0,n). The global maximum is one of the two child maxima. Once its side is identified, the global second maximum is either that side's runner-up or the other side's maximum; the displayed formula exhausts these possibilities. This proves the divide-and-conquer algorithm by induction on segment length. There are leaves and constant-cost combinations, so its time complexity is , with recursive stack space for balanced splits. A Maybe value can replace the formal sentinel for a generic ordered element type. If both largest entries are equal, both are returned; a second distinct value is a different specification.For the first recurrence relation, the master theorem compares with . Since , the recursive leaves dominate and the answer is . More explicitly, the work at depth is , a growing geometric series that stops at depth , where its sum has that order.
For the second recurrence relation, each step subtracts two and adds one until reaching a base case. For integral there are steps, so and the answer is .
The third set of printed requirements is inconsistent. The specified base values and its recurrence relation give identically, as strong induction immediately verifies: . In particular , while the extra condition demands . Thus no function satisfies all the printed conditions. Dropping that extra inequality gives .
The likely intended growth calculation can nevertheless be made precise, without treating it as a solution of the contradictory data. On dyadic arguments put . Its equation has the general formbecause has characteristic equation . The printed values force . With suitably different initial values, the condition for arbitrarily large instead requires , hence and , or . That last order describes corrected initial data, not the paper as printed. All three bullets belong to this single marked part.
Sort the two halves ascending, reverse the second, and concatenate to form a bitonic sequence:For a power-of-two length greater than one, both halves are smaller powers of two. By induction, the recursive calls return ascending permutations of their respective inputs. Reversal makes the second half descending, so part (e)'s precondition holds and
sort :: Ord a => [a] -> [a]
sort [] = []
sort [x] = [x]
sort xs = merge (sort as ++ reverse (sort bs))
where (as,bs) = halve xsmerge sorts their concatenation without losing entries. This proves both sortedness and sorting permutation preservation. Its recurrence relation is , so summing the levels gives time. Equal keys cause no difficulty; ascending and descending here permit equality. This is a bitonic sorting algorithm.Apply the supplied bitonic-merging fact directly:For length ,
merge :: Ord a => [a] -> [a]
merge xs = rounds (levels (length xs)) xs
where
levels n
| n <= 1 = 0
| otherwise = 1 + levels (n `div` 2)
order (x,y)
| x <= y = (x,y)
| otherwise = (y,x)
pass = unpairs . map order . pairs . riffle
rounds 0 ys = ys
rounds r ys = rounds (r-1) (pass ys)levels n = k. Each pass performs exactly the required shuffle and adjacent compare-exchange operations. The supplied fact therefore proves that rounds k yields ascending order from a bitonic sequence. Each pass preserves the multiset of entries and costs , giving time for . Length one needs no pass. The definition also harmlessly returns [] on empty input.For the defined shuffle, Here the identity's period means the least positive number of applications, so the empty and two-element lists have period one. Since is odd, is invertible modulo , ensuring termination. Using
count 52 = 8. The printed assertion about seven shuffles is inconsistent with the actual permutation. Number positions from zero. On an even length , a position moves to , while the last position stays fixed. Indeed, positions in the first half move to , and positions in the second half move to . Consequently the number sought is the multiplicative order of modulo :count :: Int -> Int
count n
| n < 0 || odd n = error "count: nonnegative even length required"
| n <= 2 = 1
| otherwise = go 1 (2 `mod` m)
where
m = toInteger n - 1
go k r
| r == 1 = k
| otherwise = go (k+1) ((2*r) `mod` m)Integer for residues avoids overflow in doubling; the mathematical correctness assumes the returned period fits Int. The algorithm uses one modular update per shuffle in the period, rather than constructing each shuffled deck.For , , whereas , and are not congruent to one, ruling out every proper divisor of eight. After seven shuffles, the original position is at position , not back at .
An eight-step position cycle under the 52-card perfect out-shuffle
. Details. This single position already disproves a seven-step return; the modular calculation proves that the whole permutation returns after eight.
Interleave equal halves, or collect the first and second components of adjacent pairs:For halves
riffle :: [a] -> [a]
riffle = unpairs . uncurry zip . halve
unriffle :: [a] -> [a]
unriffle = unhalve . unzip . pairsas and bs of equal length, pairs (riffle xs) = zip as bs, and unzip (zip as bs) = (as,bs). Therefore unriffle (riffle xs) = xs. Conversely, starting from the adjacent pairs of any even list, separating the components, halving their concatenation and zipping them restores those same pairs. Hence riffle (unriffle xs) = xs too. Every stage takes linear time. This perfect out-shuffle leaves the first and last positions fixed.Join either two halves or successive pairs:By the defining property of
unhalve :: ([a],[a]) -> [a]
unhalve (xs,ys) = xs ++ ys
unpairs :: [(a,a)] -> [a]
unpairs = foldr (\(x,y) zs -> x:y:zs) []splitAt, concatenating the two halves restores the original list. For unpairs, structural induction on the even input proves that its first pair restores its first two elements and the recursive result restores the rest. Thus both requested function compositions are the identity. Fully consuming either result takes at most linear time; list concatenation only copies the left half once.For finite even lists, these definitions take at most linear time:The length calculation and the prefix split each take time. The second operation consumes two constructors per step and emits one pair. Under the stated even-length precondition, neither definition encounters an unmatched final element.
halve :: [a] -> ([a],[a])
halve xs = splitAt (length xs `div` 2) xs
pairs :: [a] -> [(a,a)]
pairs [] = []
pairs (x:y:xs) = (x,y) : pairs xs
pairs [_] = error "pairs: odd length"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.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.
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.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.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]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.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.Skip whole trees using their cached sizes, then descend through one tree:After skipping a size- tree, the desired index decreases by . Inside a node, position zero is the root, positions belong to the left child and the following positions to the right child. This proves correctness by structural induction on the search.
index :: List a -> Int -> a
index (List ts) i
| i < 0 = error "index: negative index"
| otherwise = seek ts i
where
seek [] _ = error "index: out of bounds"
seek ((w,t):us) j
| j < w = at w t j
| otherwise = seek us (j-w)
at _ (Leaf x) 0 = x
at w (Node x l r) j
| j == 0 = x
| j <= h = at h l (j-1)
| otherwise = at h r (j-1-h)
where h = w `div` 2
at _ _ _ = error "index: invalid representation"There are at most forest entries by the supplied bound, and each tree has logarithmic height. Consequently a valid query takes time, with logarithmic worst cases. On a conventional linked list,
xs !! i follows links and costs , hence in the worst case. The first element remains a constant time query in either representation.Repeated root removal gives the conventional list:The representation interpretation satisfies
toList :: List a -> [a]
toList rs
| null rs = []
| otherwise = head rs : toList (tail rs)toList (cons x rs) = x : toList rs; alternatively, structural induction on the number of stored elements proves that each step emits exactly the next preorder traversal value. The output has cons cells, and each step takes constant time, so fully consuming it costs time. No repeated list concatenation is needed.The first tree's root is the first element. Deleting that root either discards a singleton or exposes two equal-sized child trees:For a node of size , both children have size . Their order agrees with the old preorder traversal, and they become the sole permitted initial duplicate. The rest of the forest was no smaller than the old root tree. Thus both operations preserve the representation invariant and take worst-case time on a nonempty skew-binary random-access list.
head :: List a -> a
head (List ((_,Leaf x):_)) = x
head (List ((_,Node x _ _):_)) = x
head (List []) = error "head: empty list"
tail :: List a -> List a
tail (List ((_,Leaf _):ts)) = List ts
tail (List ((w,Node _ l r):ts)) =
let h = w `div` 2 in List ((h,l):(h,r):ts)
tail (List []) = error "tail: empty list"Repeated constant time insertion constructs the representation:The right fold preserves order because
fromList :: [a] -> List a
fromList = foldr cons nilcons prepends its argument. On a finite length- list, there are calls of cons; completely constructing the result takes time and constructors. This claim concerns finite inputs, not productivity of conversion from an infinite lazy list. There are unlisted articles, also show them or only show them.
