{-# LANGUAGE BangPatterns #-} {-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE DeriveFoldable #-} {-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE DeriveTraversable #-} {-# LANGUAGE PatternSynonyms #-} {-# LANGUAGE TypeFamilies #-} -- | -- Module : Data.List.Kleene.Internal -- Description : Common utility functions and definitions for the kleene-list package. -- Copyright : (c) Donnacha Oisín Kidney, 2020 -- License : Apache -- Maintainer : mail@doisinkidney.com -- Stability : experimental -- Portability : ghc -- -- = WARNING -- -- This module is considered __internal__. -- -- The Package Versioning Policy __does not apply__. -- -- This contents of this module may change __in any way whatsoever__ -- and __without any warning__ between minor versions of this package. -- -- Authors importing this module are expected to track development -- closely. {-# OPTIONS_HADDOCK not-home #-} module Data.List.Kleene.Internal where import Control.DeepSeq (NFData (rnf)) import Data.Data (Data, Typeable) import Data.Functor.Classes import GHC.Generics (Generic) import GHC.Exts (IsList) import qualified GHC.Exts import Control.Applicative import Control.Monad import Control.Monad.Fix import Control.Monad.Zip import Data.Foldable import Prelude hiding (filter, head, scanl, scanr, tail) -- | A list, based on the Kleene star. -- This type is isomorphic to Haskell's standard @[]@ type, so it can be used -- in the same way. data Star a = Nil | Cons (Plus a) deriving (Star a -> Star a -> Bool (Star a -> Star a -> Bool) -> (Star a -> Star a -> Bool) -> Eq (Star a) forall a. Eq a => Star a -> Star a -> Bool forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: Star a -> Star a -> Bool $c/= :: forall a. Eq a => Star a -> Star a -> Bool == :: Star a -> Star a -> Bool $c== :: forall a. Eq a => Star a -> Star a -> Bool Eq, Eq (Star a) Eq (Star a) => (Star a -> Star a -> Ordering) -> (Star a -> Star a -> Bool) -> (Star a -> Star a -> Bool) -> (Star a -> Star a -> Bool) -> (Star a -> Star a -> Bool) -> (Star a -> Star a -> Star a) -> (Star a -> Star a -> Star a) -> Ord (Star a) Star a -> Star a -> Bool Star a -> Star a -> Ordering Star a -> Star a -> Star a forall a. Eq a => (a -> a -> Ordering) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> a) -> (a -> a -> a) -> Ord a forall a. Ord a => Eq (Star a) forall a. Ord a => Star a -> Star a -> Bool forall a. Ord a => Star a -> Star a -> Ordering forall a. Ord a => Star a -> Star a -> Star a min :: Star a -> Star a -> Star a $cmin :: forall a. Ord a => Star a -> Star a -> Star a max :: Star a -> Star a -> Star a $cmax :: forall a. Ord a => Star a -> Star a -> Star a >= :: Star a -> Star a -> Bool $c>= :: forall a. Ord a => Star a -> Star a -> Bool > :: Star a -> Star a -> Bool $c> :: forall a. Ord a => Star a -> Star a -> Bool <= :: Star a -> Star a -> Bool $c<= :: forall a. Ord a => Star a -> Star a -> Bool < :: Star a -> Star a -> Bool $c< :: forall a. Ord a => Star a -> Star a -> Bool compare :: Star a -> Star a -> Ordering $ccompare :: forall a. Ord a => Star a -> Star a -> Ordering $cp1Ord :: forall a. Ord a => Eq (Star a) Ord, (forall x. Star a -> Rep (Star a) x) -> (forall x. Rep (Star a) x -> Star a) -> Generic (Star a) forall x. Rep (Star a) x -> Star a forall x. Star a -> Rep (Star a) x forall a. (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a forall a x. Rep (Star a) x -> Star a forall a x. Star a -> Rep (Star a) x $cto :: forall a x. Rep (Star a) x -> Star a $cfrom :: forall a x. Star a -> Rep (Star a) x Generic, Typeable (Star a) DataType Constr Typeable (Star a) => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Star a -> c (Star a)) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Star a)) -> (Star a -> Constr) -> (Star a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Star a))) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Star a))) -> ((forall b. Data b => b -> b) -> Star a -> Star a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r) -> (forall u. (forall d. Data d => d -> u) -> Star a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> Star a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> Star a -> m (Star a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Star a -> m (Star a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Star a -> m (Star a)) -> Data (Star a) Star a -> DataType Star a -> Constr (forall d. Data d => c (t d)) -> Maybe (c (Star a)) (forall b. Data b => b -> b) -> Star a -> Star a (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Star a -> c (Star a) (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Star a) forall a. Data a => Typeable (Star a) forall a. Data a => Star a -> DataType forall a. Data a => Star a -> Constr forall a. Data a => (forall b. Data b => b -> b) -> Star a -> Star a forall a u. Data a => Int -> (forall d. Data d => d -> u) -> Star a -> u forall a u. Data a => (forall d. Data d => d -> u) -> Star a -> [u] forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> Star a -> m (Star a) forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> Star a -> m (Star a) forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Star a) forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Star a -> c (Star a) forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (Star a)) forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Star a)) forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> Star a -> u forall u. (forall d. Data d => d -> u) -> Star a -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> Star a -> m (Star a) forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Star a -> m (Star a) forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Star a) forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Star a -> c (Star a) forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Star a)) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Star a)) $cCons :: Constr $cNil :: Constr $tStar :: DataType gmapMo :: (forall d. Data d => d -> m d) -> Star a -> m (Star a) $cgmapMo :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> Star a -> m (Star a) gmapMp :: (forall d. Data d => d -> m d) -> Star a -> m (Star a) $cgmapMp :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> Star a -> m (Star a) gmapM :: (forall d. Data d => d -> m d) -> Star a -> m (Star a) $cgmapM :: forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> Star a -> m (Star a) gmapQi :: Int -> (forall d. Data d => d -> u) -> Star a -> u $cgmapQi :: forall a u. Data a => Int -> (forall d. Data d => d -> u) -> Star a -> u gmapQ :: (forall d. Data d => d -> u) -> Star a -> [u] $cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> Star a -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r $cgmapQr :: forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r $cgmapQl :: forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Star a -> r gmapT :: (forall b. Data b => b -> b) -> Star a -> Star a $cgmapT :: forall a. Data a => (forall b. Data b => b -> b) -> Star a -> Star a dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Star a)) $cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Star a)) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (Star a)) $cdataCast1 :: forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (Star a)) dataTypeOf :: Star a -> DataType $cdataTypeOf :: forall a. Data a => Star a -> DataType toConstr :: Star a -> Constr $ctoConstr :: forall a. Data a => Star a -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Star a) $cgunfold :: forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Star a) gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Star a -> c (Star a) $cgfoldl :: forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Star a -> c (Star a) $cp1Data :: forall a. Data a => Typeable (Star a) Data, Typeable, a -> Star b -> Star a (a -> b) -> Star a -> Star b (forall a b. (a -> b) -> Star a -> Star b) -> (forall a b. a -> Star b -> Star a) -> Functor Star forall a b. a -> Star b -> Star a forall a b. (a -> b) -> Star a -> Star b forall (f :: * -> *). (forall a b. (a -> b) -> f a -> f b) -> (forall a b. a -> f b -> f a) -> Functor f <$ :: a -> Star b -> Star a $c<$ :: forall a b. a -> Star b -> Star a fmap :: (a -> b) -> Star a -> Star b $cfmap :: forall a b. (a -> b) -> Star a -> Star b Functor, Functor Star Foldable Star (Functor Star, Foldable Star) => (forall (f :: * -> *) a b. Applicative f => (a -> f b) -> Star a -> f (Star b)) -> (forall (f :: * -> *) a. Applicative f => Star (f a) -> f (Star a)) -> (forall (m :: * -> *) a b. Monad m => (a -> m b) -> Star a -> m (Star b)) -> (forall (m :: * -> *) a. Monad m => Star (m a) -> m (Star a)) -> Traversable Star (a -> f b) -> Star a -> f (Star b) forall (t :: * -> *). (Functor t, Foldable t) => (forall (f :: * -> *) a b. Applicative f => (a -> f b) -> t a -> f (t b)) -> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a)) -> (forall (m :: * -> *) a b. Monad m => (a -> m b) -> t a -> m (t b)) -> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a)) -> Traversable t forall (m :: * -> *) a. Monad m => Star (m a) -> m (Star a) forall (f :: * -> *) a. Applicative f => Star (f a) -> f (Star a) forall (m :: * -> *) a b. Monad m => (a -> m b) -> Star a -> m (Star b) forall (f :: * -> *) a b. Applicative f => (a -> f b) -> Star a -> f (Star b) sequence :: Star (m a) -> m (Star a) $csequence :: forall (m :: * -> *) a. Monad m => Star (m a) -> m (Star a) mapM :: (a -> m b) -> Star a -> m (Star b) $cmapM :: forall (m :: * -> *) a b. Monad m => (a -> m b) -> Star a -> m (Star b) sequenceA :: Star (f a) -> f (Star a) $csequenceA :: forall (f :: * -> *) a. Applicative f => Star (f a) -> f (Star a) traverse :: (a -> f b) -> Star a -> f (Star b) $ctraverse :: forall (f :: * -> *) a b. Applicative f => (a -> f b) -> Star a -> f (Star b) $cp2Traversable :: Foldable Star $cp1Traversable :: Functor Star Traversable) infixr 5 :- -- | A non-empty list type, based on the Kleene plus. -- This type is isomorphic to 'Data.List.NonEmpty.NonEmpty' type, so it -- can be used in the same way. data Plus a = (:-) { Plus a -> a head :: a , Plus a -> Star a tail :: Star a } deriving (Plus a -> Plus a -> Bool (Plus a -> Plus a -> Bool) -> (Plus a -> Plus a -> Bool) -> Eq (Plus a) forall a. Eq a => Plus a -> Plus a -> Bool forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: Plus a -> Plus a -> Bool $c/= :: forall a. Eq a => Plus a -> Plus a -> Bool == :: Plus a -> Plus a -> Bool $c== :: forall a. Eq a => Plus a -> Plus a -> Bool Eq, Eq (Plus a) Eq (Plus a) => (Plus a -> Plus a -> Ordering) -> (Plus a -> Plus a -> Bool) -> (Plus a -> Plus a -> Bool) -> (Plus a -> Plus a -> Bool) -> (Plus a -> Plus a -> Bool) -> (Plus a -> Plus a -> Plus a) -> (Plus a -> Plus a -> Plus a) -> Ord (Plus a) Plus a -> Plus a -> Bool Plus a -> Plus a -> Ordering Plus a -> Plus a -> Plus a forall a. Eq a => (a -> a -> Ordering) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> a) -> (a -> a -> a) -> Ord a forall a. Ord a => Eq (Plus a) forall a. Ord a => Plus a -> Plus a -> Bool forall a. Ord a => Plus a -> Plus a -> Ordering forall a. Ord a => Plus a -> Plus a -> Plus a min :: Plus a -> Plus a -> Plus a $cmin :: forall a. Ord a => Plus a -> Plus a -> Plus a max :: Plus a -> Plus a -> Plus a $cmax :: forall a. Ord a => Plus a -> Plus a -> Plus a >= :: Plus a -> Plus a -> Bool $c>= :: forall a. Ord a => Plus a -> Plus a -> Bool > :: Plus a -> Plus a -> Bool $c> :: forall a. Ord a => Plus a -> Plus a -> Bool <= :: Plus a -> Plus a -> Bool $c<= :: forall a. Ord a => Plus a -> Plus a -> Bool < :: Plus a -> Plus a -> Bool $c< :: forall a. Ord a => Plus a -> Plus a -> Bool compare :: Plus a -> Plus a -> Ordering $ccompare :: forall a. Ord a => Plus a -> Plus a -> Ordering $cp1Ord :: forall a. Ord a => Eq (Plus a) Ord, (forall x. Plus a -> Rep (Plus a) x) -> (forall x. Rep (Plus a) x -> Plus a) -> Generic (Plus a) forall x. Rep (Plus a) x -> Plus a forall x. Plus a -> Rep (Plus a) x forall a. (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a forall a x. Rep (Plus a) x -> Plus a forall a x. Plus a -> Rep (Plus a) x $cto :: forall a x. Rep (Plus a) x -> Plus a $cfrom :: forall a x. Plus a -> Rep (Plus a) x Generic, Typeable (Plus a) DataType Constr Typeable (Plus a) => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Plus a -> c (Plus a)) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Plus a)) -> (Plus a -> Constr) -> (Plus a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Plus a))) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Plus a))) -> ((forall b. Data b => b -> b) -> Plus a -> Plus a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r) -> (forall u. (forall d. Data d => d -> u) -> Plus a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> Plus a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a)) -> Data (Plus a) Plus a -> DataType Plus a -> Constr (forall d. Data d => c (t d)) -> Maybe (c (Plus a)) (forall b. Data b => b -> b) -> Plus a -> Plus a (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Plus a -> c (Plus a) (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Plus a) forall a. Data a => Typeable (Plus a) forall a. Data a => Plus a -> DataType forall a. Data a => Plus a -> Constr forall a. Data a => (forall b. Data b => b -> b) -> Plus a -> Plus a forall a u. Data a => Int -> (forall d. Data d => d -> u) -> Plus a -> u forall a u. Data a => (forall d. Data d => d -> u) -> Plus a -> [u] forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Plus a) forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Plus a -> c (Plus a) forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (Plus a)) forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Plus a)) forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> Plus a -> u forall u. (forall d. Data d => d -> u) -> Plus a -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Plus a) forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Plus a -> c (Plus a) forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Plus a)) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Plus a)) $c:- :: Constr $tPlus :: DataType gmapMo :: (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) $cgmapMo :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) gmapMp :: (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) $cgmapMp :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) gmapM :: (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) $cgmapM :: forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> Plus a -> m (Plus a) gmapQi :: Int -> (forall d. Data d => d -> u) -> Plus a -> u $cgmapQi :: forall a u. Data a => Int -> (forall d. Data d => d -> u) -> Plus a -> u gmapQ :: (forall d. Data d => d -> u) -> Plus a -> [u] $cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> Plus a -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r $cgmapQr :: forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r $cgmapQl :: forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Plus a -> r gmapT :: (forall b. Data b => b -> b) -> Plus a -> Plus a $cgmapT :: forall a. Data a => (forall b. Data b => b -> b) -> Plus a -> Plus a dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Plus a)) $cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Plus a)) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (Plus a)) $cdataCast1 :: forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (Plus a)) dataTypeOf :: Plus a -> DataType $cdataTypeOf :: forall a. Data a => Plus a -> DataType toConstr :: Plus a -> Constr $ctoConstr :: forall a. Data a => Plus a -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Plus a) $cgunfold :: forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Plus a) gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Plus a -> c (Plus a) $cgfoldl :: forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Plus a -> c (Plus a) $cp1Data :: forall a. Data a => Typeable (Plus a) Data, Typeable, a -> Plus b -> Plus a (a -> b) -> Plus a -> Plus b (forall a b. (a -> b) -> Plus a -> Plus b) -> (forall a b. a -> Plus b -> Plus a) -> Functor Plus forall a b. a -> Plus b -> Plus a forall a b. (a -> b) -> Plus a -> Plus b forall (f :: * -> *). (forall a b. (a -> b) -> f a -> f b) -> (forall a b. a -> f b -> f a) -> Functor f <$ :: a -> Plus b -> Plus a $c<$ :: forall a b. a -> Plus b -> Plus a fmap :: (a -> b) -> Plus a -> Plus b $cfmap :: forall a b. (a -> b) -> Plus a -> Plus b Functor, Functor Plus Foldable Plus (Functor Plus, Foldable Plus) => (forall (f :: * -> *) a b. Applicative f => (a -> f b) -> Plus a -> f (Plus b)) -> (forall (f :: * -> *) a. Applicative f => Plus (f a) -> f (Plus a)) -> (forall (m :: * -> *) a b. Monad m => (a -> m b) -> Plus a -> m (Plus b)) -> (forall (m :: * -> *) a. Monad m => Plus (m a) -> m (Plus a)) -> Traversable Plus (a -> f b) -> Plus a -> f (Plus b) forall (t :: * -> *). (Functor t, Foldable t) => (forall (f :: * -> *) a b. Applicative f => (a -> f b) -> t a -> f (t b)) -> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a)) -> (forall (m :: * -> *) a b. Monad m => (a -> m b) -> t a -> m (t b)) -> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a)) -> Traversable t forall (m :: * -> *) a. Monad m => Plus (m a) -> m (Plus a) forall (f :: * -> *) a. Applicative f => Plus (f a) -> f (Plus a) forall (m :: * -> *) a b. Monad m => (a -> m b) -> Plus a -> m (Plus b) forall (f :: * -> *) a b. Applicative f => (a -> f b) -> Plus a -> f (Plus b) sequence :: Plus (m a) -> m (Plus a) $csequence :: forall (m :: * -> *) a. Monad m => Plus (m a) -> m (Plus a) mapM :: (a -> m b) -> Plus a -> m (Plus b) $cmapM :: forall (m :: * -> *) a b. Monad m => (a -> m b) -> Plus a -> m (Plus b) sequenceA :: Plus (f a) -> f (Plus a) $csequenceA :: forall (f :: * -> *) a. Applicative f => Plus (f a) -> f (Plus a) traverse :: (a -> f b) -> Plus a -> f (Plus b) $ctraverse :: forall (f :: * -> *) a b. Applicative f => (a -> f b) -> Plus a -> f (Plus b) $cp2Traversable :: Foldable Plus $cp1Traversable :: Functor Plus Traversable) instance Foldable Star where foldr :: (a -> b -> b) -> b -> Star a -> b foldr _ b :: b b Nil = b b foldr f :: a -> b -> b f b :: b b (Cons xs :: Plus a xs) = (a -> b -> b) -> b -> Plus a -> b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr a -> b -> b f b b Plus a xs foldl :: (b -> a -> b) -> b -> Star a -> b foldl _ b :: b b Nil = b b foldl f :: b -> a -> b f b :: b b (Cons xs :: Plus a xs) = (b -> a -> b) -> b -> Plus a -> b forall (t :: * -> *) b a. Foldable t => (b -> a -> b) -> b -> t a -> b foldl b -> a -> b f b b Plus a xs foldl' :: (b -> a -> b) -> b -> Star a -> b foldl' _ !b b Nil = b b foldl' f :: b -> a -> b f !b b (Cons xs :: Plus a xs) = (b -> a -> b) -> b -> Plus a -> b forall (t :: * -> *) b a. Foldable t => (b -> a -> b) -> b -> t a -> b foldl' b -> a -> b f b b Plus a xs foldl1 :: (a -> a -> a) -> Star a -> a foldl1 _ Nil = [Char] -> a forall a. [Char] -> a errorWithoutStackTrace "foldl1: empty list" foldl1 f :: a -> a -> a f (Cons xs :: Plus a xs) = (a -> a -> a) -> Plus a -> a forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a foldl1 a -> a -> a f Plus a xs foldr1 :: (a -> a -> a) -> Star a -> a foldr1 _ Nil = [Char] -> a forall a. [Char] -> a errorWithoutStackTrace "foldr1: empty list" foldr1 f :: a -> a -> a f (Cons xs :: Plus a xs) = (a -> a -> a) -> Plus a -> a forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a foldr1 a -> a -> a f Plus a xs foldMap :: (a -> m) -> Star a -> m foldMap _ Nil = m forall a. Monoid a => a mempty foldMap f :: a -> m f (Cons xs :: Plus a xs) = (a -> m) -> Plus a -> m forall (t :: * -> *) m a. (Foldable t, Monoid m) => (a -> m) -> t a -> m foldMap a -> m f Plus a xs minimum :: Star a -> a minimum Nil = [Char] -> a forall a. [Char] -> a errorWithoutStackTrace "minimum: empty list" minimum (Cons xs :: Plus a xs) = Plus a -> a forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a minimum Plus a xs maximum :: Star a -> a maximum Nil = [Char] -> a forall a. [Char] -> a errorWithoutStackTrace "maximum: empty list" maximum (Cons xs :: Plus a xs) = Plus a -> a forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a maximum Plus a xs instance Foldable Plus where foldr :: (a -> b -> b) -> b -> Plus a -> b foldr f :: a -> b -> b f b :: b b ~(x :: a x :- xs :: Star a xs) = a -> b -> b f a x ((a -> b -> b) -> b -> Star a -> b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr a -> b -> b f b b Star a xs) foldl :: (b -> a -> b) -> b -> Plus a -> b foldl f :: b -> a -> b f b :: b b ~(x :: a x :- xs :: Star a xs) = (b -> a -> b) -> b -> Star a -> b forall (t :: * -> *) b a. Foldable t => (b -> a -> b) -> b -> t a -> b foldl b -> a -> b f (b -> a -> b f b b a x) Star a xs foldl' :: (b -> a -> b) -> b -> Plus a -> b foldl' f :: b -> a -> b f !b b ~(x :: a x :- xs :: Star a xs) = (b -> a -> b) -> b -> Star a -> b forall (t :: * -> *) b a. Foldable t => (b -> a -> b) -> b -> t a -> b foldl' b -> a -> b f (b -> a -> b f b b a x) Star a xs foldl1 :: (a -> a -> a) -> Plus a -> a foldl1 f :: a -> a -> a f ~(x :: a x :- xs :: Star a xs) = (a -> a -> a) -> a -> Star a -> a forall (t :: * -> *) b a. Foldable t => (b -> a -> b) -> b -> t a -> b foldl a -> a -> a f a x Star a xs foldr1 :: (a -> a -> a) -> Plus a -> a foldr1 f :: a -> a -> a f = Plus a -> a go where go :: Plus a -> a go (x :: a x :- xs :: Star a xs) = case Star a xs of Nil -> a x Cons ys :: Plus a ys -> a -> a -> a f a x (Plus a -> a go Plus a ys) foldMap :: (a -> m) -> Plus a -> m foldMap f :: a -> m f ~(x :: a x :- xs :: Star a xs) = a -> m f a x m -> m -> m forall a. Semigroup a => a -> a -> a <> (a -> m) -> Star a -> m forall (t :: * -> *) m a. (Foldable t, Monoid m) => (a -> m) -> t a -> m foldMap a -> m f Star a xs null :: Plus a -> Bool null _ = Bool False minimum :: Plus a -> a minimum = (a -> a -> a) -> Plus a -> a forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a foldr1 a -> a -> a forall a. Ord a => a -> a -> a min maximum :: Plus a -> a maximum = (a -> a -> a) -> Plus a -> a forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a foldr1 a -> a -> a forall a. Ord a => a -> a -> a max instance Eq1 Star where liftEq :: (a -> b -> Bool) -> Star a -> Star b -> Bool liftEq _ Nil Nil = Bool True liftEq eq :: a -> b -> Bool eq (Cons xs :: Plus a xs) (Cons ys :: Plus b ys) = (a -> b -> Bool) -> Plus a -> Plus b -> Bool forall (f :: * -> *) a b. Eq1 f => (a -> b -> Bool) -> f a -> f b -> Bool liftEq a -> b -> Bool eq Plus a xs Plus b ys liftEq _ _ _ = Bool False instance Eq1 Plus where liftEq :: (a -> b -> Bool) -> Plus a -> Plus b -> Bool liftEq eq :: a -> b -> Bool eq ~(x :: a x :- xs :: Star a xs) (y :: b y :- ys :: Star b ys) = a -> b -> Bool eq a x b y Bool -> Bool -> Bool && (a -> b -> Bool) -> Star a -> Star b -> Bool forall (f :: * -> *) a b. Eq1 f => (a -> b -> Bool) -> f a -> f b -> Bool liftEq a -> b -> Bool eq Star a xs Star b ys instance Ord1 Star where liftCompare :: (a -> b -> Ordering) -> Star a -> Star b -> Ordering liftCompare _ Nil Nil = Ordering EQ liftCompare _ Nil (Cons _) = Ordering LT liftCompare _ (Cons _) Nil = Ordering GT liftCompare c :: a -> b -> Ordering c (Cons xs :: Plus a xs) (Cons ys :: Plus b ys) = (a -> b -> Ordering) -> Plus a -> Plus b -> Ordering forall (f :: * -> *) a b. Ord1 f => (a -> b -> Ordering) -> f a -> f b -> Ordering liftCompare a -> b -> Ordering c Plus a xs Plus b ys instance Ord1 Plus where liftCompare :: (a -> b -> Ordering) -> Plus a -> Plus b -> Ordering liftCompare c :: a -> b -> Ordering c ~(x :: a x :- xs :: Star a xs) ~(y :: b y :- ys :: Star b ys) = a -> b -> Ordering c a x b y Ordering -> Ordering -> Ordering forall a. Semigroup a => a -> a -> a <> (a -> b -> Ordering) -> Star a -> Star b -> Ordering forall (f :: * -> *) a b. Ord1 f => (a -> b -> Ordering) -> f a -> f b -> Ordering liftCompare a -> b -> Ordering c Star a xs Star b ys instance Show1 Plus where liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Plus a -> ShowS liftShowsPrec _ sp :: [a] -> ShowS sp _ = [a] -> ShowS sp ([a] -> ShowS) -> (Plus a -> [a]) -> Plus a -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . (a -> [a] -> [a]) -> [a] -> Plus a -> [a] forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (:) [] instance Show1 Star where liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Star a -> ShowS liftShowsPrec _ sp :: [a] -> ShowS sp _ = [a] -> ShowS sp ([a] -> ShowS) -> (Star a -> [a]) -> Star a -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . (a -> [a] -> [a]) -> [a] -> Star a -> [a] forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (:) [] -- | A pattern for building up star lists as cons-lists. -- -- >>> 1 :* 2 :* 3 :* Nil -- [1,2,3] infixr 5 :* pattern (:*) :: a -> Star a -> Star a pattern $b:* :: a -> Star a -> Star a $m:* :: forall r a. Star a -> (a -> Star a -> r) -> (Void# -> r) -> r (:*) x xs = Cons (x :- xs) {-# COMPLETE (:*), Nil #-} -- | A pattern for building up plus lists as cons-lists. -- -- >>> 1 :+ 2 :+ One 3 -- [1,2,3] infixr 5 :+ pattern (:+) :: a -> Plus a -> Plus a pattern $b:+ :: a -> Plus a -> Plus a $m:+ :: forall r a. Plus a -> (a -> Plus a -> r) -> (Void# -> r) -> r (:+) x xs = x :- Cons xs -- | A pattern for a singleton plus list. pattern One :: a -> Plus a pattern $bOne :: a -> Plus a $mOne :: forall r a. Plus a -> (a -> r) -> (Void# -> r) -> r One x = x :- Nil {-# COMPLETE (:+), One #-} instance IsList (Star a) where type Item (Star a) = a fromList :: [Item (Star a)] -> Star a fromList = (a -> Star a -> Star a) -> Star a -> [a] -> Star a forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr a -> Star a -> Star a forall a. a -> Star a -> Star a (:*) Star a forall a. Star a Nil toList :: Star a -> [Item (Star a)] toList = (a -> [a] -> [a]) -> [a] -> Star a -> [a] forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (:) [] instance IsList (Plus a) where type Item (Plus a) = a fromList :: [Item (Plus a)] -> Plus a fromList [] = [Char] -> Plus a forall a. [Char] -> a errorWithoutStackTrace "Cannot make plus from empty list" fromList (x :: Item (Plus a) x:xs :: [Item (Plus a)] xs) = a Item (Plus a) x a -> Star a -> Plus a forall a. a -> Star a -> Plus a :- [Item (Star a)] -> Star a forall l. IsList l => [Item l] -> l GHC.Exts.fromList [Item (Plus a)] [Item (Star a)] xs toList :: Plus a -> [Item (Plus a)] toList = (a -> [a] -> [a]) -> [a] -> Plus a -> [a] forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (:) [] instance Show a => Show (Star a) where showsPrec :: Int -> Star a -> ShowS showsPrec n :: Int n = Int -> [a] -> ShowS forall a. Show a => Int -> a -> ShowS showsPrec Int n ([a] -> ShowS) -> (Star a -> [a]) -> Star a -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . Star a -> [a] forall (t :: * -> *) a. Foldable t => t a -> [a] toList instance Show a => Show (Plus a) where showsPrec :: Int -> Plus a -> ShowS showsPrec n :: Int n = Int -> [a] -> ShowS forall a. Show a => Int -> a -> ShowS showsPrec Int n ([a] -> ShowS) -> (Plus a -> [a]) -> Plus a -> ShowS forall b c a. (b -> c) -> (a -> b) -> a -> c . Plus a -> [a] forall (t :: * -> *) a. Foldable t => t a -> [a] toList instance NFData a => NFData (Star a) where rnf :: Star a -> () rnf Nil = () rnf (Cons xs :: Plus a xs) = Plus a -> () forall a. NFData a => a -> () rnf Plus a xs instance NFData a => NFData (Plus a) where rnf :: Plus a -> () rnf (x :: a x :- xs :: Star a xs) = a -> () forall a. NFData a => a -> () rnf a x () -> () -> () forall a b. a -> b -> b `seq` Star a -> () forall a. NFData a => a -> () rnf Star a xs instance Semigroup (Plus a) where ~(x :: a x :- xs :: Star a xs) <> :: Plus a -> Plus a -> Plus a <> ys :: Plus a ys = a x a -> Plus a -> Plus a forall a. a -> Plus a -> Plus a :+ (Star a xs Star a -> Plus a -> Plus a forall a. Star a -> Plus a -> Plus a *<>+ Plus a ys) (*<>+) :: Star a -> Plus a -> Plus a Nil *<>+ :: Star a -> Plus a -> Plus a *<>+ ys :: Plus a ys = Plus a ys Cons xs :: Plus a xs *<>+ ys :: Plus a ys = Plus a xs Plus a -> Plus a -> Plus a forall a. Semigroup a => a -> a -> a <> Plus a ys instance Semigroup (Star a) where Nil <> :: Star a -> Star a -> Star a <> ys :: Star a ys = Star a ys Cons xs :: Plus a xs <> ys :: Star a ys = Plus a -> Star a forall a. Plus a -> Star a Cons (Plus a xs Plus a -> Star a -> Plus a forall a. Plus a -> Star a -> Plus a +<>* Star a ys) (+<>*) :: Plus a -> Star a -> Plus a ~(x :: a x :- xs :: Star a xs) +<>* :: Plus a -> Star a -> Plus a +<>* ys :: Star a ys = a x a -> Star a -> Plus a forall a. a -> Star a -> Plus a :- (Star a xs Star a -> Star a -> Star a forall a. Semigroup a => a -> a -> a <> Star a ys) instance Monoid (Star a) where mempty :: Star a mempty = Star a forall a. Star a Nil instance Applicative Star where pure :: a -> Star a pure = Plus a -> Star a forall a. Plus a -> Star a Cons (Plus a -> Star a) -> (a -> Plus a) -> a -> Star a forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> Plus a forall (f :: * -> *) a. Applicative f => a -> f a pure Nil <*> :: Star (a -> b) -> Star a -> Star b <*> _ = Star b forall a. Star a Nil f :: a -> b f :* fs :: Star (a -> b) fs <*> xs :: Star a xs = (a -> Star b -> Star b) -> Star b -> Star a -> Star b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (b -> Star b -> Star b forall a. a -> Star a -> Star a (:*) (b -> Star b -> Star b) -> (a -> b) -> a -> Star b -> Star b forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> b f) (Star (a -> b) fs Star (a -> b) -> Star a -> Star b forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b <*> Star a xs) Star a xs liftA2 :: (a -> b -> c) -> Star a -> Star b -> Star c liftA2 _ Nil _ = Star c forall a. Star a Nil liftA2 f :: a -> b -> c f (x :: a x :* xs :: Star a xs) ys :: Star b ys = (b -> Star c -> Star c) -> Star c -> Star b -> Star c forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (c -> Star c -> Star c forall a. a -> Star a -> Star a (:*) (c -> Star c -> Star c) -> (b -> c) -> b -> Star c -> Star c forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> b -> c f a x) ((a -> b -> c) -> Star a -> Star b -> Star c forall (f :: * -> *) a b c. Applicative f => (a -> b -> c) -> f a -> f b -> f c liftA2 a -> b -> c f Star a xs Star b ys) Star b ys -- | -- >>> (,) <$> (1 :+ 2 :+ One 3) <*> ('a' :+ 'b' :+ One 'c') -- [(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a'),(3,'b'),(3,'c')] -- -- >>> liftA2 (,) (1 :+ 2 :+ One 3) ('a' :+ 'b' :+ One 'c') -- [(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a'),(3,'b'),(3,'c')] instance Applicative Plus where pure :: a -> Plus a pure = a -> Plus a forall a. a -> Plus a One ~(f' :: a -> b f' :- fs' :: Star (a -> b) fs') <*> :: Plus (a -> b) -> Plus a -> Plus b <*> xs :: Plus a xs = a -> b f' (Plus a -> a forall a. Plus a -> a head Plus a xs) b -> Star b -> Plus b forall a. a -> Star a -> Plus a :- (a -> Star b -> Star b) -> Star b -> Star a -> Star b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (b -> Star b -> Star b forall a. a -> Star a -> Star a (:*) (b -> Star b -> Star b) -> (a -> b) -> a -> Star b -> Star b forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> b f') (Star (a -> b) -> Star b go Star (a -> b) fs') (Plus a -> Star a forall a. Plus a -> Star a tail Plus a xs) where go :: Star (a -> b) -> Star b go Nil = Star b forall a. Star a Nil go (f :: a -> b f :* fs :: Star (a -> b) fs) = (a -> Star b -> Star b) -> Star b -> Plus a -> Star b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (b -> Star b -> Star b forall a. a -> Star a -> Star a (:*) (b -> Star b -> Star b) -> (a -> b) -> a -> Star b -> Star b forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> b f) (Star (a -> b) -> Star b go Star (a -> b) fs) Plus a xs liftA2 :: (a -> b -> c) -> Plus a -> Plus b -> Plus c liftA2 f :: a -> b -> c f ~(x' :: a x' :- xs' :: Star a xs') ys :: Plus b ys = a -> b -> c f a x' (Plus b -> b forall a. Plus a -> a head Plus b ys) c -> Star c -> Plus c forall a. a -> Star a -> Plus a :- (b -> Star c -> Star c) -> Star c -> Star b -> Star c forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (c -> Star c -> Star c forall a. a -> Star a -> Star a (:*) (c -> Star c -> Star c) -> (b -> c) -> b -> Star c -> Star c forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> b -> c f a x') (Star a -> Star c go Star a xs') (Plus b -> Star b forall a. Plus a -> Star a tail Plus b ys) where go :: Star a -> Star c go Nil = Star c forall a. Star a Nil go (x :: a x :* xs :: Star a xs) = (b -> Star c -> Star c) -> Star c -> Plus b -> Star c forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (c -> Star c -> Star c forall a. a -> Star a -> Star a (:*) (c -> Star c -> Star c) -> (b -> c) -> b -> Star c -> Star c forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> b -> c f a x) (Star a -> Star c go Star a xs) Plus b ys instance Monad Star where xs :: Star a xs >>= :: Star a -> (a -> Star b) -> Star b >>= f :: a -> Star b f = (a -> Star b -> Star b) -> Star b -> Star a -> Star b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (Star b -> Star b -> Star b forall a. Semigroup a => a -> a -> a (<>) (Star b -> Star b -> Star b) -> (a -> Star b) -> a -> Star b -> Star b forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> Star b f) Star b forall a. Star a Nil Star a xs instance Monad Plus where ~(x :: a x :- xs :: Star a xs) >>= :: Plus a -> (a -> Plus b) -> Plus b >>= f :: a -> Plus b f = a -> Plus b f a x Plus b -> Star b -> Plus b forall a. Plus a -> Star a -> Plus a +<>* Star a -> Star b go Star a xs where go :: Star a -> Star b go Nil = Star b forall a. Star a Nil go (Cons ys :: Plus a ys) = Plus b -> Star b forall a. Plus a -> Star a Cons (Plus a ys Plus a -> (a -> Plus b) -> Plus b forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b >>= a -> Plus b f) instance Alternative Star where <|> :: Star a -> Star a -> Star a (<|>) = Star a -> Star a -> Star a forall a. Semigroup a => a -> a -> a (<>) empty :: Star a empty = Star a forall a. Star a Nil instance MonadPlus Star instance MonadFix Plus where mfix :: (a -> Plus a) -> Plus a mfix f :: a -> Plus a f = case (Plus a -> Plus a) -> Plus a forall a. (a -> a) -> a fix (a -> Plus a f (a -> Plus a) -> (Plus a -> a) -> Plus a -> Plus a forall b c a. (b -> c) -> (a -> b) -> a -> c . Plus a -> a forall a. Plus a -> a head) of ~(x :: a x :- _) -> a x a -> Star a -> Plus a forall a. a -> Star a -> Plus a :- (a -> Star a) -> Star a forall (m :: * -> *) a. MonadFix m => (a -> m a) -> m a mfix (Plus a -> Star a forall a. Plus a -> Star a tail (Plus a -> Star a) -> (a -> Plus a) -> a -> Star a forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> Plus a f) instance MonadFix Star where mfix :: (a -> Star a) -> Star a mfix f :: a -> Star a f = case (Star a -> Star a) -> Star a forall a. (a -> a) -> a fix (a -> Star a f (a -> Star a) -> (Star a -> a) -> Star a -> Star a forall b c a. (b -> c) -> (a -> b) -> a -> c . Plus a -> a forall a. Plus a -> a head (Plus a -> a) -> (Star a -> Plus a) -> Star a -> a forall b c a. (b -> c) -> (a -> b) -> a -> c . Star a -> Plus a forall a. Star a -> Plus a unStar) of Nil -> Star a forall a. Star a Nil (x :: a x :* _) -> a x a -> Star a -> Star a forall a. a -> Star a -> Star a :* (a -> Star a) -> Star a forall (m :: * -> *) a. MonadFix m => (a -> m a) -> m a mfix (Plus a -> Star a forall a. Plus a -> Star a tail (Plus a -> Star a) -> (a -> Plus a) -> a -> Star a forall b c a. (b -> c) -> (a -> b) -> a -> c . Star a -> Plus a forall a. Star a -> Plus a unStar (Star a -> Plus a) -> (a -> Star a) -> a -> Plus a forall b c a. (b -> c) -> (a -> b) -> a -> c . a -> Star a f) where unStar :: Star a -> Plus a unStar ~(Cons xs :: Plus a xs) = Plus a xs instance MonadZip Plus where mzip :: Plus a -> Plus b -> Plus (a, b) mzip ~(x :: a x :- xs :: Star a xs) ~(y :: b y :- ys :: Star b ys) = (a x, b y) (a, b) -> Star (a, b) -> Plus (a, b) forall a. a -> Star a -> Plus a :- Star a -> Star b -> Star (a, b) forall (m :: * -> *) a b. MonadZip m => m a -> m b -> m (a, b) mzip Star a xs Star b ys mzipWith :: (a -> b -> c) -> Plus a -> Plus b -> Plus c mzipWith f :: a -> b -> c f ~(x :: a x :- xs :: Star a xs) ~(y :: b y :- ys :: Star b ys) = a -> b -> c f a x b y c -> Star c -> Plus c forall a. a -> Star a -> Plus a :- (a -> b -> c) -> Star a -> Star b -> Star c forall (m :: * -> *) a b c. MonadZip m => (a -> b -> c) -> m a -> m b -> m c mzipWith a -> b -> c f Star a xs Star b ys munzip :: Plus (a, b) -> (Plus a, Plus b) munzip ~(~(y :: a y,z :: b z) :- xs :: Star (a, b) xs) = (a y a -> Star a -> Plus a forall a. a -> Star a -> Plus a :- Star a ys, b z b -> Star b -> Plus b forall a. a -> Star a -> Plus a :- Star b zs) where ~(ys :: Star a ys,zs :: Star b zs) = Star (a, b) -> (Star a, Star b) forall (m :: * -> *) a b. MonadZip m => m (a, b) -> (m a, m b) munzip Star (a, b) xs instance MonadZip Star where mzip :: Star a -> Star b -> Star (a, b) mzip Nil _ = Star (a, b) forall a. Star a Nil mzip _ Nil = Star (a, b) forall a. Star a Nil mzip (Cons xs :: Plus a xs) (Cons ys :: Plus b ys) = Plus (a, b) -> Star (a, b) forall a. Plus a -> Star a Cons (Plus a -> Plus b -> Plus (a, b) forall (m :: * -> *) a b. MonadZip m => m a -> m b -> m (a, b) mzip Plus a xs Plus b ys) mzipWith :: (a -> b -> c) -> Star a -> Star b -> Star c mzipWith _ Nil _ = Star c forall a. Star a Nil mzipWith _ _ Nil = Star c forall a. Star a Nil mzipWith f :: a -> b -> c f (Cons xs :: Plus a xs) (Cons ys :: Plus b ys) = Plus c -> Star c forall a. Plus a -> Star a Cons ((a -> b -> c) -> Plus a -> Plus b -> Plus c forall (m :: * -> *) a b c. MonadZip m => (a -> b -> c) -> m a -> m b -> m c mzipWith a -> b -> c f Plus a xs Plus b ys) munzip :: Star (a, b) -> (Star a, Star b) munzip Nil = (Star a forall a. Star a Nil, Star b forall a. Star a Nil) munzip (Cons xs :: Plus (a, b) xs) = (Plus a -> Star a forall a. Plus a -> Star a Cons Plus a ys, Plus b -> Star b forall a. Plus a -> Star a Cons Plus b zs) where ~(ys :: Plus a ys,zs :: Plus b zs) = Plus (a, b) -> (Plus a, Plus b) forall (m :: * -> *) a b. MonadZip m => m (a, b) -> (m a, m b) munzip Plus (a, b) xs merge :: (a -> a -> Ordering) -> Star a -> Star a -> Star a merge :: (a -> a -> Ordering) -> Star a -> Star a -> Star a merge _ Nil ys :: Star a ys = Star a ys merge cmp :: a -> a -> Ordering cmp (Cons xs :: Plus a xs) ys :: Star a ys = Plus a -> Star a forall a. Plus a -> Star a Cons ((a -> a -> Ordering) -> Plus a -> Star a -> Plus a forall a. (a -> a -> Ordering) -> Plus a -> Star a -> Plus a mergel a -> a -> Ordering cmp Plus a xs Star a ys) mergel :: (a -> a -> Ordering) -> Plus a -> Star a -> Plus a mergel :: (a -> a -> Ordering) -> Plus a -> Star a -> Plus a mergel _ xs :: Plus a xs Nil = Plus a xs mergel cmp :: a -> a -> Ordering cmp xs :: Plus a xs (Cons ys :: Plus a ys) = (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 Plus a ys merger :: (a -> a -> Ordering) -> Star a -> Plus a -> Plus a merger :: (a -> a -> Ordering) -> Star a -> Plus a -> Plus a merger _ Nil ys :: Plus a ys = Plus a ys merger cmp :: a -> a -> Ordering cmp (Cons xs :: Plus a xs) ys :: Plus a ys = (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 Plus a ys mergelr :: (a -> a -> Ordering) -> Plus a -> Plus a -> Plus a mergelr :: (a -> a -> Ordering) -> Plus a -> Plus a -> Plus a mergelr cmp :: a -> a -> Ordering cmp xss :: Plus a xss@ ~(x :: a x :- xs :: Star a xs) yss :: Plus a yss@ ~(y :: a y :- ys :: Star a ys) = case a -> a -> Ordering cmp a x a y of LT -> a x a -> Plus a -> Plus a forall a. a -> Plus a -> Plus a :+ (a -> a -> Ordering) -> Star a -> Plus a -> Plus a forall a. (a -> a -> Ordering) -> Star a -> Plus a -> Plus a merger a -> a -> Ordering cmp Star a xs Plus a yss EQ -> a x a -> Plus a -> Plus a forall a. a -> Plus a -> Plus a :+ a y a -> Star a -> Plus a forall a. a -> Star a -> Plus a :- (a -> a -> Ordering) -> Star a -> Star a -> Star a forall a. (a -> a -> Ordering) -> Star a -> Star a -> Star a merge a -> a -> Ordering cmp Star a xs Star a ys GT -> a y a -> Plus a -> Plus a forall a. a -> Plus a -> Plus a :+ (a -> a -> Ordering) -> Plus a -> Star a -> Plus a forall a. (a -> a -> Ordering) -> Plus a -> Star a -> Plus a mergel a -> a -> Ordering cmp Plus a xss Star a ys treeFoldMap :: (a -> b) -> (b -> b -> b) -> Plus a -> b treeFoldMap :: (a -> b) -> (b -> b -> b) -> Plus a -> b treeFoldMap c :: a -> b c f :: b -> b -> b f = Plus a -> b go where go :: Plus a -> b go (One x :: a x) = a -> b c a x go (x :: a x :+ y :: a y :- xs :: Star a xs) = Plus b -> b go' (b -> b -> b f (a -> b c a x) (a -> b c a y) b -> Star b -> Plus b forall a. a -> Star a -> Plus a :- Star a -> Star b pairMap Star a xs) pairMap :: Star a -> Star b pairMap (x1 :: a x1 :* x2 :: a x2 :* xs :: Star a xs) = b -> b -> b f (a -> b c a x1) (a -> b c a x2) b -> Star b -> Star b forall a. a -> Star a -> Star a :* Star a -> Star b pairMap Star a xs pairMap (x1 :: a x1 :* Nil) = a -> b c a x1 b -> Star b -> Star b forall a. a -> Star a -> Star a :* Star b forall a. Star a Nil pairMap Nil = Star b forall a. Star a Nil go' :: Plus b -> b go' (One x :: b x) = b x go' (x :: b x :+ y :: b y :- xs :: Star b xs) = Plus b -> b go' (b -> b -> b f b x b y b -> Star b -> Plus b forall a. a -> Star a -> Plus a :- Star b -> Star b pairMap' Star b xs) pairMap' :: Star b -> Star b pairMap' (x1 :: b x1 :* x2 :: b x2 :* xs :: Star b xs) = b -> b -> b f b x1 b x2 b -> Star b -> Star b forall a. a -> Star a -> Star a :* Star b -> Star b pairMap' Star b xs pairMap' xs :: Star b xs = Star b xs -- | -- >>> prescanlPlus (+) 0 [1,2,3] -- [1,3,6] prescanlPlus :: (b -> a -> b) -> b -> Plus a -> Plus b prescanlPlus :: (b -> a -> b) -> b -> Plus a -> Plus b prescanlPlus f :: b -> a -> b f b :: b b (x :: a x :- xs :: Star a xs) = (b -> a -> b) -> b -> Star a -> Plus b forall b a. (b -> a -> b) -> b -> Star a -> Plus b scanl b -> a -> b f (b -> a -> b f b b a x) Star a xs -- | -- >>> prescanlStar (+) 0 [1,2,3] -- [1,3,6] prescanlStar :: (b -> a -> b) -> b -> Star a -> Star b prescanlStar :: (b -> a -> b) -> b -> Star a -> Star b prescanlStar _ _ Nil = Star b forall a. Star a Nil prescanlStar f :: b -> a -> b f b :: b b (Cons xs :: Plus a xs) = Plus b -> Star b forall a. Plus a -> Star a Cons ((b -> a -> b) -> b -> Plus a -> Plus b forall b a. (b -> a -> b) -> b -> Plus a -> Plus b prescanlPlus b -> a -> b f b b Plus a xs) -- | Functions the same as 'Data.List.scanl' in "Data.List". -- -- >>> scanl (+) 0 [1,2,3] -- [0,1,3,6] scanl :: (b -> a -> b) -> b -> Star a -> Plus b scanl :: (b -> a -> b) -> b -> Star a -> Plus b scanl f :: b -> a -> b f b :: b b xs :: Star a xs = b b b -> Star b -> Plus b forall a. a -> Star a -> Plus a :- (b -> a -> b) -> b -> Star a -> Star b forall b a. (b -> a -> b) -> b -> Star a -> Star b prescanlStar b -> a -> b f b b Star a xs -- | Functions the same as 'Data.List.scanr' in "Data.List". -- -- >>> scanr (+) 0 ([1,2,3] :: Star Int) -- [6,5,3,0] scanr :: Foldable f => (a -> b -> b) -> b -> f a -> Plus b scanr :: (a -> b -> b) -> b -> f a -> Plus b scanr f :: a -> b -> b f b :: b b = (a -> Plus b -> Plus b) -> Plus b -> f a -> Plus b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (\x :: a x xs :: Plus b xs -> a -> b -> b f a x (Plus b -> b forall a. Plus a -> a head Plus b xs) b -> Plus b -> Plus b forall a. a -> Plus a -> Plus a :+ Plus b xs) (b -> Plus b forall a. a -> Plus a One b b) -- | Functions the same as 'Data.List.filter' in "Data.List". -- -- >>> filter even ([1..5] :: Star Int) -- [2,4] filter :: Foldable f => (a -> Bool) -> f a -> Star a filter :: (a -> Bool) -> f a -> Star a filter p :: a -> Bool p = (a -> Star a -> Star a) -> Star a -> f a -> Star a forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr a -> Star a -> Star a f Star a forall a. Star a Nil where f :: a -> Star a -> Star a f x :: a x xs :: Star a xs | a -> Bool p a x = a x a -> Star a -> Star a forall a. a -> Star a -> Star a :* Star a xs | Bool otherwise = Star a xs takeStar :: Int -> Star a -> Star a takeStar :: Int -> Star a -> Star a takeStar _ Nil = Star a forall a. Star a Nil takeStar i :: Int i (Cons xs :: Plus a xs) = Int -> Plus a -> Star a forall a. Int -> Plus a -> Star a takePlus Int i Plus a xs takePlus :: Int -> Plus a -> Star a takePlus :: Int -> Plus a -> Star a takePlus 0 _ = Star a forall a. Star a Nil takePlus i :: Int i ~(x :: a x :- xs :: Star a xs) = a x a -> Star a -> Star a forall a. a -> Star a -> Star a :* Int -> Star a -> Star a forall a. Int -> Star a -> Star a takeStar (Int iInt -> Int -> Int forall a. Num a => a -> a -> a -1) Star a xs indexPlus :: Plus a -> Int -> a indexPlus :: Plus a -> Int -> a indexPlus xs :: Plus a xs 0 = Plus a -> a forall a. Plus a -> a head Plus a xs indexPlus xs :: Plus a xs i :: Int i = Star a -> Int -> a forall a. Star a -> Int -> a indexStar (Plus a -> Star a forall a. Plus a -> Star a tail Plus a xs) (Int iInt -> Int -> Int forall a. Num a => a -> a -> a -1) indexStar :: Star a -> Int -> a indexStar :: Star a -> Int -> a indexStar Nil _ = [Char] -> a forall a. [Char] -> a errorWithoutStackTrace "index: empty list!" indexStar (Cons xs :: Plus a xs) i :: Int i = Plus a -> Int -> a forall a. Plus a -> Int -> a indexPlus Plus a xs Int i -- $setup -- >>> :set -XOverloadedLists