Data.List

module Data.List(module Data.List,module List) where
import List hiding (genericLength)
import Data.Ord(comparing)

-- | A strict version of 'foldl'.

foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

-- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
-- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
-- result.
intercalate :: [a] -> [[a]] -> [a]
intercalate xs xss = concat (intersperse xs xss)

isInfixOf               :: (Eq a) => [a] -> [a] -> Bool
isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)

stripPrefix xs ys =
    if xs==take n ys
    then Just (drop n ys)
    else Nothing
  where
    n = length xs

sortOn f = sortBy (comparing f)

-- | The 'permutations' function returns the list of all permutations of
-- the argument.
-- > permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
permutations            :: [a] -> [[a]]
permutations xs0        =  xs0 : perms xs0 []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

-- | In Haskell 2010 genericLength works with any type in the Num class,
-- in Haskell 98 it is restricted to types in the Integral class
genericLength           :: Num a => [b] -> a
genericLength []        =  0
genericLength (x:xs)    =  1 + genericLength xs

subsequences [] = [[]]
subsequences (x:xs) = --concatMap (\xs->[xs,x:xs])
                      foldr (\xs r->xs:(x:xs):r) [] (subsequences xs)