On 05/01/2012 10:02, Jon Fairbairn wrote:
Steve Horne<[email protected]> writes:
Personally, I think this is a tad disappointing. Given that
groupBy cannot check or enforce that it's test respects
equivalence classes, it should ideally give results that
make as much sense as possible either way. That said, even
if the test was always given adjacent elements, there's
still room for a different order of processing the list
(left-to-right or right-to-left) to give different results -
and in any case, maybe it's more efficient the way it is.
Looking back at the libraries list, I get the impression that
there was a suggestion to change the behaviour of groupBy, but
it doesn’t seem to have happened.
I've realised that the left-to-right vs. right-to-left order thing makes
no difference - I don't know why I thought that now.
I've written an implementation, only the predicate is inverse-logic -
True means cut-between-these rather than keep-these-together.
I keep thinking there should be a tail-recursive implementation, but the
usual trick would either mean using ++ or difference lists or similar,
or would deliver the results in reverse order. If anyone can think of a
way to get the correct result in one pass through the list (assuming
tail recursion is optimised), I'm curious.
Or... does non-strict evaluation mean I shouldn't worry about it? Maybe
it does a good job of evaluating the head quickly anyway, as the data
dependencies are quite localized? I've been wondering how lazy
evaluation interacts with recursion over lists in performance terms for
a while.
-- groupCut - Similar to groupBy, but where groupBy assumes an
equivalence relation,
-- groupCut takes a function that indicates where to cut. The two
parameters to this
-- function are always adjacent items from the list, and if the
function returns True,
-- a cut is done between the two items.
groupCut :: (x -> x -> Bool) -> [x] -> [[x]]
groupCut f [] = []
groupCut f xs = let (y,ys,yss) = groupCut' f xs in (y:ys):yss
-- arg1 - cut here test function
-- arg2 - input list
-- result - triple of current (head char, head group excl. head
char, tail groups)
--
-- the input list must not be empty - this is handled in the
front-end function.
groupCut' :: (x -> x -> Bool) -> [x] -> (x, [x], [[x]])
groupCut' f (x:[]) = (x, [], [])
groupCut' f (x:xs) = let (y,ys,yss) = groupCut' f xs
in if (f x y) then (x, [], (y:ys):yss)
else (x, y:ys, yss)
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
