toTree needs Ord a; fromTree does not. Construction compares each key against a pivot. Flattening merely traverses and concatenates the buckets, so its more general type is Tree a -> [a]. A manually constructed tree need not satisfy the search-tree invariant; fromTree still flattens it, although its output need not be sorted.
Store the equal bucket at each internal node:
data Tree a = Empty | Node (Tree a) [a] (Tree a)

toTree :: Ord a => [a] -> Tree a
toTree [] = Empty
toTree (pivot:xs) =
  let (lo,eq,hi) = partition3 pivot xs
  in Node (toTree lo) (pivot:eq) (toTree hi)

fromTree :: Tree a -> [a]
fromTree Empty = []
fromTree (Node left equal right) =
  fromTree left ++ equal ++ fromTree right
The representation invariant for a tree produced by toTree is that its bucket is nonempty and contains equal keys, every left-subtree key is smaller, and every right-subtree key is larger. Its multiplicities are preserved. Substituting the two equations for toTree into fromTree gives exactly the two defining equations for sort; induction proves sort = fromTree . toTree on finite inputs.
Both versions call the same partition helper on the same pivot and sublists. The flattening stage makes no key comparisons. Thus fully producing the answer makes the same comparison decisions as the direct algorithm; no additional comparison against stored tree keys is introduced.
The ordering operations used to decide the partitions require an Ord a constraint. A function with parametric polymorphism and type [a] -> [a] cannot inspect arbitrary element values to decide which one is smaller; for example, functions themselves need not admit the comparison operations required by this sorting algorithm. A Haskell Ord class instance supplies the comparison method, with its ordering laws a separate semantic assumption.[ref]
A three-way quicksort can use a common partition helper so that the tree factorisation below makes the same key comparisons. The compare operation is assumed to be a terminating lawful total ordering on the supplied keys.
partition3 :: Ord a => a -> [a] -> ([a],[a],[a])
partition3 pivot = foldr step ([],[],[])
  where
    step x rest =
      let (lo,eq,hi) = rest
      in case compare x pivot of
           LT -> (x:lo,eq,hi)
           EQ -> (lo,x:eq,hi)
           GT -> (lo,eq,x:hi)

sort :: Ord a => [a] -> [a]
sort [] = []
sort (pivot:xs) =
  let (lo,eq,hi) = partition3 pivot xs
  in sort lo ++ (pivot:eq) ++ sort hi
Every non-pivot entry appears in exactly one partition, and the equal bucket contains the original pivot exactly once. The recursive sublists have length at most one less than the current finite input, so recursion terminates. Induction gives sorted recursive results with the original multiplicities; placing the equal bucket between them gives a sorted permutation of the input. There is no recursive call on the equal bucket, which avoids needless descent on repeated keys.
Yes, under the finite total assumption in part (d). The pair result retains enough information to reconstruct the tail; the ~ pattern keeps its two components lazy:
spanFold :: (a -> Bool) -> [a] -> ([a], [a])
spanFold p = foldr step ([], [])
  where
    step x ~(ys,zs)
      | p x       = (x:ys,zs)
      | otherwise = ([],x:(ys ++ zs))
Take , and . The base image is . If is true, the recursive equation gives the first branch. If it is false, part (d), applied to the tail, gives , so the second branch becomes . These are precisely the fusion compatibility equations. Finite structural induction establishes the desired equality; it does not require extending the restricted-domain hypothesis to undefined predicate applications.
The qualification matters. If is false but is undefined, ordinary spanP p [v,u] can return the untouched list suffix immediately, whereas the reconstruction through spanFold p [u] cannot recover that list suffix. The weaker condition needed only for the single reconstruction identity in (d) is therefore insufficient for this particular list fold on all list suffixes. The stronger totality condition stated there supplies exactly the missing premise.
For the finite total inputs just specified, a recursive implementation is
spanP :: (a -> Bool) -> [a] -> ([a], [a])
spanP p [] = ([], [])
spanP p whole@(x:xs)
  | p x       = let (ys,zs) = spanP p xs in (x:ys,zs)
  | otherwise = ([],whole)
At a true test, the head belongs to the list prefix and splitting continues on the tail; at a false test, the complete remaining list is the list suffix. Induction proves that the first projection is the longest accepted list prefix and the second projection is the remaining list suffix.
There is a small partial-value distinction behind the paper's displayed pair identity. The conventional recursive span is strict in an entirely undefined list, whereas the literal expression (takeWhile p undefined, dropWhile p undefined) exposes an outer pair with two undefined components. The equality as a pair therefore needs the stated defined-input convention, or an interpretation that compares the two projections. This does not affect the finite total answers here.[ref]
The necessary definedness condition is local: every predicate application actually reached before the first false result must produce a Boolean value. No condition is needed on predicate applications after that first false result, because the list suffix is then returned without further testing. If a reached test is bottom at a known cons cell, the reconstructed list is bottom at that position, while the original list still exposes a cons there; equality fails.
To prove sufficiency on finite lists, induct on the spine. The empty case gives [] ++ [] = []. At a true test the left list prefix contributes the head, and the induction hypothesis reconstructs the tail. At a false test the list prefix is empty and the list suffix is the whole current list. For an infinite true-tested list prefix, every finite output list prefix is copied correctly; the infinite list prefix hides the possibly divergent list suffix computation. A partial spine ending in bottom is reconstructed up to exactly the same bottom. Thus finiteness is sufficient for an elementary induction proof but is not itself necessary for the identity.
For the uniform list fold calculation in part (f), use the convenient stronger assumption that the input is a finite total list and the predicate terminates on every element of that list. This makes the reconstruction identity available on every list suffix, not only on the list suffixes visited by the original list prefix scan. A total predicate on the element type ensures this uniformly over all finite total inputs.
In general, no direct list fold with result type [a] can implement dropWhile p. Choose total values for which and . The results on [] and [u] are both []. A hypothetical implementation foldr h z would therefore receive identical folded-tail values when extending either input by the same head . Yet the required outputs are [v] and [v,u], respectively. This contradicts the fold factorisation criterion: the combining function cannot distinguish information already discarded by its tail summary.
The claim concerns a direct same-result-type list fold. A list fold returning extra information, followed by a projection, is possible: a pair can retain both the original tail and the dropped list suffix. Also, special predicates can have direct list folds: a constantly false predicate gives the identity; a constantly true predicate can use foldr (\_ r -> r) [], which correctly diverges when it must traverse an infinite spine. Those special cases do not supply an implementation for an arbitrary predicate.
Yes. Define the combining function as follows:
takeP :: (a -> Bool) -> [a] -> [a]
takeP p = foldr step []
  where
    step x rest = if p x then x : rest else []
For the fusion derivation use the identity reconstruction foldr (:) [], take , and choose the displayed step as . The function is strict in the input list, , and its cons equation is exactly . Fusion gives the implementation. On a false test, step does not demand the folded tail, so the implementation can terminate after a finite list prefix even when the remaining list is infinite or undefined. An undefined predicate result at a tested element makes both definitions undefined.
The empty-list case uses . At a cons, assuming the equality for the tail, the calculation is
The middle equality is the supplied compatibility condition, instantiated with the folded tail; the last expression is the right fold on the whole list. Structural induction therefore proves fusion for finite total spines.
The strictness condition accounts for a bottom-valued input spine: the inner list fold returns bottom, and makes the two sides agree. The same induction covers finite partial lists. For pure definable continuous functions, an infinite list is the limit of its finite partial approximations, so equality extends to it. These are the three distinct obligations in the right-fold fusion law; strictness is not needed if the domain is restricted to finite terminating spines.
Treat one visit to a level as a whole gambler's ruin excursion, starting at its chamber and ending at local chamber or . The room choices are fair, so the chance of reaching before is , and the chance of reaching first is . The one-way hatches reset the next excursion to chamber of the adjacent level. Thus the embedded Markov chain at level exits moves upward with probability and downward with probability , even though individual room choices are unbiased.
Let be the food probability from the lower starting chamber, and that from the upper chamber . The lower level either exits unsuccessfully or reaches the upper level, while the upper level either finds food or returns to the lower start. First-step analysis at these level exits gives
Substituting yields , so
This also follows from biased gambler's ruin probability on levels , starting at , with ratio : . Absorption occurs almost surely, since from each active level a fixed positive chance of terminal absorption occurs within two excursions; the original chamber excursions are also almost surely finite.
Figure 1.
The maze reduced to level exits has upward probability one quarter and downward probability three quarters
. Details.
Condition on the fair coin choosing the initial chamber. The law of total probability gives . With , substituting the biased gambler's ruin probability gives
Both numerator and denominator in the first case have the same sign. Its limit as is the fair-walk value, since the ratio of their first derivatives is . The averaging is over initial locations, not over the transition probabilities.

There are unlisted articles, also show them or only show them.