[Haskell-cafe] How to split this string.
Steve Horne
sh006d3592 at blueyonder.co.uk
Thu Jan 5 11:57:41 CET 2012
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)
More information about the Haskell-Cafe
mailing list