content: {-# OPTIONS -fno-warn-orphans #-}
  {-# LANGUAGE EmptyDataDecls    #-}
  {-# LANGUAGE StandaloneDeriving #-}
  
  module Data.List where
  
  import Prelude
  import Data.Maybe
  
  -- | The 'isPrefixOf' function takes two lists and returns 'True'
  -- iff the first list is a prefix of the second.
  isPrefixOf              :: (Eq a) => [a] -> [a] -> Bool
  isPrefixOf [] _         =  True
  isPrefixOf _  []        =  False
  isPrefixOf (x:xs) (y:ys)=  x == y && isPrefixOf xs ys
  
  -- | The 'isSuffixOf' function takes two lists and returns 'True'
  -- iff the first list is a suffix of the second.
  -- Both lists must be finite.
  isSuffixOf              :: (Eq a) => [a] -> [a] -> Bool
  isSuffixOf x y          =  reverse x `isPrefixOf` reverse y
  
  -- | The 'stripPrefix' function drops the given prefix from a list.
  -- It returns 'Nothing' if the list did not start with the prefix
  -- given, or 'Just' the list after the prefix, if it does.
  --
  -- > stripPrefix "foo" "foobar" == Just "bar"
  -- > stripPrefix "foo" "foo" == Just ""
  -- > stripPrefix "foo" "barfoo" == Nothing
  -- > stripPrefix "foo" "barfoobaz" == Nothing
  stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]
  stripPrefix [] ys = Just ys
  stripPrefix (x:xs) (y:ys)
   | x == y = stripPrefix xs ys
  stripPrefix _ _ = Nothing
  
  -- | Like 'stripPrefix', but drops the given suffix from the end.
  stripSuffix :: Eq a => [a] -> [a] -> Maybe [a]
  stripSuffix x y = onJust reverse $ reverse x `stripPrefix` reverse y
  
  -- | Split lists at delimiter specified by a condition
  --   Drops empty groups (similar to `words`)
  splitWhen :: (a -> Bool) -> [a] -> [[a]]
  splitWhen p s = case dropWhile p s of
    [] -> []
    s' -> case break p s' of
      (w, s'') -> w : splitWhen p s''
  
  -- | Split lists at the specified delimiter
  --   Drops empty groups (similar to `words`)
  splitOn :: Eq a => a -> [a] -> [[a]]
  splitOn c = splitWhen (==c)
  
  -- | The 'partition' function takes a predicate a list and returns
  -- the pair of lists of elements which do and do not satisfy the
  -- predicate, respectively; i.e.,
  --
  -- > partition p xs == (filter p xs, filter (not . p) xs)
  
  partition :: (a -> Bool) -> [a] -> ([a],[a])
  partition p xs = (filter p xs, filter (not . p) xs)
  {-
  -- Fay doesn't support irrefutable patterns
  partition :: (a -> Bool) -> [a] -> ([a],[a])
  partition p = foldr (select p) ([],[])
    where
      select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
      select p x ~(ts,fs) | p x       = (x:ts,fs)
                          | otherwise = (ts, x:fs)
  -}
  
  -- | The 'inits' function returns all initial segments of the argument,
  -- shortest first.  For example,
  --
  -- > inits "abc" == ["","a","ab","abc"]
  --
  -- Note that 'inits' has the following strictness property:
  -- @inits _|_ = [] : _|_@
  inits                   :: [a] -> [[a]]
  inits xs                =  [] : case xs of
                                    []      -> []
                                    x : xs' -> map (x :) (inits xs')
  
  -- This one /isn't/ from Data.List
  groupSortBy :: (a -> a -> Ordering) -> [a] -> [[a]]
  groupSortBy f = groupBy (\x y -> f x y == EQ) . sortBy f
  
  -- | Classic group by.
  groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
  groupBy _  []           =  []
  groupBy eq (x:xs)       =  case span (eq x) xs of
    (ys,zs) -> (x:ys) : groupBy eq zs
  
  -- | Belongs in Control.Monad, right?
  findM :: (a -> Fay (Maybe b)) -> [a] -> Fay (Maybe b)
  findM _ [] = return Nothing
  findM f (x:xs) = do
    b <- f x
    case b of
      Nothing -> findM f xs
      Just _ -> return b
  