ListLike 4.4 → 4.5

+ Data.ListLike: stripPrefix :: (ListLike full item, Eq item) => full -> full -> Maybe full

+ Data.ListLike: stripSuffix :: (ListLike full item, Eq item) => full -> full -> Maybe full

+ Data.ListLike.Base: stripPrefix :: (ListLike full item, Eq item) => full -> full -> Maybe full

+ Data.ListLike.Base: stripSuffix :: (ListLike full item, Eq item) => full -> full -> Maybe full

+ Data.ListLike: class (FoldableLL full item, Monoid full) => ListLike full item | full -> item where empty = mempty cons item l = append (singleton item) l snoc l item = append l (singleton item) append = mappend head = maybe (error "head") fst . uncons uncons x = if null x then Nothing else Just (head x, tail x) last l = case genericLength l of { (0 :: Integer) -> error "Called last on empty list" 1 -> head l _ -> last (tail l) } tail = maybe (error "tail") snd . uncons init l | null l = error "init: empty list" | null xs = empty | otherwise = cons (head l) (init xs) where xs = tail l null x = genericLength x == (0 :: Integer) length = genericLength map func inp | null inp = empty | otherwise = cons (func (head inp)) (map func (tail inp)) rigidMap = map reverse l = rev l empty where rev rl a | null rl = a | otherwise = rev (tail rl) (cons (head rl) a) intersperse sep l | null l = empty | null xs = singleton x | otherwise = cons x (cons sep (intersperse sep xs)) where x = head l xs = tail l concat = fold concatMap = foldMap rigidConcatMap = concatMap any p = getAny . foldMap (Any . p) all p = getAll . foldMap (All . p) maximum = foldr1 max minimum = foldr1 min replicate = genericReplicate take = genericTake drop = genericDrop splitAt = genericSplitAt takeWhile func l | null l = empty | func x = cons x (takeWhile func (tail l)) | otherwise = empty where x = head l dropWhile func l | null l = empty | func (head l) = dropWhile func (tail l) | otherwise = l dropWhileEnd func = foldr (\ x xs -> if func x && null xs then empty else cons x xs) empty span func l | null l = (empty, empty) | func x = (cons x ys, zs) | otherwise = (empty, l) where (ys, zs) = span func (tail l) x = head l break p = span (not . p) group = groupBy (==) inits l | null l = singleton empty | otherwise = append (singleton empty) (map (cons (head l)) theinits) where theinits = asTypeOf (inits (tail l)) [l] tails l | null l = singleton empty | otherwise = cons l (tails (tail l)) isPrefixOf needle haystack | null needle = True | null haystack = False | otherwise = (head needle) == (head haystack) && isPrefixOf (tail needle) (tail haystack) isSuffixOf needle haystack = isPrefixOf (reverse needle) (reverse haystack) isInfixOf needle haystack = any (isPrefixOf needle) thetails where thetails = asTypeOf (tails haystack) [haystack] stripPrefix xs ys = if xs `isPrefixOf` ys then Just $ drop (length xs) ys else Nothing stripSuffix xs ys = if xs `isSuffixOf` ys then Just $ take (length ys - length xs) ys else Nothing elem i = any (== i) notElem i = all (/= i) find f l = case findIndex f l of { Nothing -> Nothing Just x -> Just (index l x) } filter func l | null l = empty | func (head l) = cons (head l) (filter func (tail l)) | otherwise = filter func (tail l) partition p xs = (filter p xs, filter (not . p) xs) index l i | null l = error "index: index not found" | i < 0 = error "index: index must be >= 0" | i == 0 = head l | otherwise = index (tail l) (i - 1) elemIndex e l = findIndex (== e) l elemIndices i l = findIndices (== i) l findIndex f = listToMaybe . findIndices f findIndices p xs = map snd $ filter (p . fst) $ thezips where thezips = asTypeOf (zip xs [0 .. ]) [(head xs, 0 :: Int)] sequence l = foldr func (return empty) l where func litem results = do { x <- litem; xs <- results; return (cons x xs) } mapM func l = sequence mapresult where mapresult = asTypeOf (map func l) [] rigidMapM = mapM nub = nubBy (==) delete = deleteBy (==) deleteFirsts = foldl (flip delete) union = unionBy (==) intersect = intersectBy (==) sort = sortBy compare insert = insertBy compare toList = fromListLike fromList [] = empty fromList (x : xs) = cons x (fromList xs) fromListLike = map id nubBy f l = nubBy' l (empty :: full) where nubBy' ys xs | null ys = empty | any (f (head ys)) xs = nubBy' (tail ys) xs | otherwise = let y = head ys in cons y (nubBy' (tail ys) (cons y xs)) deleteBy func i l | null l = empty | otherwise = if func i (head l) then tail l else cons (head l) (deleteBy func i (tail l)) deleteFirstsBy func = foldl (flip (deleteBy func)) unionBy func x y = append x $ foldl (flip (deleteBy func)) (nubBy func y) x intersectBy func xs ys = filter (\ x -> any (func x) ys) xs groupBy eq l | null l = empty | otherwise = cons (cons x ys) (groupBy eq zs) where (ys, zs) = span (eq x) xs x = head l xs = tail l sortBy cmp = foldr (insertBy cmp) empty insertBy cmp x ys | null ys = singleton x | otherwise = case cmp x (head ys) of { GT -> cons (head ys) (insertBy cmp x (tail ys)) _ -> cons x ys } genericLength l = calclen 0 l where calclen !accum cl = if null cl then accum else calclen (accum + 1) (tail cl) genericTake n l | n <= 0 = empty | null l = empty | otherwise = cons (head l) (genericTake (n - 1) (tail l)) genericDrop n l | n <= 0 = l | null l = l | otherwise = genericDrop (n - 1) (tail l) genericSplitAt n l = (genericTake n l, genericDrop n l) genericReplicate count x | count <= 0 = empty | otherwise = map (\ _ -> x) [1 .. count]

+ Data.ListLike.Base: class (FoldableLL full item, Monoid full) => ListLike full item | full -> item where empty = mempty cons item l = append (singleton item) l snoc l item = append l (singleton item) append = mappend head = maybe (error "head") fst . uncons uncons x = if null x then Nothing else Just (head x, tail x) last l = case genericLength l of { (0 :: Integer) -> error "Called last on empty list" 1 -> head l _ -> last (tail l) } tail = maybe (error "tail") snd . uncons init l | null l = error "init: empty list" | null xs = empty | otherwise = cons (head l) (init xs) where xs = tail l null x = genericLength x == (0 :: Integer) length = genericLength map func inp | null inp = empty | otherwise = cons (func (head inp)) (map func (tail inp)) rigidMap = map reverse l = rev l empty where rev rl a | null rl = a | otherwise = rev (tail rl) (cons (head rl) a) intersperse sep l | null l = empty | null xs = singleton x | otherwise = cons x (cons sep (intersperse sep xs)) where x = head l xs = tail l concat = fold concatMap = foldMap rigidConcatMap = concatMap any p = getAny . foldMap (Any . p) all p = getAll . foldMap (All . p) maximum = foldr1 max minimum = foldr1 min replicate = genericReplicate take = genericTake drop = genericDrop splitAt = genericSplitAt takeWhile func l | null l = empty | func x = cons x (takeWhile func (tail l)) | otherwise = empty where x = head l dropWhile func l | null l = empty | func (head l) = dropWhile func (tail l) | otherwise = l dropWhileEnd func = foldr (\ x xs -> if func x && null xs then empty else cons x xs) empty span func l | null l = (empty, empty) | func x = (cons x ys, zs) | otherwise = (empty, l) where (ys, zs) = span func (tail l) x = head l break p = span (not . p) group = groupBy (==) inits l | null l = singleton empty | otherwise = append (singleton empty) (map (cons (head l)) theinits) where theinits = asTypeOf (inits (tail l)) [l] tails l | null l = singleton empty | otherwise = cons l (tails (tail l)) isPrefixOf needle haystack | null needle = True | null haystack = False | otherwise = (head needle) == (head haystack) && isPrefixOf (tail needle) (tail haystack) isSuffixOf needle haystack = isPrefixOf (reverse needle) (reverse haystack) isInfixOf needle haystack = any (isPrefixOf needle) thetails where thetails = asTypeOf (tails haystack) [haystack] stripPrefix xs ys = if xs `isPrefixOf` ys then Just $ drop (length xs) ys else Nothing stripSuffix xs ys = if xs `isSuffixOf` ys then Just $ take (length ys - length xs) ys else Nothing elem i = any (== i) notElem i = all (/= i) find f l = case findIndex f l of { Nothing -> Nothing Just x -> Just (index l x) } filter func l | null l = empty | func (head l) = cons (head l) (filter func (tail l)) | otherwise = filter func (tail l) partition p xs = (filter p xs, filter (not . p) xs) index l i | null l = error "index: index not found" | i < 0 = error "index: index must be >= 0" | i == 0 = head l | otherwise = index (tail l) (i - 1) elemIndex e l = findIndex (== e) l elemIndices i l = findIndices (== i) l findIndex f = listToMaybe . findIndices f findIndices p xs = map snd $ filter (p . fst) $ thezips where thezips = asTypeOf (zip xs [0 .. ]) [(head xs, 0 :: Int)] sequence l = foldr func (return empty) l where func litem results = do { x <- litem; xs <- results; return (cons x xs) } mapM func l = sequence mapresult where mapresult = asTypeOf (map func l) [] rigidMapM = mapM nub = nubBy (==) delete = deleteBy (==) deleteFirsts = foldl (flip delete) union = unionBy (==) intersect = intersectBy (==) sort = sortBy compare insert = insertBy compare toList = fromListLike fromList [] = empty fromList (x : xs) = cons x (fromList xs) fromListLike = map id nubBy f l = nubBy' l (empty :: full) where nubBy' ys xs | null ys = empty | any (f (head ys)) xs = nubBy' (tail ys) xs | otherwise = let y = head ys in cons y (nubBy' (tail ys) (cons y xs)) deleteBy func i l | null l = empty | otherwise = if func i (head l) then tail l else cons (head l) (deleteBy func i (tail l)) deleteFirstsBy func = foldl (flip (deleteBy func)) unionBy func x y = append x $ foldl (flip (deleteBy func)) (nubBy func y) x intersectBy func xs ys = filter (\ x -> any (func x) ys) xs groupBy eq l | null l = empty | otherwise = cons (cons x ys) (groupBy eq zs) where (ys, zs) = span (eq x) xs x = head l xs = tail l sortBy cmp = foldr (insertBy cmp) empty insertBy cmp x ys | null ys = singleton x | otherwise = case cmp x (head ys) of { GT -> cons (head ys) (insertBy cmp x (tail ys)) _ -> cons x ys } genericLength l = calclen 0 l where calclen !accum cl = if null cl then accum else calclen (accum + 1) (tail cl) genericTake n l | n <= 0 = empty | null l = empty | otherwise = cons (head l) (genericTake (n - 1) (tail l)) genericDrop n l | n <= 0 = l | null l = l | otherwise = genericDrop (n - 1) (tail l) genericSplitAt n l = (genericTake n l, genericDrop n l) genericReplicate count x | count <= 0 = empty | otherwise = map (\ _ -> x) [1 .. count]