[Haskell-cafe] List find-and-remove

[Graham Klyne]

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