[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