xmonad-contrib-0.17.1.9: Community-maintained extensions for xmonad
Copyright(c) 2022 L. S. Leary
LicenseBSD3-style (see LICENSE)
Maintainer@LSLeary (on github)
Stabilityunstable
Portabilityunportable
Safe HaskellSafe-Inferred
LanguageHaskell2010

XMonad.Util.History

Description

Provides History, a variation on a LIFO stack with a uniqueness property. In order to achieve the desired asymptotics, the data type is implemented as an ordered Map.

Synopsis

Documentation

data History k a Source #

A history of unique k-events with a-annotations.

History k a can be considered a (LIFO) stack of (k, a) values with the property that each k is unique. From this point of view, event pushes and ledger pops/peeks all.

The naive implementation has O(n) event and erase due to the uniqueness condition, but we can still use it as a denotation:

mu :: History k a -> [(k, a)]

As an opaque data type with strict operations, History k a values are all finite expressions in the core interface: origin, erase and event. Hence we define mu by structural induction on these three cases.

Instances

Instances details
Foldable (History k) Source # 
Instance details

Defined in XMonad.Util.History

Methods

fold :: Monoid m => History k m -> m #

foldMap :: Monoid m => (a -> m) -> History k a -> m #

foldMap' :: Monoid m => (a -> m) -> History k a -> m #

foldr :: (a -> b -> b) -> b -> History k a -> b #

foldr' :: (a -> b -> b) -> b -> History k a -> b #

foldl :: (b -> a -> b) -> b -> History k a -> b #

foldl' :: (b -> a -> b) -> b -> History k a -> b #

foldr1 :: (a -> a -> a) -> History k a -> a #

foldl1 :: (a -> a -> a) -> History k a -> a #

toList :: History k a -> [a] #

null :: History k a -> Bool #

length :: History k a -> Int #

elem :: Eq a => a -> History k a -> Bool #

maximum :: Ord a => History k a -> a #

minimum :: Ord a => History k a -> a #

sum :: Num a => History k a -> a #

product :: Num a => History k a -> a #

Traversable (History k) Source # 
Instance details

Defined in XMonad.Util.History

Methods

traverse :: Applicative f => (a -> f b) -> History k a -> f (History k b) #

sequenceA :: Applicative f => History k (f a) -> f (History k a) #

mapM :: Monad m => (a -> m b) -> History k a -> m (History k b) #

sequence :: Monad m => History k (m a) -> m (History k a) #

Functor (History k) Source # 
Instance details

Defined in XMonad.Util.History

Methods

fmap :: (a -> b) -> History k a -> History k b #

(<$) :: a -> History k b -> History k a #

(Read k, Read a, Ord k) => Read (History k a) Source # 
Instance details

Defined in XMonad.Util.History

(Show k, Show a) => Show (History k a) Source # 
Instance details

Defined in XMonad.Util.History

Methods

showsPrec :: Int -> History k a -> ShowS #

show :: History k a -> String #

showList :: [History k a] -> ShowS #

(Eq k, Eq a) => Eq (History k a) Source # 
Instance details

Defined in XMonad.Util.History

Methods

(==) :: History k a -> History k a -> Bool #

(/=) :: History k a -> History k a -> Bool #

(Ord k, Ord a) => Ord (History k a) Source # 
Instance details

Defined in XMonad.Util.History

Methods

compare :: History k a -> History k a -> Ordering #

(<) :: History k a -> History k a -> Bool #

(<=) :: History k a -> History k a -> Bool #

(>) :: History k a -> History k a -> Bool #

(>=) :: History k a -> History k a -> Bool #

max :: History k a -> History k a -> History k a #

min :: History k a -> History k a -> History k a #

origin :: History k a Source #

O(1). A history of nothing.

mu origin := []

event :: Ord k => k -> a -> History k a -> History k a Source #

O(log n). A new event makes history; its predecessor forgotten.

mu (event k a h) := (k, a) : mu (erase k h)

erase :: Ord k => k -> History k a -> History k a Source #

O(log n). Erase an event from history.

mu (erase k h) := filter ((k /=) . fst) (mu h)

recall :: Ord k => k -> History k a -> Maybe a Source #

O(log n). Recall an event.

ledger :: History k a -> [(k, a)] Source #

O(n). Read history, starting with the modern day. ledger is mu.

transcribe :: Ord k => [(k, a)] -> History k a Source #

O(n * log n). Transcribe a ledger.