xmonad-contrib-0.18.0: Community-maintained extensions for xmonad

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 Source #

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

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

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

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

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

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

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

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

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

null :: History k a -> Bool Source #

length :: History k a -> Int Source #

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

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

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

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

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

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) Source # sequenceA :: Applicative f => History k (f a) -> f (History k a) Source # mapM :: Monad m => (a -> m b) -> History k a -> m (History k b) Source # sequence :: Monad m => History k (m a) -> m (History k a) Source #
Functor (History k) Source # |
Instance details Defined in XMonad.Util.History Methods fmap :: (a -> b) -> History k a -> History k b Source # (<$) :: a -> History k b -> History k a Source #
(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) Source # readList :: ReadS [History k a] Source # readPrec :: ReadPrec (History k a) Source # readListPrec :: ReadPrec [History k a] Source #
(Show k, Show a) => Show (History k a) Source # |
Instance details Defined in XMonad.Util.History Methods showsPrec :: Int -> History k a -> ShowS Source # show :: History k a -> String Source # showList :: [History k a] -> ShowS Source #
(Eq k, Eq a) => Eq (History k a) Source # |
Instance details Defined in XMonad.Util.History Methods (==) :: History k a -> History k a -> Bool Source # (/=) :: History k a -> History k a -> Bool Source #
(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 Source #

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

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

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

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

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

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

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.