Stable list partition (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.