Re: [Haskell-cafe] How to split this string.

On 05/01/2012 10:02, Jon Fairbairn wrote:

Steve Horne 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)