= Stable list partition
{title2=`partition :: (a -> Bool) -> [a] -> ([a],[a])`}
Split a <list> into the subsequence satisfying a <predicate> and the subsequence failing it, preserving relative order in both. One recursive traversal computes the pair for the tail once, evaluates the head's <predicate> once and prepends the head to the appropriate component. A shared irrefutable pair binding preserves lazy access to either component. Fully consuming both finite outputs takes <linear time> in addition to <predicate> evaluation costs.
Back to article page
