Solution
= Solution
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.<Haskell 2010 Language Report>[§3.17, pattern matching; Chapter 9, definitions of span and the prefix operations]{ref}