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)