For the finite total inputs just specified, a recursive implementation isAt 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.
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)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]Haskell 2010 Language Report. §3.17, pattern matching; Chapter 9, definitions of span and the prefix operations
Articles by others on the same topic
There are currently no matching articles.