Copyright	(c) 2022 L. S. Leary
License	BSD3-style (see LICENSE)
Maintainer	@LSLeary (on github)
Stability	unstable
Portability	unportable
Safe Haskell	Safe-Inferred
Language	Haskell2010

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

data History k a
origin :: History k a
event :: Ord k => k -> a -> History k a -> History k a
erase :: Ord k => k -> History k a -> History k a
recall :: Ord k => k -> History k a -> Maybe a
ledger :: History k a -> [(k, a)]
transcribe :: Ord k => [(k, a)] -> History k a

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 Methods readsPrec :: Int -> ReadS (History k a) # readList :: ReadS [History k a] # readPrec :: ReadPrec (History k a) # readListPrec :: ReadPrec [History k a] #
(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.