    {-# OPTIONS_HADDOCK prune #-}

    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Data.List.Split.Internals
    -- Copyright   :  (c) Brent Yorgey, Louis Wasserman 2008-2012
    -- License     :  BSD-style (see LICENSE)
    -- Maintainer  :  Brent Yorgey <byorgey@gmail.com>
    -- Stability   :  stable
    -- Portability :  Haskell 2010
    --
    -- Implementation module for "Data.List.Split", a combinator library
    -- for splitting lists.  See the "Data.List.Split" documentation for
    -- more description and examples.
    --
    -----------------------------------------------------------------------------

    module Data.List.Split.Internals where

    import           Data.List (genericSplitAt)

    -- * Types and utilities

    -- | A splitting strategy.
    data Splitter a = Splitter { delimiter        :: Delimiter a
                                   -- ^ What delimiter to split on
                               , delimPolicy      :: DelimPolicy
                                   -- ^ What to do with delimiters (drop
                                   --   from output, keep as separate
                                   --   elements in output, or merge with
                                   --   previous or following chunks)
                               , condensePolicy   :: CondensePolicy
                                   -- ^ What to do with multiple
                                   --   consecutive delimiters
                               , initBlankPolicy  :: EndPolicy
                                   -- ^ Drop an initial blank?
                               , finalBlankPolicy :: EndPolicy
                                   -- ^ Drop a final blank?
                               }

    -- | The default splitting strategy: keep delimiters in the output
    --   as separate chunks, don't condense multiple consecutive
    --   delimiters into one, keep initial and final blank chunks.
    --   Default delimiter is the constantly false predicate.
    --
    --   Note that 'defaultSplitter' should normally not be used; use
    --   'oneOf', 'onSublist', or 'whenElt' instead, which are the same as
    --   the 'defaultSplitter' with just the delimiter overridden.
    --
    --   The 'defaultSplitter' strategy with any delimiter gives a
    --   maximally information-preserving splitting strategy, in the sense
    --   that (a) taking the 'concat' of the output yields the original
    --   list, and (b) given only the output list, we can reconstruct a
    --   'Splitter' which would produce the same output list again given
    --   the original input list.  This default strategy can be overridden
    --   to allow discarding various sorts of information.
    defaultSplitter :: Splitter a
    defaultSplitter = Splitter { delimiter        = Delimiter [const False]
                               , delimPolicy      = Keep
                               , condensePolicy   = KeepBlankFields
                               , initBlankPolicy  = KeepBlank
                               , finalBlankPolicy = KeepBlank
                               }

    -- | A delimiter is a list of predicates on elements, matched by some
    --   contiguous subsequence of a list.
    newtype Delimiter a = Delimiter [a -> Bool]

    -- | Try to match a delimiter at the start of a list, either failing
    --   or decomposing the list into the portion which matched the delimiter
    --   and the remainder.
    matchDelim :: Delimiter a -> [a] -> Maybe ([a],[a])
    matchDelim (Delimiter []) xs = Just ([],xs)
    matchDelim (Delimiter _)  [] = Nothing
    matchDelim (Delimiter (p:ps)) (x:xs)
      | p x       = matchDelim (Delimiter ps) xs >>= \(h,t) -> Just (x:h,t)
      | otherwise = Nothing

    -- | What to do with delimiters?
    data DelimPolicy = Drop      -- ^ Drop delimiters from the output.
                     | Keep      -- ^ Keep delimiters as separate chunks
                                 --   of the output.
                     | KeepLeft  -- ^ Keep delimiters in the output,
                                 --   prepending them to the following
                                 --   chunk.
                     | KeepRight -- ^ Keep delimiters in the output,
                                 --   appending them to the previous chunk.
      deriving (Eq, Show)

    -- | What to do with multiple consecutive delimiters?
    data CondensePolicy = Condense         -- ^ Condense into a single delimiter.
                        | DropBlankFields  -- ^ Keep consecutive
                                           --   delimiters separate, but
                                           --   don't insert blank chunks in
                                           --   between them.
                        | KeepBlankFields  -- ^ Insert blank chunks
                                           --   between consecutive
                                           --   delimiters.
      deriving (Eq, Show)

    -- | What to do with a blank chunk at either end of the list
    --   (/i.e./ when the list begins or ends with a delimiter).
    data EndPolicy = DropBlank | KeepBlank
      deriving (Eq, Show)

    -- | Tag chunks as delimiters or text.
    data Chunk a = Delim [a] | Text [a]
      deriving (Show, Eq)

    -- | Internal representation of a split list that tracks which pieces
    --   are delimiters and which aren't.
    type SplitList a = [Chunk a]

    -- | Untag a 'Chunk'.
    fromElem :: Chunk a -> [a]
    fromElem (Text as) = as
    fromElem (Delim as) = as

    -- | Test whether a 'Chunk' is a delimiter.
    isDelim :: Chunk a -> Bool
    isDelim (Delim _) = True
    isDelim _ = False

    -- | Test whether a 'Chunk' is text.
    isText :: Chunk a -> Bool
    isText (Text _) = True
    isText _ = False

    -- * Implementation

    -- | Given a delimiter to use, split a list into an internal
    --   representation with chunks tagged as delimiters or text.  This
    --   transformation is lossless; in particular,
    --
    -- @
    --   'concatMap' 'fromElem' ('splitInternal' d l) == l.
    -- @
    splitInternal :: Delimiter a -> [a] -> SplitList a
    splitInternal _ [] = []
    splitInternal d xxs
      | null xs   = toSplitList match
      | otherwise = Text xs : toSplitList match
     where
      (xs,match) = breakDelim d xxs

      toSplitList Nothing             = []
      toSplitList (Just ([],r:rs))    = Delim [] : Text [r] : splitInternal d rs
      toSplitList (Just (delim,rest)) = Delim delim : splitInternal d rest

    breakDelim :: Delimiter a -> [a] -> ([a],Maybe ([a],[a]))
    breakDelim (Delimiter []) xs         = ([],Just ([],xs))
    breakDelim _              []         = ([],Nothing)
    breakDelim d              xxs@(x:xs) =
      case matchDelim d xxs of
          Nothing    -> let (ys,match) = breakDelim d xs in (x:ys,match)
          Just match -> ([], Just match)

    -- | Given a split list in the internal tagged representation, produce
    --   a new internal tagged representation corresponding to the final
    --   output, according to the strategy defined by the given
    --   'Splitter'.
    postProcess :: Splitter a -> SplitList a -> SplitList a
    postProcess s = dropFinal (finalBlankPolicy s)
                  . dropInitial (initBlankPolicy s)
                  . doMerge (delimPolicy s)
                  . doDrop (delimPolicy s)
                  . insertBlanks (condensePolicy s)
                  . doCondense (condensePolicy s)

    -- | Drop delimiters if the 'DelimPolicy' is 'Drop'.
    doDrop :: DelimPolicy -> SplitList a -> SplitList a
    doDrop Drop l = [ c | c@(Text _) <- l ]
    doDrop _ l = l

    -- | Condense multiple consecutive delimiters into one if the
    --   'CondensePolicy' is 'Condense'.
    doCondense :: CondensePolicy -> SplitList a -> SplitList a
    doCondense Condense ls = condense' ls
      where condense' [] = []
            condense' (c@(Text _) : l) = c : condense' l
            condense' l = (Delim $ concatMap fromElem ds) : condense' rest
              where (ds,rest) = span isDelim l
    doCondense _ ls = ls

    -- | Insert blank chunks between any remaining consecutive delimiters
    --   (unless the condense policy is 'DropBlankFields'), and at the
    --   beginning or end if the first or last element is a delimiter.
    insertBlanks :: CondensePolicy -> SplitList a -> SplitList a
    insertBlanks _ [] = [Text []]
    insertBlanks cp (d@(Delim _) : l) = Text [] : insertBlanks' cp (d:l)
    insertBlanks cp l = insertBlanks' cp l

    -- | Insert blank chunks between consecutive delimiters.
    insertBlanks' :: CondensePolicy -> SplitList a -> SplitList a
    insertBlanks' _ [] = []
    insertBlanks' cp@DropBlankFields (d1@(Delim _) : d2@(Delim _) : l)
      = d1           : insertBlanks' cp (d2:l)
    insertBlanks' cp (d1@(Delim _) : d2@(Delim _) : l)
      = d1 : Text [] : insertBlanks' cp (d2:l)
    insertBlanks' _ [d@(Delim _)] = [d, Text []]
    insertBlanks' cp (c : l) = c : insertBlanks' cp l

    -- | Merge delimiters into adjacent chunks according to the 'DelimPolicy'.
    doMerge :: DelimPolicy -> SplitList a -> SplitList a
    doMerge KeepLeft = mergeLeft
    doMerge KeepRight = mergeRight
    doMerge _ = id

    -- | Merge delimiters with adjacent chunks to the right (yes, that's
    --   not a typo: the delimiters should end up on the left of the
    --   chunks, so they are merged with chunks to their right).
    mergeLeft :: SplitList a -> SplitList a
    mergeLeft [] = []
    mergeLeft ((Delim d) : (Text c) : l) = Text (d++c) : mergeLeft l
    mergeLeft (c : l) = c : mergeLeft l

    -- | Merge delimiters with adjacent chunks to the left.
    mergeRight :: SplitList a -> SplitList a
    mergeRight [] = []
    -- below fanciness is with the goal of laziness: we want to start returning
    -- stuff before we've necessarily discovered a delimiter, in case we're
    -- processing some infinite list with no delimiter
    mergeRight ((Text c) : l) = Text (c++d) : mergeRight lTail
      where (d, lTail) = case l of
                         Delim d' : l' -> (d', l')
                         _ -> ([], l)
    mergeRight (c : l) = c : mergeRight l

    -- | Drop an initial blank chunk according to the given 'EndPolicy'.
    dropInitial :: EndPolicy -> SplitList a -> SplitList a
    dropInitial DropBlank (Text [] : l) = l
    dropInitial _ l = l

    -- | Drop a final blank chunk according to the given 'EndPolicy'.
    dropFinal :: EndPolicy -> SplitList a -> SplitList a
    dropFinal _         [] = []
    dropFinal DropBlank l  = dropFinal' l
      where dropFinal' []        = []
            dropFinal' [Text []] = []
            dropFinal' (x:xs)    = x:dropFinal' xs
    dropFinal _         l  = l

    -- * Combinators

    -- | Split a list according to the given splitting strategy.  This is
    --   how to \"run\" a 'Splitter' that has been built using the other
    --   combinators.
    split :: Splitter a -> [a] -> [[a]]
    split s = map fromElem . postProcess s . splitInternal (delimiter s)

    -- ** Basic strategies
    --
    -- $ All these basic strategies have the same parameters as the
    -- 'defaultSplitter' except for the delimiters.

    -- | A splitting strategy that splits on any one of the given
    --   elements.  For example:
    --
    -- > split (oneOf "xyz") "aazbxyzcxd" == ["aa","z","b","x","","y","","z","c","x","d"]
    oneOf :: Eq a => [a] -> Splitter a
    oneOf elts = defaultSplitter { delimiter = Delimiter [(`elem` elts)] }

    -- | A splitting strategy that splits on the given list, when it is
    --   encountered as an exact subsequence.  For example:
    --
    -- > split (onSublist "xyz") "aazbxyzcxd" == ["aazb","xyz","cxd"]
    --
    --   Note that splitting on the empty list is a special case, which
    --   splits just before every element of the list being split.  For example:
    --
    -- > split (onSublist "") "abc" == ["","","a","","b","","c"]
    -- > split (dropDelims . dropBlanks $ onSublist "") "abc" == ["a","b","c"]
    --
    --   However, if you want to break a list into singleton elements like
    --   this, you are better off using @'chunksOf' 1@, or better yet,
    --   @'map' (:[])@.
    onSublist :: Eq a => [a] -> Splitter a
    onSublist lst = defaultSplitter { delimiter = Delimiter (map (==) lst) }

    -- | A splitting strategy that splits on any elements that satisfy the
    --   given predicate.  For example:
    --
    -- > split (whenElt (<0)) [2,4,-3,6,-9,1] == [[2,4],[-3],[6],[-9],[1]]
    whenElt :: (a -> Bool) -> Splitter a
    whenElt p = defaultSplitter { delimiter = Delimiter [p] }

    -- ** Strategy transformers

    -- | Drop delimiters from the output (the default is to keep
    --   them). For example,
    --
    -- > split (oneOf ":") "a:b:c" == ["a", ":", "b", ":", "c"]
    -- > split (dropDelims $ oneOf ":") "a:b:c" == ["a", "b", "c"]
    dropDelims :: Splitter a -> Splitter a
    dropDelims s = s { delimPolicy = Drop }

    -- | Keep delimiters in the output by prepending them to adjacent
    --   chunks.  For example:
    --
    -- > split (keepDelimsL $ oneOf "xyz") "aazbxyzcxd" == ["aa","zb","x","y","zc","xd"]
    keepDelimsL :: Splitter a -> Splitter a
    keepDelimsL s = s { delimPolicy = KeepLeft }

    -- | Keep delimiters in the output by appending them to adjacent
    --   chunks. For example:
    --
    -- > split (keepDelimsR $ oneOf "xyz") "aazbxyzcxd" == ["aaz","bx","y","z","cx","d"]
    keepDelimsR :: Splitter a -> Splitter a
    keepDelimsR s = s { delimPolicy = KeepRight }

    -- | Condense multiple consecutive delimiters into one.  For example:
    --
    -- > split (condense $ oneOf "xyz") "aazbxyzcxd" == ["aa","z","b","xyz","c","x","d"]
    -- > split (dropDelims $ oneOf "xyz") "aazbxyzcxd" == ["aa","b","","","c","d"]
    -- > split (condense . dropDelims $ oneOf "xyz") "aazbxyzcxd" == ["aa","b","c","d"]
    condense :: Splitter a -> Splitter a
    condense s = s { condensePolicy = Condense }

    -- | Don't generate a blank chunk if there is a delimiter at the
    --   beginning.  For example:
    --
    -- > split (oneOf ":") ":a:b" == ["",":","a",":","b"]
    -- > split (dropInitBlank $ oneOf ":") ":a:b" == [":","a",":","b"]
    dropInitBlank :: Splitter a -> Splitter a
    dropInitBlank s = s { initBlankPolicy = DropBlank }

    -- | Don't generate a blank chunk if there is a delimiter at the end.
    --   For example:
    --
    -- > split (oneOf ":") "a:b:" == ["a",":","b",":",""]
    -- > split (dropFinalBlank $ oneOf ":") "a:b:" == ["a",":","b",":"]
    dropFinalBlank :: Splitter a -> Splitter a
    dropFinalBlank s = s { finalBlankPolicy = DropBlank }

    -- | Don't generate blank chunks between consecutive delimiters.
    --   For example:
    --
    -- > split (oneOf ":") "::b:::a" == ["",":","",":","b",":","",":","",":","a"]
    -- > split (dropInnerBlanks $ oneOf ":") "::b:::a" == ["", ":",":","b",":",":",":","a"]
    dropInnerBlanks :: Splitter a -> Splitter a
    dropInnerBlanks s = s { condensePolicy = DropBlankFields }

    -- ** Derived combinators

    -- | Drop all blank chunks from the output, and condense consecutive
    --   delimiters into one.  Equivalent to @'dropInitBlank'
    --   . 'dropFinalBlank' . 'condense'@.  For example:
    --
    -- > split (oneOf ":") "::b:::a" == ["",":","",":","b",":","",":","",":","a"]
    -- > split (dropBlanks $ oneOf ":") "::b:::a" == ["::","b",":::","a"]
    dropBlanks :: Splitter a -> Splitter a
    dropBlanks = dropInitBlank . dropFinalBlank . condense

    -- | Make a strategy that splits a list into chunks that all start
    --   with the given subsequence (except possibly the first).
    --   Equivalent to @'dropInitBlank' . 'keepDelimsL' . 'onSublist'@.
    --   For example:
    --
    -- > split (startsWith "app") "applyapplicativeapplaudapproachapple" == ["apply","applicative","applaud","approach","apple"]
    startsWith :: Eq a => [a] -> Splitter a
    startsWith = dropInitBlank . keepDelimsL . onSublist

    -- | Make a strategy that splits a list into chunks that all start
    --   with one of the given elements (except possibly the first).
    --   Equivalent to @'dropInitBlank' . 'keepDelimsL' . 'oneOf'@.  For
    --   example:
    --
    -- > split (startsWithOneOf ['A'..'Z']) "ACamelCaseIdentifier" == ["A","Camel","Case","Identifier"]
    startsWithOneOf :: Eq a => [a] -> Splitter a
    startsWithOneOf = dropInitBlank . keepDelimsL . oneOf

    -- | Make a strategy that splits a list into chunks that all end with
    --   the given subsequence, except possibly the last.  Equivalent to
    --   @'dropFinalBlank' . 'keepDelimsR' . 'onSublist'@.  For example:
    --
    -- > split (endsWith "ly") "happilyslowlygnarlylily" == ["happily","slowly","gnarly","lily"]
    endsWith :: Eq a => [a] -> Splitter a
    endsWith = dropFinalBlank . keepDelimsR . onSublist

    -- | Make a strategy that splits a list into chunks that all end with
    --   one of the given elements, except possibly the last.  Equivalent
    --   to @'dropFinalBlank' . 'keepDelimsR' . 'oneOf'@.  For example:
    --
    -- > split (condense $ endsWithOneOf ".,?! ") "Hi, there!  How are you?" == ["Hi, ","there!  ","How ","are ","you?"]
    endsWithOneOf :: Eq a => [a] -> Splitter a
    endsWithOneOf = dropFinalBlank . keepDelimsR . oneOf

    -- ** Convenience functions
    --
    -- These functions implement some common splitting strategies.  Note
    -- that all of the functions in this section drop delimiters from
    -- the final output, since that is a more common use case even
    -- though it is not the default.

    -- | Split on any of the given elements.  Equivalent to @'split'
    --   . 'dropDelims' . 'oneOf'@.  For example:
    --
    -- > splitOneOf ";.," "foo,bar;baz.glurk" == ["foo","bar","baz","glurk"]
    splitOneOf :: Eq a => [a] -> [a] -> [[a]]
    splitOneOf = split . dropDelims . oneOf

    -- | Split on the given sublist.  Equivalent to @'split'
    --   . 'dropDelims' . 'onSublist'@.  For example:
    --
    -- > splitOn ".." "a..b...c....d.." == ["a","b",".c","","d",""]
    --
    --   In some parsing combinator frameworks this is also known as
    --   @sepBy@.
    --
    --   Note that this is the right inverse of the 'Data.List.intercalate' function
    --   from "Data.List", that is,
    --
    --   > intercalate x . splitOn x === id
    --
    --   @'splitOn' x . 'Data.List.intercalate' x@ is the identity on
    --   certain lists, but it is tricky to state the precise conditions
    --   under which this holds.  (For example, it is not enough to say
    --   that @x@ does not occur in any elements of the input list.
    --   Working out why is left as an exercise for the reader.)
    splitOn :: Eq a => [a] -> [a] -> [[a]]
    splitOn   = split . dropDelims . onSublist

    -- | Split on elements satisfying the given predicate.  Equivalent to
    --   @'split' . 'dropDelims' . 'whenElt'@.  For example:
    --
    -- > splitWhen (<0) [1,3,-4,5,7,-9,0,2] == [[1,3],[5,7],[0,2]]
    splitWhen :: (a -> Bool) -> [a] -> [[a]]
    splitWhen = split . dropDelims . whenElt

    {-# DEPRECATED sepBy "Use splitOn." #-}
    sepBy :: Eq a => [a] -> [a] -> [[a]]
    sepBy = splitOn

    {-# DEPRECATED sepByOneOf "Use splitOneOf." #-}
    sepByOneOf :: Eq a => [a] -> [a] -> [[a]]
    sepByOneOf = splitOneOf

    -- | Split into chunks terminated by the given subsequence.
    --   Equivalent to @'split' . 'dropFinalBlank' . 'dropDelims'
    --   . 'onSublist'@.  For example:
    --
    -- > endBy ";" "foo;bar;baz;" == ["foo","bar","baz"]
    --
    --   Note also that the 'lines' function from "Data.List" is equivalent
    --   to @'endBy' \"\\n\"@.
    endBy :: Eq a => [a] -> [a] -> [[a]]
    endBy = split . dropFinalBlank . dropDelims . onSublist

    -- | Split into chunks terminated by one of the given elements.
    --   Equivalent to @'split' . 'dropFinalBlank' . 'dropDelims'
    --   . 'oneOf'@. For example:
    --
    -- > endByOneOf ";," "foo;bar,baz;" == ["foo","bar","baz"]
    endByOneOf :: Eq a => [a] -> [a] -> [[a]]
    endByOneOf = split . dropFinalBlank . dropDelims . oneOf

    {-# DEPRECATED unintercalate "Use splitOn." #-}
    unintercalate :: Eq a => [a] -> [a] -> [[a]]
    unintercalate = splitOn

    -- | Split into \"words\", with word boundaries indicated by the given
    --   predicate.  Satisfies @'Data.List.words' === wordsBy
    --   'Data.Char.isSpace'@; equivalent to @'split' . 'dropBlanks'
    --   . 'dropDelims' . 'whenElt'@.  For example:
    --
    -- > wordsBy (=='x') "dogxxxcatxbirdxx" == ["dog","cat","bird"]
    wordsBy :: (a -> Bool) -> [a] -> [[a]]
    wordsBy = split . dropBlanks . dropDelims . whenElt

    -- | Split into \"lines\", with line boundaries indicated by the given
    --   predicate. Satisfies @'lines' === linesBy (=='\n')@; equivalent to
    --   @'split' . 'dropFinalBlank' . 'dropDelims' . 'whenElt'@.  For example:
    --
    -- > linesBy (=='x') "dogxxxcatxbirdxx" == ["dog","","","cat","bird",""]
    linesBy :: (a -> Bool) -> [a] -> [[a]]
    linesBy = split . dropFinalBlank . dropDelims . whenElt

    -- * Other splitting methods

    -- | Standard build function, specialized to building lists.
    --
    --   Usually build is given the rank-2 type
    --
    --   > build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
    --
    --   but since we only use it when @(b ~ [a])@, we give it the more
    --   restricted type signature in order to avoid needing a
    --   non-Haskell2010 extension.
    --
    --   Note that the 0.1.4.3 release of this package did away with a
    --   custom @build@ implementation in favor of importing one from
    --   "GHC.Exts", which was (reportedly) faster for some applications.
    --   However, in the interest of simplicity and complete Haskell2010
    --   compliance as @split@ is being included in the Haskel Platform,
    --   version 0.2.1.0 has gone back to defining @build@ manually.  This
    --   is in line with @split@'s design philosophy of having efficiency
    --   as a non-goal.
    build :: ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
    build g = g (:) []

    -- | @'chunksOf' n@ splits a list into length-n pieces.  The last
    --   piece will be shorter if @n@ does not evenly divide the length of
    --   the list.  If @n <= 0@, @'chunksOf' n l@ returns an infinite list
    --   of empty lists.  For example:
    --
    --   Note that @'chunksOf' n []@ is @[]@, not @[[]]@.  This is
    --   intentional, and is consistent with a recursive definition of
    --   'chunksOf'; it satisfies the property that
    --
    --   @chunksOf n xs ++ chunksOf n ys == chunksOf n (xs ++ ys)@
    --
    --   whenever @n@ evenly divides the length of @xs@.
    chunksOf :: Int -> [e] -> [[e]]
    chunksOf i ls = map (take i) (build (splitter ls)) where
      splitter :: [e] -> ([e] -> a -> a) -> a -> a
      splitter [] _ n = n
      splitter l c n  = l `c` splitter (drop i l) c n

    {-# DEPRECATED chunk "Use chunksOf." #-}
    chunk :: Int -> [e] -> [[e]]
    chunk = chunksOf

    {-# DEPRECATED splitEvery "Use chunksOf." #-}
    splitEvery :: Int -> [e] -> [[e]]
    splitEvery = chunksOf

    -- | Split a list into chunks of the given lengths. For example:
    --
    -- > splitPlaces [2,3,4] [1..20] == [[1,2],[3,4,5],[6,7,8,9]]
    -- > splitPlaces [4,9] [1..10] == [[1,2,3,4],[5,6,7,8,9,10]]
    -- > splitPlaces [4,9,3] [1..10] == [[1,2,3,4],[5,6,7,8,9,10]]
    --
    --   If the input list is longer than the total of the given lengths,
    --   then the remaining elements are dropped. If the list is shorter
    --   than the total of the given lengths, then the result may contain
    --   fewer chunks than requested, and the last chunk may be shorter
    --   than requested.
    splitPlaces :: Integral a => [a] -> [e] -> [[e]]
    splitPlaces is ys = build (splitPlacer is ys) where
      splitPlacer :: Integral i => [i] -> [b] -> ([b] -> t -> t) -> t -> t
      splitPlacer [] _ _ n      = n
      splitPlacer _ [] _ n      = n
      splitPlacer (l:ls) xs c n = let (x1, x2) = genericSplitAt l xs
                                  in  x1 `c` splitPlacer ls x2 c n

    -- | Split a list into chunks of the given lengths. Unlike
    --   'splitPlaces', the output list will always be the same length as
    --   the first input argument. If the input list is longer than the
    --   total of the given lengths, then the remaining elements are
    --   dropped. If the list is shorter than the total of the given
    --   lengths, then the last several chunks will be shorter than
    --   requested or empty. For example:
    --
    -- > splitPlacesBlanks [2,3,4] [1..20] == [[1,2],[3,4,5],[6,7,8,9]]
    -- > splitPlacesBlanks [4,9] [1..10] == [[1,2,3,4],[5,6,7,8,9,10]]
    -- > splitPlacesBlanks [4,9,3] [1..10] == [[1,2,3,4],[5,6,7,8,9,10],[]]
    --
    --   Notice the empty list in the output of the third example, which
    --   differs from the behavior of 'splitPlaces'.
    splitPlacesBlanks :: Integral a => [a] -> [e] -> [[e]]
    splitPlacesBlanks is ys = build (splitPlacer is ys) where
      splitPlacer :: Integral i => [i] -> [b] -> ([b] -> t -> t) -> t -> t
      splitPlacer [] _ _ n      = n
      splitPlacer (l:ls) xs c n = let (x1, x2) = genericSplitAt l xs
                                  in  x1 `c` splitPlacer ls x2 c n

    -- | A useful recursion pattern for processing a list to produce a new
    --   list, often used for \"chopping\" up the input list.  Typically
    --   chop is called with some function that will consume an initial
    --   prefix of the list and produce a value and the rest of the list.
    --
    --   For example, many common Prelude functions can be implemented in
    --   terms of @chop@:
    --
    -- > group :: (Eq a) => [a] -> [[a]]
    -- > group = chop (\ xs@(x:_) -> span (==x) xs)
    -- >
    -- > words :: String -> [String]
    -- > words = filter (not . null) . chop (span (not . isSpace) . dropWhile isSpace)

    chop :: ([a] -> (b, [a])) -> [a] -> [b]
    chop _ [] = []
    chop f as = b : chop f as'
      where (b, as') = f as