Graham Klyne gk at ninebynine.org
Thu Jul 8 06:56:54 EDT 2004

```Once again, I find myself making code that I think may exist somewhere in
the libraries:

[[
-- list find and remove
extract0 :: (a->Bool) -> [a] -> Maybe (a,[a])
extract0 p as = ex [] as
where
ex seen (a:more)
| p a       = Just (a,revcat seen more)
| otherwise = ex (a:seen) more
ex _ [] = Nothing

extract :: (a->Bool) -> [a] -> Maybe (a,[a])
extract _ []     = Nothing
extract p (a:as)
| p a       = Just (a,as)
| otherwise = pref a (extract p as)
where
pref a1 (Just (a,as)) = Just (a,a1:as)
pref _  Nothing       = Nothing

-- make list from reversed initial sublist and given trailing sublist
revcat :: [a] -> [a] -> [a]
revcat []     more = more
revcat (a:as) more = revcat as (a:more)

t1 = extract (==2) [1,2,3,4] == Just (2,[1,3,4])
t2 = extract (>2)  [1,2,3,4] == Just (3,[1,2,4])
t3 = extract (>5)  [1,2,3,4] == Nothing

ts = and [t1,t2,t3]
]]

(1) is there a function like 'extract'/'extract0' in the standard libraries?

(2) if not, is there any significant difference in the efficiency of the
above implementations?  I think they both use linear time and space, but
the 'extract0' performs a second traversal of (part of) the list to
construct the result, where 'extract' has to pick apart and test the result
from each recursive call.  To my eye, the 'extract0' version looks better.

#g

------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact

```