Duh! Please forgive my stupidity.
We were talking about this definition of partition:
> partition _ [] = ([], [])
> partition p (x:xs) = if p x then (x:ys, zs) else (ys, x:zs)
> where (ys, zs) = partition p xs
But all the time, I was thinking about this one:
> partition p xs = partition' xs ([],[])
> where partition' [] a = a
> partition' (x:xs) (ys, zs) =
> partition' xs (if p x then (x:ys, zs) else (ys, x:zs))
I just saw the base case of ([],[]) and the consing at the front of
xs and ys and jumped to the wrong conclusion!
In fact, this is my definition from the Haskell-1.1 prelude:
> partition :: (a -> Bool) -> [a] -> ([a],[a])
> partition p = foldr select ([],[])
> where select x (ts,fs) | p x = (x:ts,fs)
> | otherwise = (ts,x:fs)
and it's the same as the first above, of course. (Was that really ten
years ago?)
Does anybody have a loop-fusion/tupling optimization that can turn
the (filter p xs, filter (not . p) xs) definition into the above?
Cheers,
--Joe
Joseph H. Fasel, Ph.D. email: [EMAIL PROTECTED]
Technology Modeling and Analysis phone: +1 505 667 7158
University of California fax: +1 505 667 2960
Los Alamos National Laboratory postal: TSA-7 MS F609
Los Alamos, NM 87545