--
-- Copyright (C) 2011 by Jonas Kramer. All rights reserved.
-- Published under the terms of the GNU General Public License (GPL).
--

-- | Find sequences within lists.

module Data.List.Sequences where

    -- | Find sequences within a list and return them as new list of sequences.
    -- The first argument is a function that takes two subsequent elements of the
    -- given list (second argument) and returns whether the second element
    -- follows the first one in a sequence.
    --
    -- > splitSeq ((==) . succ) [1,2,3,5,6,7]
    -- > [[1,2,3],[5,6,7]]
    --
    splitSeq :: (a -> a -> Bool) -> [a] -> [[a]]
    splitSeq _ [] = []
    splitSeq f xs = group : splitSeq f rest where (group, rest) = spanSeq f xs


    -- | Works pretty much like `splitSeq`, except that a tuple with only the
    -- sequence starting at the first element and the rest of the list is
    -- returned.
    --
    -- > spanSeq ((==) . succ) "abcxyz123"
    -- > ("abc","xyz123")
    --
    spanSeq :: (a -> a -> Bool) -> [a] -> ([a], [a])
    spanSeq _ [] = ([], [])
    spanSeq _ (x:[]) = ([x], [])
    spanSeq f (x:xs) =
        split' x xs
        where
            split' x [] = ([x], [])
            split' x (y:ys)
                | f x y = (x : s, rest)
                | otherwise = ([x], y : ys)
                where
                    (s, rest) = split' y ys