Is it possible to implement groupBy using folds?
Hi, The source code of groupBy shows that groupBy does not go through every element. Is it really possible to implement it using folds? Thanks. -- | The 'groupBy' function is the non-overloaded version of 'group'. groupBy :: (a -> a -> Bool) -> [a] -> [[a]] groupBy _ [] = [] groupBy eq (x:xs) = (x:ys) : groupBy eq zs where (ys,zs) = span (eq x) xs Best regards, Zhi-Qiang Lei zhiqiang.lei@gmail.com
This foldr version uses a partitioned accumulator and a post-processing step - it should be possible to achieve the same with an accumulator of [[a]] and deeper pattern matching: groupBy :: (a -> a -> Bool) -> [a] -> [[a]] groupBy test = post . foldr fn ([],[]) where post ([],yss) = yss post (xs,yss) = xs : yss fn a ([],yss) = ([a], yss) fn a (b:bs, yss) | test a b = (a:b:bs, yss) | otherwise = ([a], (b:bs):yss)
participants (2)
-
Stephen Tetley -
Zhi-Qiang Lei