2010/1/2
I'm inclined to agree with you. Could you please post the sources to both nubBy and groupBy to see what has changed?
Thanks, Kim-Ee yeoh@cs.wisc.edu
Sure thing, Here is the report's implementation of nubBy: ------------------- nubBy :: (a -> a -> Bool) -> [a] -> [a] nubBy eq [] = [] nubBy eq (x:xs) = x : nubBy eq (filter (\y -> not (eq x y)) xs) ------------------- And here is the implementation in GHC 6.10.4 and GHC 6.12.1: ------------------- nubBy eq l = nubBy' l [] where nubBy' [] _ = [] nubBy' (y:ys) xs | elem_by eq y xs = nubBy' ys xs | otherwise = y : nubBy' ys (y:xs) -- Not exported: -- Note that we keep the call to `eq` with arguments in the -- same order as in the reference implementation -- 'xs' is the list of things we've seen so far, -- 'y' is the potential new element elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool elem_by _ _ [] = False elem_by eq y (x:xs) = y `eq` x || elem_by eq y xs ------------------- Note that the comment is actually incorrect. The report implementation of nubBy applies the function such that earlier accepted elements of the list are the left parameter to eq. Simply switching the y `eq` x to become x `eq` y in elem_by produces something which passes QuickCheck tests at the very least. I believe it's really the right thing at that point. The implementation of groupBy in 6.10.4 and 6.12.1 is the same as the report version, and I'm happy with it: ------------------- groupBy :: (a -> a -> Bool) -> [a] -> [[a]] groupBy _ [] = [] groupBy eq (x:xs) = (x:ys) : groupBy eq zs where (ys,zs) = span (eq x) xs ------------------- My main concern with it is that the report says: ------------------- When the "By" function replaces an Eq context by a binary predicate, the predicate is assumed to define an equivalence ------------------- which I think is much too strong an assumption given that these functions have reasonably natural and quite useful extensions to non-equivalence relations, which the code provided by the Report actually implements. - Cale