[Haskell-cafe] How to split this string.

[Steve Horne]

On 05/01/2012 10:02, Jon Fairbairn wrote:
> Steve Horne<sh006d3592 at blueyonder.co.uk>  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)