Data.Seqn.Internal.MTree

This is an internal module. You probably don't need to import this. Use Data.Seqn.MSeq instead.

WARNING

Definitions in this module allow violating invariants that would otherwise be guaranteed by Data.Seqn.MSeq. Use at your own risk!

Measured

class Semigroup (Measure a) => Measured a where

Types that have a combinable property, called the measure.

Associated Types

type Measure a

Methods

measure :: a -> Measure a

Calculate the measure of a value.

Instances

Ord a => Measured (Elem a)

Defined in Data.Seqn.Internal.PQueue

Associated Types

type Measure (Elem a)

Methods

measure :: Elem a -> Measure (Elem a)

MTree

data MTree a

Constructors

MBin !Int !(Measure a) !a !(MTree a) !(MTree a)

MTip

Instances

(NFData (Measure a), NFData a) => NFData (MTree a)

Defined in Data.Seqn.Internal.MTree

Methods

rnf :: MTree a -> ()

Basic

singleton :: Measured a => a -> MTree a

size :: MTree a -> Int

(<>>) :: Measured a => MTree a -> Measure a -> Measure a infixr 6

(<<>) :: Measured a => Measure a -> MTree a -> Measure a infixr 6

bin :: Measured a => a -> MTree a -> MTree a -> MTree a

binn :: Measured a => Int -> a -> MTree a -> MTree a -> MTree a

Folds

foldMap :: forall a m. Monoid m => (a -> m) -> MTree a -> m

foldl' :: (b -> a -> b) -> b -> MTree a -> b

foldr' :: (a -> b -> b) -> b -> MTree a -> b

ifoldl' :: (Int -> b -> a -> b) -> b -> Int -> MTree a -> b

ifoldr' :: (Int -> a -> b -> b) -> b -> Int -> MTree a -> b

traverse :: (Measured b, Applicative f) => (a -> f b) -> MTree a -> f (MTree b)

ifoldMap :: Monoid m => (Int -> a -> m) -> Int -> MTree a -> m

itraverse :: (Measured b, Applicative f) => (Int -> a -> f b) -> Int -> MTree a -> f (MTree b)

Construct

generateA :: (Measured a, Applicative f) => (Int -> f a) -> Int -> Int -> f (MTree a)

Index

index :: Int -> MTree a -> a

adjustF :: (Measured a, Functor f) => (a -> f a) -> Int -> MTree a -> f (MTree a)

insertAt :: Measured a => Int -> a -> MTree a -> MTree a

deleteAt :: Measured a => Int -> MTree a -> MTree a

Slice

cons :: Measured a => a -> MTree a -> MTree a

snoc :: Measured a => MTree a -> a -> MTree a

uncons :: Measured a => MTree a -> SMaybe (S2 a (MTree a))

unconsSure :: Measured a => a -> MTree a -> MTree a -> S2 a (MTree a)

unsnoc :: Measured a => MTree a -> SMaybe (S2 (MTree a) a)

unsnocSure :: Measured a => a -> MTree a -> MTree a -> S2 (MTree a) a

splitAtF :: (Measured a, Biapplicative f) => Int -> MTree a -> f (MTree a) (S2 a (MTree a))

Transform

mapMaybeA :: (Applicative f, Measured b) => (a -> f (Maybe b)) -> MTree a -> f (MTree b)

mapEitherA :: (Applicative f, Measured b, Measured c) => (a -> f (Either b c)) -> MTree a -> f (S2 (MTree b) (MTree c))

Force

liftRnf2 :: (Measure a -> ()) -> (a -> ()) -> MTree a -> ()

Zip and unzip

zipWithStreamM :: (Measured c, Monad m) => (a -> b -> m c) -> MTree a -> Stream b -> m (MTree c)

unzipWithA :: (Measured b, Measured c, Applicative f) => (a -> f (b, c)) -> MTree a -> f (S2 (MTree b) (MTree c))

unzipWith3A :: (Measured b, Measured c, Measured d, Applicative f) => (a -> f (b, c, d)) -> MTree a -> f (S3 (MTree b) (MTree c) (MTree d))

Tree helpers

fold :: b -> (Int -> a -> b -> b -> b) -> (Int -> a -> b -> b) -> (Int -> a -> b -> b) -> (a -> b) -> MTree a -> b

foldSimple :: b -> (Int -> a -> b -> b -> b) -> MTree a -> b

link :: Measured a => a -> MTree a -> MTree a -> MTree a

merge :: Measured a => MTree a -> MTree a -> MTree a

glue :: Measured a => MTree a -> MTree a -> MTree a

balanceL :: Measured a => a -> MTree a -> MTree a -> MTree a

balanceR :: Measured a => a -> MTree a -> MTree a -> MTree a

Testing

valid :: (Measured a, Eq (Measure a)) => MTree a -> Bool

debugShowsPrec :: (Show a, Show (Measure a)) => Int -> MTree a -> ShowS