{-# 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
  { forall a. Splitter a -> Delimiter a
delimiter :: Delimiter a
  -- ^ What delimiter to split on
  , forall a. Splitter a -> DelimPolicy
delimPolicy :: DelimPolicy
  -- ^ What to do with delimiters (drop
  --   from output, keep as separate
  --   elements in output, or merge with
  --   previous or following chunks)
  , forall a. Splitter a -> CondensePolicy
condensePolicy :: CondensePolicy
  -- ^ What to do with multiple
  --   consecutive delimiters
  , forall a. Splitter a -> EndPolicy
initBlankPolicy :: EndPolicy
  -- ^ Drop an initial blank?
  , forall a. Splitter a -> EndPolicy
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 :: forall a. Splitter a
defaultSplitter =
  Splitter
    { delimiter :: Delimiter a
delimiter = [a -> Bool] -> Delimiter a
forall a. [a -> Bool] -> Delimiter a
Delimiter [Bool -> a -> Bool
forall a b. a -> b -> a
const Bool
False]
    , delimPolicy :: DelimPolicy
delimPolicy = DelimPolicy
Keep
    , condensePolicy :: CondensePolicy
condensePolicy = CondensePolicy
KeepBlankFields
    , initBlankPolicy :: EndPolicy
initBlankPolicy = EndPolicy
KeepBlank
    , finalBlankPolicy :: EndPolicy
finalBlankPolicy = EndPolicy
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 :: forall a. Delimiter a -> [a] -> Maybe ([a], [a])
matchDelim (Delimiter []) [a]
xs = ([a], [a]) -> Maybe ([a], [a])
forall a. a -> Maybe a
Just ([], [a]
xs)
matchDelim (Delimiter [a -> Bool]
_) [] = Maybe ([a], [a])
forall a. Maybe a
Nothing
matchDelim (Delimiter (a -> Bool
p : [a -> Bool]
ps)) (a
x : [a]
xs)
  | a -> Bool
p a
x = Delimiter a -> [a] -> Maybe ([a], [a])
forall a. Delimiter a -> [a] -> Maybe ([a], [a])
matchDelim ([a -> Bool] -> Delimiter a
forall a. [a -> Bool] -> Delimiter a
Delimiter [a -> Bool]
ps) [a]
xs Maybe ([a], [a])
-> (([a], [a]) -> Maybe ([a], [a])) -> Maybe ([a], [a])
forall a b. Maybe a -> (a -> Maybe b) -> Maybe b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \([a]
h, [a]
t) -> ([a], [a]) -> Maybe ([a], [a])
forall a. a -> Maybe a
Just (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
h, [a]
t)
  | Bool
otherwise = Maybe ([a], [a])
forall a. Maybe a
Nothing

-- | What to do with delimiters?
data DelimPolicy
  = -- | Drop delimiters from the output.
    Drop
  | -- | Keep delimiters as separate chunks
    --   of the output.
    Keep
  | -- | Keep delimiters in the output,
    --   prepending them to the following
    --   chunk.
    KeepLeft
  | -- | Keep delimiters in the output,
    --   appending them to the previous chunk.
    KeepRight
  deriving (DelimPolicy -> DelimPolicy -> Bool
(DelimPolicy -> DelimPolicy -> Bool)
-> (DelimPolicy -> DelimPolicy -> Bool) -> Eq DelimPolicy
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: DelimPolicy -> DelimPolicy -> Bool
== :: DelimPolicy -> DelimPolicy -> Bool
$c/= :: DelimPolicy -> DelimPolicy -> Bool
/= :: DelimPolicy -> DelimPolicy -> Bool
Eq, Int -> DelimPolicy -> ShowS
[DelimPolicy] -> ShowS
DelimPolicy -> String
(Int -> DelimPolicy -> ShowS)
-> (DelimPolicy -> String)
-> ([DelimPolicy] -> ShowS)
-> Show DelimPolicy
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> DelimPolicy -> ShowS
showsPrec :: Int -> DelimPolicy -> ShowS
$cshow :: DelimPolicy -> String
show :: DelimPolicy -> String
$cshowList :: [DelimPolicy] -> ShowS
showList :: [DelimPolicy] -> ShowS
Show)

-- | What to do with multiple consecutive delimiters?
data CondensePolicy
  = -- | Condense into a single delimiter.
    Condense
  | -- | Keep consecutive
    --   delimiters separate, but
    --   don't insert blank chunks in
    --   between them.
    DropBlankFields
  | -- | Insert blank chunks
    --   between consecutive
    --   delimiters.
    KeepBlankFields
  deriving (CondensePolicy -> CondensePolicy -> Bool
(CondensePolicy -> CondensePolicy -> Bool)
-> (CondensePolicy -> CondensePolicy -> Bool) -> Eq CondensePolicy
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: CondensePolicy -> CondensePolicy -> Bool
== :: CondensePolicy -> CondensePolicy -> Bool
$c/= :: CondensePolicy -> CondensePolicy -> Bool
/= :: CondensePolicy -> CondensePolicy -> Bool
Eq, Int -> CondensePolicy -> ShowS
[CondensePolicy] -> ShowS
CondensePolicy -> String
(Int -> CondensePolicy -> ShowS)
-> (CondensePolicy -> String)
-> ([CondensePolicy] -> ShowS)
-> Show CondensePolicy
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> CondensePolicy -> ShowS
showsPrec :: Int -> CondensePolicy -> ShowS
$cshow :: CondensePolicy -> String
show :: CondensePolicy -> String
$cshowList :: [CondensePolicy] -> ShowS
showList :: [CondensePolicy] -> ShowS
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 (EndPolicy -> EndPolicy -> Bool
(EndPolicy -> EndPolicy -> Bool)
-> (EndPolicy -> EndPolicy -> Bool) -> Eq EndPolicy
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: EndPolicy -> EndPolicy -> Bool
== :: EndPolicy -> EndPolicy -> Bool
$c/= :: EndPolicy -> EndPolicy -> Bool
/= :: EndPolicy -> EndPolicy -> Bool
Eq, Int -> EndPolicy -> ShowS
[EndPolicy] -> ShowS
EndPolicy -> String
(Int -> EndPolicy -> ShowS)
-> (EndPolicy -> String)
-> ([EndPolicy] -> ShowS)
-> Show EndPolicy
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> EndPolicy -> ShowS
showsPrec :: Int -> EndPolicy -> ShowS
$cshow :: EndPolicy -> String
show :: EndPolicy -> String
$cshowList :: [EndPolicy] -> ShowS
showList :: [EndPolicy] -> ShowS
Show)

-- | Tag chunks as delimiters or text.
data Chunk a = Delim [a] | Text [a]
  deriving (Int -> Chunk a -> ShowS
[Chunk a] -> ShowS
Chunk a -> String
(Int -> Chunk a -> ShowS)
-> (Chunk a -> String) -> ([Chunk a] -> ShowS) -> Show (Chunk a)
forall a. Show a => Int -> Chunk a -> ShowS
forall a. Show a => [Chunk a] -> ShowS
forall a. Show a => Chunk a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> Chunk a -> ShowS
showsPrec :: Int -> Chunk a -> ShowS
$cshow :: forall a. Show a => Chunk a -> String
show :: Chunk a -> String
$cshowList :: forall a. Show a => [Chunk a] -> ShowS
showList :: [Chunk a] -> ShowS
Show, Chunk a -> Chunk a -> Bool
(Chunk a -> Chunk a -> Bool)
-> (Chunk a -> Chunk a -> Bool) -> Eq (Chunk a)
forall a. Eq a => Chunk a -> Chunk a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Chunk a -> Chunk a -> Bool
== :: Chunk a -> Chunk a -> Bool
$c/= :: forall a. Eq a => Chunk a -> Chunk a -> Bool
/= :: Chunk a -> Chunk a -> Bool
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 :: forall a. Chunk a -> [a]
fromElem (Text [a]
as) = [a]
as
fromElem (Delim [a]
as) = [a]
as

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

-- | Test whether a 'Chunk' is text.
isText :: Chunk a -> Bool
isText :: forall a. Chunk a -> Bool
isText (Text [a]
_) = Bool
True
isText Chunk a
_ = Bool
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 :: forall a. Delimiter a -> [a] -> SplitList a
splitInternal Delimiter a
_ [] = []
splitInternal Delimiter a
d [a]
xxs
  | [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
xs = Maybe ([a], [a]) -> [Chunk a]
toSplitList Maybe ([a], [a])
match
  | Bool
otherwise = [a] -> Chunk a
forall a. [a] -> Chunk a
Text [a]
xs Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: Maybe ([a], [a]) -> [Chunk a]
toSplitList Maybe ([a], [a])
match
 where
  ([a]
xs, Maybe ([a], [a])
match) = Delimiter a -> [a] -> ([a], Maybe ([a], [a]))
forall a. Delimiter a -> [a] -> ([a], Maybe ([a], [a]))
breakDelim Delimiter a
d [a]
xxs

  toSplitList :: Maybe ([a], [a]) -> [Chunk a]
toSplitList Maybe ([a], [a])
Nothing = []
  toSplitList (Just ([], a
r : [a]
rs)) = [a] -> Chunk a
forall a. [a] -> Chunk a
Delim [] Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: [a] -> Chunk a
forall a. [a] -> Chunk a
Text [a
r] Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: Delimiter a -> [a] -> [Chunk a]
forall a. Delimiter a -> [a] -> SplitList a
splitInternal Delimiter a
d [a]
rs
  toSplitList (Just ([a]
delim, [a]
rest)) = [a] -> Chunk a
forall a. [a] -> Chunk a
Delim [a]
delim Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: Delimiter a -> [a] -> [Chunk a]
forall a. Delimiter a -> [a] -> SplitList a
splitInternal Delimiter a
d [a]
rest

breakDelim :: Delimiter a -> [a] -> ([a], Maybe ([a], [a]))
breakDelim :: forall a. Delimiter a -> [a] -> ([a], Maybe ([a], [a]))
breakDelim (Delimiter []) [a]
xs = ([], ([a], [a]) -> Maybe ([a], [a])
forall a. a -> Maybe a
Just ([], [a]
xs))
breakDelim Delimiter a
_ [] = ([], Maybe ([a], [a])
forall a. Maybe a
Nothing)
breakDelim Delimiter a
d xxs :: [a]
xxs@(a
x : [a]
xs) =
  case Delimiter a -> [a] -> Maybe ([a], [a])
forall a. Delimiter a -> [a] -> Maybe ([a], [a])
matchDelim Delimiter a
d [a]
xxs of
    Maybe ([a], [a])
Nothing -> let ([a]
ys, Maybe ([a], [a])
match) = Delimiter a -> [a] -> ([a], Maybe ([a], [a]))
forall a. Delimiter a -> [a] -> ([a], Maybe ([a], [a]))
breakDelim Delimiter a
d [a]
xs in (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
ys, Maybe ([a], [a])
match)
    Just ([a], [a])
match -> ([], ([a], [a]) -> Maybe ([a], [a])
forall a. a -> Maybe a
Just ([a], [a])
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 :: forall a. Splitter a -> SplitList a -> SplitList a
postProcess Splitter a
s =
  EndPolicy -> SplitList a -> SplitList a
forall a. EndPolicy -> SplitList a -> SplitList a
dropFinal (Splitter a -> EndPolicy
forall a. Splitter a -> EndPolicy
finalBlankPolicy Splitter a
s)
    (SplitList a -> SplitList a)
-> (SplitList a -> SplitList a) -> SplitList a -> SplitList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. EndPolicy -> SplitList a -> SplitList a
forall a. EndPolicy -> SplitList a -> SplitList a
dropInitial (Splitter a -> EndPolicy
forall a. Splitter a -> EndPolicy
initBlankPolicy Splitter a
s)
    (SplitList a -> SplitList a)
-> (SplitList a -> SplitList a) -> SplitList a -> SplitList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DelimPolicy -> SplitList a -> SplitList a
forall a. DelimPolicy -> SplitList a -> SplitList a
doMerge (Splitter a -> DelimPolicy
forall a. Splitter a -> DelimPolicy
delimPolicy Splitter a
s)
    (SplitList a -> SplitList a)
-> (SplitList a -> SplitList a) -> SplitList a -> SplitList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DelimPolicy -> SplitList a -> SplitList a
forall a. DelimPolicy -> SplitList a -> SplitList a
doDrop (Splitter a -> DelimPolicy
forall a. Splitter a -> DelimPolicy
delimPolicy Splitter a
s)
    (SplitList a -> SplitList a)
-> (SplitList a -> SplitList a) -> SplitList a -> SplitList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CondensePolicy -> SplitList a -> SplitList a
forall a. CondensePolicy -> SplitList a -> SplitList a
insertBlanks (Splitter a -> CondensePolicy
forall a. Splitter a -> CondensePolicy
condensePolicy Splitter a
s)
    (SplitList a -> SplitList a)
-> (SplitList a -> SplitList a) -> SplitList a -> SplitList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CondensePolicy -> SplitList a -> SplitList a
forall a. CondensePolicy -> SplitList a -> SplitList a
doCondense (Splitter a -> CondensePolicy
forall a. Splitter a -> CondensePolicy
condensePolicy Splitter a
s)

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

-- | Condense multiple consecutive delimiters into one if the
--   'CondensePolicy' is 'Condense'.
doCondense :: CondensePolicy -> SplitList a -> SplitList a
doCondense :: forall a. CondensePolicy -> SplitList a -> SplitList a
doCondense CondensePolicy
Condense SplitList a
ls = SplitList a -> SplitList a
forall {a}. [Chunk a] -> [Chunk a]
condense' SplitList a
ls
 where
  condense' :: [Chunk a] -> [Chunk a]
condense' [] = []
  condense' (c :: Chunk a
c@(Text [a]
_) : [Chunk a]
l) = Chunk a
c Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: [Chunk a] -> [Chunk a]
condense' [Chunk a]
l
  condense' [Chunk a]
l = [a] -> Chunk a
forall a. [a] -> Chunk a
Delim ((Chunk a -> [a]) -> [Chunk a] -> [a]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Chunk a -> [a]
forall a. Chunk a -> [a]
fromElem [Chunk a]
ds) Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: [Chunk a] -> [Chunk a]
condense' [Chunk a]
rest
   where
    ([Chunk a]
ds, [Chunk a]
rest) = (Chunk a -> Bool) -> [Chunk a] -> ([Chunk a], [Chunk a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
span Chunk a -> Bool
forall a. Chunk a -> Bool
isDelim [Chunk a]
l
doCondense CondensePolicy
_ SplitList a
ls = SplitList a
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 :: forall a. CondensePolicy -> SplitList a -> SplitList a
insertBlanks CondensePolicy
_ [] = [[a] -> Chunk a
forall a. [a] -> Chunk a
Text []]
insertBlanks CondensePolicy
cp (d :: Chunk a
d@(Delim [a]
_) : [Chunk a]
l) = [a] -> Chunk a
forall a. [a] -> Chunk a
Text [] Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: CondensePolicy -> [Chunk a] -> [Chunk a]
forall a. CondensePolicy -> SplitList a -> SplitList a
insertBlanks' CondensePolicy
cp (Chunk a
d Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: [Chunk a]
l)
insertBlanks CondensePolicy
cp [Chunk a]
l = CondensePolicy -> [Chunk a] -> [Chunk a]
forall a. CondensePolicy -> SplitList a -> SplitList a
insertBlanks' CondensePolicy
cp [Chunk a]
l

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

-- | Merge delimiters into adjacent chunks according to the 'DelimPolicy'.
doMerge :: DelimPolicy -> SplitList a -> SplitList a
doMerge :: forall a. DelimPolicy -> SplitList a -> SplitList a
doMerge DelimPolicy
KeepLeft = SplitList a -> SplitList a
forall {a}. [Chunk a] -> [Chunk a]
mergeLeft
doMerge DelimPolicy
KeepRight = SplitList a -> SplitList a
forall {a}. [Chunk a] -> [Chunk a]
mergeRight
doMerge DelimPolicy
_ = SplitList a -> SplitList a
forall a. a -> a
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 :: forall {a}. [Chunk a] -> [Chunk a]
mergeLeft [] = []
mergeLeft ((Delim [a]
d) : (Text [a]
c) : [Chunk a]
l) = [a] -> Chunk a
forall a. [a] -> Chunk a
Text ([a]
d [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
c) Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: [Chunk a] -> [Chunk a]
forall {a}. [Chunk a] -> [Chunk a]
mergeLeft [Chunk a]
l
mergeLeft (Chunk a
c : [Chunk a]
l) = Chunk a
c Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: [Chunk a] -> [Chunk a]
forall {a}. [Chunk a] -> [Chunk a]
mergeLeft [Chunk a]
l

-- | Merge delimiters with adjacent chunks to the left.
mergeRight :: SplitList a -> SplitList a
mergeRight :: forall {a}. [Chunk a] -> [Chunk 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 [a]
c) : [Chunk a]
l) = [a] -> Chunk a
forall a. [a] -> Chunk a
Text ([a]
c [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
d) Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: [Chunk a] -> [Chunk a]
forall {a}. [Chunk a] -> [Chunk a]
mergeRight [Chunk a]
lTail
 where
  ([a]
d, [Chunk a]
lTail) = case [Chunk a]
l of
    Delim [a]
d' : [Chunk a]
l' -> ([a]
d', [Chunk a]
l')
    [Chunk a]
_ -> ([], [Chunk a]
l)
mergeRight (Chunk a
c : [Chunk a]
l) = Chunk a
c Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: [Chunk a] -> [Chunk a]
forall {a}. [Chunk a] -> [Chunk a]
mergeRight [Chunk a]
l

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

-- | Drop a final blank chunk according to the given 'EndPolicy'.
dropFinal :: EndPolicy -> SplitList a -> SplitList a
dropFinal :: forall a. EndPolicy -> SplitList a -> SplitList a
dropFinal EndPolicy
_ [] = []
dropFinal EndPolicy
DropBlank [Chunk a]
l = [Chunk a] -> [Chunk a]
forall {a}. [Chunk a] -> [Chunk a]
dropFinal' [Chunk a]
l
 where
  dropFinal' :: [Chunk a] -> [Chunk a]
dropFinal' [] = []
  dropFinal' [Text []] = []
  dropFinal' (Chunk a
x : [Chunk a]
xs) = Chunk a
x Chunk a -> [Chunk a] -> [Chunk a]
forall a. a -> [a] -> [a]
: [Chunk a] -> [Chunk a]
dropFinal' [Chunk a]
xs
dropFinal EndPolicy
_ [Chunk a]
l = [Chunk a]
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 :: forall a. Splitter a -> [a] -> [[a]]
split Splitter a
s = (Chunk a -> [a]) -> [Chunk a] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map Chunk a -> [a]
forall a. Chunk a -> [a]
fromElem ([Chunk a] -> [[a]]) -> ([a] -> [Chunk a]) -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> [Chunk a] -> [Chunk a]
forall a. Splitter a -> SplitList a -> SplitList a
postProcess Splitter a
s ([Chunk a] -> [Chunk a]) -> ([a] -> [Chunk a]) -> [a] -> [Chunk a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Delimiter a -> [a] -> [Chunk a]
forall a. Delimiter a -> [a] -> SplitList a
splitInternal (Splitter a -> Delimiter a
forall a. Splitter a -> Delimiter a
delimiter Splitter a
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.
--
-- >>> split (oneOf ",;") "hi;there,world"
-- ["hi",";","there",",","world"]
--
-- >>> split (oneOf "xyz") "aazbxyzcxd"
-- ["aa","z","b","x","","y","","z","c","x","d"]
oneOf :: (Eq a) => [a] -> Splitter a
oneOf :: forall a. Eq a => [a] -> Splitter a
oneOf [a]
elts = Splitter Any
forall a. Splitter a
defaultSplitter {delimiter = Delimiter [(`elem` elts)]}

-- | A splitting strategy that splits on the given list, when it is
--   encountered as an exact subsequence.
--
-- >>> 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.
--
-- >>> 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 :: forall a. Eq a => [a] -> Splitter a
onSublist [a]
lst = Splitter Any
forall a. Splitter a
defaultSplitter {delimiter = Delimiter (map (==) lst)}

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

-- ** Strategy transformers

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

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

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

-- | Condense multiple consecutive delimiters into one.
--
-- >>> 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 :: forall a. Splitter a -> Splitter a
condense Splitter a
s = Splitter a
s {condensePolicy = Condense}

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

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

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

-- | Split over a different type of element by performing a preprocessing step.
--
-- >>> split (mapSplitter snd $ oneOf "-_") $ zip [0..] "a-bc_d"
-- [[(0,'a')],[(1,'-')],[(2,'b'),(3,'c')],[(4,'_')],[(5,'d')]]
--
-- >>> import Data.Char (toLower)
-- >>> split (mapSplitter toLower $ dropDelims $ whenElt (== 'x')) "abXcxd"
-- ["ab","c","d"]
mapSplitter :: (b -> a) -> Splitter a -> Splitter b
mapSplitter :: forall b a. (b -> a) -> Splitter a -> Splitter b
mapSplitter b -> a
f (Splitter Delimiter a
d DelimPolicy
dp CondensePolicy
cp EndPolicy
ibp EndPolicy
fbp) = Delimiter b
-> DelimPolicy
-> CondensePolicy
-> EndPolicy
-> EndPolicy
-> Splitter b
forall a.
Delimiter a
-> DelimPolicy
-> CondensePolicy
-> EndPolicy
-> EndPolicy
-> Splitter a
Splitter ((b -> a) -> Delimiter a -> Delimiter b
forall b a. (b -> a) -> Delimiter a -> Delimiter b
mapDelimiter b -> a
f Delimiter a
d) DelimPolicy
dp CondensePolicy
cp EndPolicy
ibp EndPolicy
fbp
 where
  mapDelimiter :: (b -> a) -> Delimiter a -> Delimiter b
  mapDelimiter :: forall b a. (b -> a) -> Delimiter a -> Delimiter b
mapDelimiter b -> a
g (Delimiter [a -> Bool]
xs) = [b -> Bool] -> Delimiter b
forall a. [a -> Bool] -> Delimiter a
Delimiter ([b -> Bool] -> Delimiter b) -> [b -> Bool] -> Delimiter b
forall a b. (a -> b) -> a -> b
$ ((a -> Bool) -> b -> Bool) -> [a -> Bool] -> [b -> Bool]
forall a b. (a -> b) -> [a] -> [b]
map ((a -> Bool) -> (b -> a) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> a
g) [a -> Bool]
xs

-- ** Derived combinators

-- | Drop all blank chunks from the output, and condense consecutive
--   delimiters into one.  Equivalent to @'dropInitBlank'
--   . 'dropFinalBlank' . 'condense'@.
--
-- >>> split (oneOf ":") "::b:::a"
-- ["",":","",":","b",":","",":","",":","a"]
--
-- >>> split (dropBlanks $ oneOf ":") "::b:::a"
-- ["::","b",":::","a"]
dropBlanks :: Splitter a -> Splitter a
dropBlanks :: forall a. Splitter a -> Splitter a
dropBlanks = Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropInitBlank (Splitter a -> Splitter a)
-> (Splitter a -> Splitter a) -> Splitter a -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropFinalBlank (Splitter a -> Splitter a)
-> (Splitter a -> Splitter a) -> Splitter a -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
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'@.
--
-- >>> split (startsWith "app") "applyapplicativeapplaudapproachapple"
-- ["apply","applicative","applaud","approach","apple"]
startsWith :: (Eq a) => [a] -> Splitter a
startsWith :: forall a. Eq a => [a] -> Splitter a
startsWith = Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropInitBlank (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
keepDelimsL (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Splitter a
forall a. Eq a => [a] -> Splitter a
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'@.
--   example:
--
-- >>> split (startsWithOneOf ['A'..'Z']) "ACamelCaseIdentifier"
-- ["A","Camel","Case","Identifier"]
startsWithOneOf :: (Eq a) => [a] -> Splitter a
startsWithOneOf :: forall a. Eq a => [a] -> Splitter a
startsWithOneOf = Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropInitBlank (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
keepDelimsL (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Splitter a
forall a. Eq a => [a] -> Splitter a
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'@.
--
-- >>> split (endsWith "ly") "happilyslowlygnarlylily"
-- ["happily","slowly","gnarly","lily"]
endsWith :: (Eq a) => [a] -> Splitter a
endsWith :: forall a. Eq a => [a] -> Splitter a
endsWith = Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropFinalBlank (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
keepDelimsR (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Splitter a
forall a. Eq a => [a] -> Splitter a
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'@.
--
-- >>> split (condense $ endsWithOneOf ".,?! ") "Hi, there!  How are you?"
-- ["Hi, ","there!  ","How ","are ","you?"]
endsWithOneOf :: (Eq a) => [a] -> Splitter a
endsWithOneOf :: forall a. Eq a => [a] -> Splitter a
endsWithOneOf = Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropFinalBlank (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
keepDelimsR (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Splitter a
forall a. Eq a => [a] -> Splitter a
oneOf

-- ** Convenience functions

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

-- | Split on the given sublist.  Equivalent to @'split'
--   . 'dropDelims' . 'onSublist'@.
--
-- >>> splitOn ":" "12:35:07"
-- ["12","35","07"]
--
-- >>> splitOn "x" "axbxc"
-- ["a","b","c"]
--
-- >>> splitOn "x" "axbxcx"
-- ["a","b","c",""]
--
-- >>> 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 :: forall a. Eq a => [a] -> [a] -> [[a]]
splitOn = Splitter a -> [a] -> [[a]]
forall a. Splitter a -> [a] -> [[a]]
split (Splitter a -> [a] -> [[a]])
-> ([a] -> Splitter a) -> [a] -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropDelims (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Splitter a
forall a. Eq a => [a] -> Splitter a
onSublist

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

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

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

-- | Split into chunks terminated by the given subsequence.
--   Equivalent to @'split' . 'dropFinalBlank' . 'dropDelims'
--   . 'onSublist'@.
--
-- >>> 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 :: forall a. Eq a => [a] -> [a] -> [[a]]
endBy = Splitter a -> [a] -> [[a]]
forall a. Splitter a -> [a] -> [[a]]
split (Splitter a -> [a] -> [[a]])
-> ([a] -> Splitter a) -> [a] -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropFinalBlank (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropDelims (Splitter a -> Splitter a)
-> ([a] -> Splitter a) -> [a] -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Splitter a
forall a. Eq a => [a] -> Splitter a
onSublist

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

{-# DEPRECATED unintercalate "Use splitOn." #-}
unintercalate :: (Eq a) => [a] -> [a] -> [[a]]
unintercalate :: forall a. Eq a => [a] -> [a] -> [[a]]
unintercalate = [a] -> [a] -> [[a]]
forall a. Eq a => [a] -> [a] -> [[a]]
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'@.
--
-- >>> wordsBy (`elem` ",;.?! ") "Hello there, world! How?"
-- ["Hello","there","world","How"]
--
-- >>> wordsBy (=='x') "dogxxxcatxbirdxx"
-- ["dog","cat","bird"]
wordsBy :: (a -> Bool) -> [a] -> [[a]]
wordsBy :: forall a. (a -> Bool) -> [a] -> [[a]]
wordsBy = Splitter a -> [a] -> [[a]]
forall a. Splitter a -> [a] -> [[a]]
split (Splitter a -> [a] -> [[a]])
-> ((a -> Bool) -> Splitter a) -> (a -> Bool) -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropBlanks (Splitter a -> Splitter a)
-> ((a -> Bool) -> Splitter a) -> (a -> Bool) -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropDelims (Splitter a -> Splitter a)
-> ((a -> Bool) -> Splitter a) -> (a -> Bool) -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> Splitter a
forall a. (a -> Bool) -> Splitter a
whenElt

-- | Split into \"lines\", with line boundaries indicated by the given
--   predicate. Satisfies @'lines' === linesBy (=='\n')@; equivalent to
--   @'split' . 'dropFinalBlank' . 'dropDelims' . 'whenElt'@.
--
-- >>> linesBy (==';') "foo;bar;;baz;"
-- ["foo","bar","","baz"]
--
-- >>> linesBy (=='x') "dogxxxcatxbirdxx"
-- ["dog","","","cat","bird",""]
linesBy :: (a -> Bool) -> [a] -> [[a]]
linesBy :: forall a. (a -> Bool) -> [a] -> [[a]]
linesBy = Splitter a -> [a] -> [[a]]
forall a. Splitter a -> [a] -> [[a]]
split (Splitter a -> [a] -> [[a]])
-> ((a -> Bool) -> Splitter a) -> (a -> Bool) -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropFinalBlank (Splitter a -> Splitter a)
-> ((a -> Bool) -> Splitter a) -> (a -> Bool) -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Splitter a -> Splitter a
forall a. Splitter a -> Splitter a
dropDelims (Splitter a -> Splitter a)
-> ((a -> Bool) -> Splitter a) -> (a -> Bool) -> Splitter a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> Splitter a
forall a. (a -> Bool) -> Splitter a
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 :: forall a. ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
build (a -> [a] -> [a]) -> [a] -> [a]
g = (a -> [a] -> [a]) -> [a] -> [a]
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.
--
-- >>> chunksOf 3 [1..12]
-- [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]
--
-- >>> chunksOf 3 "Hello there"
-- ["Hel","lo ","the","re"]
--
-- >>> chunksOf 3 ([] :: [Int])
-- []
--
--   Note that @'chunksOf' n []@ is @[]@, not @[[]]@.  This is
--   intentional, and 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 :: forall e. Int -> [e] -> [[e]]
chunksOf Int
i [e]
ls = ([e] -> [e]) -> [[e]] -> [[e]]
forall a b. (a -> b) -> [a] -> [b]
map (Int -> [e] -> [e]
forall a. Int -> [a] -> [a]
take Int
i) ((([e] -> [[e]] -> [[e]]) -> [[e]] -> [[e]]) -> [[e]]
forall a. ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
build ([e] -> ([e] -> [[e]] -> [[e]]) -> [[e]] -> [[e]]
forall e a. [e] -> ([e] -> a -> a) -> a -> a
splitter [e]
ls))
 where
  splitter :: [e] -> ([e] -> a -> a) -> a -> a
  splitter :: forall e a. [e] -> ([e] -> a -> a) -> a -> a
splitter [] [e] -> a -> a
_ a
n = a
n
  splitter [e]
l [e] -> a -> a
c a
n = [e]
l [e] -> a -> a
`c` [e] -> ([e] -> a -> a) -> a -> a
forall e a. [e] -> ([e] -> a -> a) -> a -> a
splitter (Int -> [e] -> [e]
forall a. Int -> [a] -> [a]
drop Int
i [e]
l) [e] -> a -> a
c a
n

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

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

-- | Split a list into chunks of the given lengths.
--
-- >>> 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 :: forall a e. Integral a => [a] -> [e] -> [[e]]
splitPlaces [a]
is [e]
ys = (([e] -> [[e]] -> [[e]]) -> [[e]] -> [[e]]) -> [[e]]
forall a. ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
build ([a] -> [e] -> ([e] -> [[e]] -> [[e]]) -> [[e]] -> [[e]]
forall i b t. Integral i => [i] -> [b] -> ([b] -> t -> t) -> t -> t
splitPlacer [a]
is [e]
ys)
 where
  splitPlacer :: (Integral i) => [i] -> [b] -> ([b] -> t -> t) -> t -> t
  splitPlacer :: forall i b t. Integral i => [i] -> [b] -> ([b] -> t -> t) -> t -> t
splitPlacer [] [b]
_ [b] -> t -> t
_ t
n = t
n
  splitPlacer [i]
_ [] [b] -> t -> t
_ t
n = t
n
  splitPlacer (i
l : [i]
ls) [b]
xs [b] -> t -> t
c t
n =
    let ([b]
x1, [b]
x2) = i -> [b] -> ([b], [b])
forall i a. Integral i => i -> [a] -> ([a], [a])
genericSplitAt i
l [b]
xs
     in [b]
x1 [b] -> t -> t
`c` [i] -> [b] -> ([b] -> t -> t) -> t -> t
forall i b t. Integral i => [i] -> [b] -> ([b] -> t -> t) -> t -> t
splitPlacer [i]
ls [b]
x2 [b] -> t -> t
c t
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.
--
-- >>> 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 :: forall a e. Integral a => [a] -> [e] -> [[e]]
splitPlacesBlanks [a]
is [e]
ys = (([e] -> [[e]] -> [[e]]) -> [[e]] -> [[e]]) -> [[e]]
forall a. ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]
build ([a] -> [e] -> ([e] -> [[e]] -> [[e]]) -> [[e]] -> [[e]]
forall i b t. Integral i => [i] -> [b] -> ([b] -> t -> t) -> t -> t
splitPlacer [a]
is [e]
ys)
 where
  splitPlacer :: (Integral i) => [i] -> [b] -> ([b] -> t -> t) -> t -> t
  splitPlacer :: forall i b t. Integral i => [i] -> [b] -> ([b] -> t -> t) -> t -> t
splitPlacer [] [b]
_ [b] -> t -> t
_ t
n = t
n
  splitPlacer (i
l : [i]
ls) [b]
xs [b] -> t -> t
c t
n =
    let ([b]
x1, [b]
x2) = i -> [b] -> ([b], [b])
forall i a. Integral i => i -> [a] -> ([a], [a])
genericSplitAt i
l [b]
xs
     in [b]
x1 [b] -> t -> t
`c` [i] -> [b] -> ([b] -> t -> t) -> t -> t
forall i b t. Integral i => [i] -> [b] -> ([b] -> t -> t) -> t -> t
splitPlacer [i]
ls [b]
x2 [b] -> t -> t
c t
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 (break isSpace . dropWhile isSpace)
chop :: ([a] -> (b, [a])) -> [a] -> [b]
chop :: forall a b. ([a] -> (b, [a])) -> [a] -> [b]
chop [a] -> (b, [a])
_ [] = []
chop [a] -> (b, [a])
f [a]
as = b
b b -> [b] -> [b]
forall a. a -> [a] -> [a]
: ([a] -> (b, [a])) -> [a] -> [b]
forall a b. ([a] -> (b, [a])) -> [a] -> [b]
chop [a] -> (b, [a])
f [a]
as'
 where
  (b
b, [a]
as') = [a] -> (b, [a])
f [a]
as

-- | Divides up an input list into a set of sublists, according to 'n' and 'm'
--   input specifications you provide. Each sublist will have 'n' items, and the
--   start of each sublist will be offset by 'm' items from the previous one.
--
-- >>> divvy 5 5 [1..15]
-- [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15]]
--
-- >>> divvy 5 2 [1..15]
-- [[1,2,3,4,5],[3,4,5,6,7],[5,6,7,8,9],[7,8,9,10,11],[9,10,11,12,13],[11,12,13,14,15]]
--
--   In the case where a source list's trailing elements do no fill an entire
--   sublist, those trailing elements will be dropped.
--
-- >>> divvy 5 2 [1..10]
-- [[1,2,3,4,5],[3,4,5,6,7],[5,6,7,8,9]]
--
--   As an example, you can generate a moving average over a list of prices:
--
-- > type Prices = [Float]
-- > type AveragePrices = [Float]
-- >
-- > average :: [Float] -> Float
-- > average xs = sum xs / (fromIntegral $ length xs)
-- >
-- > simpleMovingAverage :: Prices -> AveragePrices
-- > simpleMovingAverage = map average . divvy 20 1
divvy :: Int -> Int -> [a] -> [[a]]
divvy :: forall a. Int -> Int -> [a] -> [[a]]
divvy Int
_ Int
_ [] = []
divvy Int
n Int
m [a]
lst = ([a] -> Bool) -> [[a]] -> [[a]]
forall a. (a -> Bool) -> [a] -> [a]
filter ((Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
==) (Int -> Bool) -> ([a] -> Int) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length) [[a]]
choppedl
 where
  choppedl :: [[a]]
choppedl = ([a] -> ([a], [a])) -> [a] -> [[a]]
forall a b. ([a] -> (b, [a])) -> [a] -> [b]
chop (\[a]
xs -> (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
n [a]
xs, Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop Int
m [a]
xs)) [a]
lst