Haskell boundedSpan function
I was recently playing with an interesting toy problem: Given a string, return a list of strings, where each element is a grouping of consecutive equal characters in the string of maximum length 9.
As an example, given
"aaaaaaaaaaaabb" I wanted to obtain
To help me do this, I wanted a function that was almost the same as the 'group' function in Data.List, but with the added size bound of 9, on the groups.
Initially, I used span followed by a "wrapping" function, to correctly wrap my results to <= 9 in length:
runs :: (Eq a) => [a] -> [[a]] runs  =  runs xs = let (eqs, rest) = chomp xs in (wrap eqs) ++ (runs rest) chomp :: (Eq a) => [a] -> ([a], [a]) chomp xs@ = (xs,xs) chomp xs@(x:_) = span (== x) xs wrap :: [a] -> [[a]] wrap xs | length xs <= 9 = [xs] | otherwise = before : (wrap after) where (before, after) = splitAt 9 xs
This seemed somewhat inefficient, as I was having to use append to flatten the list of "wrapped" strings. I thought that if could fuse the wrap and span functions, I'd have a more efficient implementation.
Using the Prelude definition of span for guidance, I was able to create the following function:
-- | The 'boundedSpan' function takes an integer @n@, predicate -- @f@ and list @xs@, and returns a tuple containing the longest -- prefix (possibly empty) of size <= @n@ of @xs@, of elements -- that satisfy @p@, and the remaining elements of @xs@. boundedSpan :: Int -> (a -> Bool) -> [a] -> ([a], [a]) boundedSpan _ _ xs@ = (xs, xs) boundedSpan 0 _ xs = (, xs) boundedSpan n p xs@(x:xs') | p x = let (ys, zs) = boundedSpan (n-1) p xs' in (x:ys, zs) | otherwise = (, xs)
Using this function allowed me to simply cons together a list of strings, rather than using append:
chomp9 :: (Eq a) => [a] -> ([a], [a]) chomp9 xs@ = (xs, xs) chomp9 xs@(x:xs') = boundedSpan 9 (== x) xs runs2 :: (Eq a) => [a] -> [[a]] runs2  =  runs2 xs = let (chomped, rest) = chomp9 xs in chomped : runs2 rest