[Haskell-cafe] mapAccumL - find max in-sequence subsequence
Ross Paterson
ross at soi.city.ac.uk
Mon Oct 30 04:00:51 EST 2006
It's a pity that groupBy isn't defined a little differently:
-- @'groupBy' rel xs@ returns the shortest list of lists such that
--
-- * the concatenation of the lists is @xs@, and
--
-- * @rel@ is 'True' for each consecutive pair of elements in a sublist.
--
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy rel [] = []
groupBy rel (x:xs) = (x:ys) : groupBy rel zs
where (ys,zs) = groupByAux x xs
groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs)
where (ys,zs) = groupByAux x xs
groupByAux y xs = ([], xs)
That's equivalent to the existing definition if rel is symmetric and
transitive, but also useful in other cases, e.g. groupBy (<=) would
generate a list of "runs", and the solution to the problem here would be
longestInSequence :: (Enum a, Eq a) => [a] -> Int
longestInSequence = maximum . map length . groupBy adjacent
where adjacent x y = succ x == y
More information about the Haskell-Cafe
mailing list