{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE TypeFamilies #-}
module Data.List.Kleene.Star
(
Star(..)
,pattern (:*)
,Plus(..)
,filter
,reverse
,uncons
,take
,(!!)
,unfoldr
,scanr
,scanl
,prescanl
,prescanr
,sortBy
,sortOn
,sort
)
where
import Data.List.Kleene.Internal
import Data.Ord
import Prelude hiding (filter, head, reverse, scanl,
scanr, take, (!!))
sortBy :: (a -> a -> Ordering) -> Star a -> Star a
sortBy :: (a -> a -> Ordering) -> Star a -> Star a
sortBy _ Nil = Star a
forall a. Star a
Nil
sortBy cmp :: a -> a -> Ordering
cmp (Cons xs :: Plus a
xs) = Plus a -> Star a
forall a. Plus a -> Star a
Cons ((a -> Plus a) -> (Plus a -> Plus a -> Plus a) -> Plus a -> Plus a
forall a b. (a -> b) -> (b -> b -> b) -> Plus a -> b
treeFoldMap a -> Plus a
forall a. a -> Plus a
One ((a -> a -> Ordering) -> Plus a -> Plus a -> Plus a
forall a. (a -> a -> Ordering) -> Plus a -> Plus a -> Plus a
mergelr a -> a -> Ordering
cmp) Plus a
xs)
sortOn :: Ord b => (a -> b) -> Star a -> Star a
sortOn :: (a -> b) -> Star a -> Star a
sortOn _ Nil = Star a
forall a. Star a
Nil
sortOn c :: a -> b
c (Cons xs :: Plus a
xs) = Plus a -> Star a
forall a. Plus a -> Star a
Cons (((a, b) -> a) -> Plus (a, b) -> Plus a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, b) -> a
forall a b. (a, b) -> a
fst ((a -> Plus (a, b))
-> (Plus (a, b) -> Plus (a, b) -> Plus (a, b))
-> Plus a
-> Plus (a, b)
forall a b. (a -> b) -> (b -> b -> b) -> Plus a -> b
treeFoldMap (\x :: a
x -> (a, b) -> Plus (a, b)
forall a. a -> Plus a
One (a
x, a -> b
c a
x)) (((a, b) -> (a, b) -> Ordering)
-> Plus (a, b) -> Plus (a, b) -> Plus (a, b)
forall a. (a -> a -> Ordering) -> Plus a -> Plus a -> Plus a
mergelr (((a, b) -> b) -> (a, b) -> (a, b) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (a, b) -> b
forall a b. (a, b) -> b
snd)) Plus a
xs))
sort :: Ord a => Star a -> Star a
sort :: Star a -> Star a
sort = (a -> a -> Ordering) -> Star a -> Star a
forall a. (a -> a -> Ordering) -> Star a -> Star a
sortBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
unfoldr :: (b -> Maybe (a, b)) -> b -> Star a
unfoldr :: (b -> Maybe (a, b)) -> b -> Star a
unfoldr f :: b -> Maybe (a, b)
f b :: b
b = Star a -> ((a, b) -> Star a) -> Maybe (a, b) -> Star a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Star a
forall a. Star a
Nil (\(x :: a
x, xs :: b
xs) -> a
x a -> Star a -> Star a
forall a. a -> Star a -> Star a
:* (b -> Maybe (a, b)) -> b -> Star a
forall b a. (b -> Maybe (a, b)) -> b -> Star a
unfoldr b -> Maybe (a, b)
f b
xs) (b -> Maybe (a, b)
f b
b)
prescanl :: (b -> a -> b) -> b -> Star a -> Star b
prescanl :: (b -> a -> b) -> b -> Star a -> Star b
prescanl = (b -> a -> b) -> b -> Star a -> Star b
forall b a. (b -> a -> b) -> b -> Star a -> Star b
prescanlStar
prescanr :: (a -> b -> b) -> b -> Star a -> Star b
prescanr :: (a -> b -> b) -> b -> Star a -> Star b
prescanr _ _ Nil = Star b
forall a. Star a
Nil
prescanr f :: a -> b -> b
f b :: b
b (Cons xs :: Plus a
xs) = Plus b -> Star b
forall a. Plus a -> Star a
Cons (Plus a -> Plus b
go Plus a
xs)
where
go :: Plus a -> Plus b
go (One x :: a
x) = b -> Plus b
forall a. a -> Plus a
One (a -> b -> b
f a
x b
b)
go (y :: a
y :+ ys :: Plus a
ys) = a -> b -> b
f a
y (Plus b -> b
forall a. Plus a -> a
head Plus b
zs) b -> Plus b -> Plus b
forall a. a -> Plus a -> Plus a
:+ Plus b
zs
where
zs :: Plus b
zs = Plus a -> Plus b
go Plus a
ys
reverse :: Star a -> Star a
reverse :: Star a -> Star a
reverse = (Star a -> a -> Star a) -> Star a -> Star a -> Star a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((a -> Star a -> Star a) -> Star a -> a -> Star a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> Star a -> Star a
forall a. a -> Star a -> Star a
(:*)) Star a
forall a. Star a
Nil
uncons :: Star a -> Maybe (Plus a)
uncons :: Star a -> Maybe (Plus a)
uncons Nil = Maybe (Plus a)
forall a. Maybe a
Nothing
uncons (Cons xs :: Plus a
xs) = Plus a -> Maybe (Plus a)
forall a. a -> Maybe a
Just Plus a
xs
take :: Int -> Star a -> Star a
take :: Int -> Star a -> Star a
take = Int -> Star a -> Star a
forall a. Int -> Star a -> Star a
takeStar
(!!) :: Star a -> Int -> a
!! :: Star a -> Int -> a
(!!) = Star a -> Int -> a
forall a. Star a -> Int -> a
indexStar