= Solution
Share the recursive pair and inspect the <predicate> once:
``
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 xs
``
For a finite <list>, <structural induction> establishes that `yes` 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 $n$ <predicate> applications and $\Theta(n)$ additional work. Sharing the recursive result avoids making separate recursive traversals. This is a <stable list partition>.
Back to article page
