Xmonad/Guided tour of the xmonad source/StackSet.hs

From HaskellWiki

StackSet.hs is the pure, functional heart of xmonad. Far removed from corrupting pollutants such as the IO monad and the X server, it is a beautiful, limpid pool of pure code which defines most of the basic data structures used to store the state of xmonad. It is heavily validated by QuickCheck tests; the combination of good use of types and QuickCheck validation means that we can be very confident of the correctness of the code in StackSet.hs.

1

StackSet

of xmonad's state. Let's take a look at the definition of the

data StackSet i l a sid sd =
    StackSet { current  :: !(Screen i l a sid sd)    -- ^ currently focused workspace
             , visible  :: [Screen i l a sid sd]     -- ^ non-focused workspaces, visible in xinerama
             , hidden   :: [Workspace i l a]         -- ^ workspaces not visible anywhere
             , floating :: M.Map a RationalRect      -- ^ floating windows
             } deriving (Show, Read, Eq)

• The first type parameter, here represented by
  i
  , is the type of workspace tags. Each workspace has a tag which uniquely identifies it (and which is shown in your status bar if you use the DynamicLog extension). At the moment, these tags are simply
  String
  s---but, as you can see, the definition of
  StackSet
  doesn't depend on knowing exactly what they are. If, in the future, the xmonad developers decided that
  Complex Double
  s would make better workspace tags, no changes would be required to any of the code in StackSet.hs.

• The second type parameter
  l
  is somewhat mysterious---there isn't much code in StackSet.hs that does much of anything with it. For now, it's enough to know that the type
  l
  has something to do with layouts;
  StackSet
  is completely independent of particular window layouts, so there's not much to see here.

• The third type parameter,
  a
  , is the type of a single window.

• sid
  is a screen id, which identifies a physical screen; as we'll see later, it is (essentially)
  Int
  .

• sd
  , the last type parameter to
  StackSet
  , represents details about a physical screen.

A few comments are in order:

• visible
  is only needed to support multiple physical screens with Xinerama; in a non-Xinerama setup,
  visible
  will always be the empty list.

• Notice that
  current
  and
  visible
  store
  Screen
  s, whereas
  hidden
  stores
  Workspace
  s. This might seem confusing until you realize that a
  Screen
  is really just a glorified
  Workspace
  , with a little extra information to keep track of which physical screen it is currently being displayed on:

data Screen i l a sid sd = Screen { workspace :: !(Workspace i l a)
                                  , screen :: !sid
                                  , screenDetail :: !sd }
    deriving (Show, Read, Eq)

• A note about those exclamation points, as in
  workspace :: !(Workspace i l a)
  : they are strictness annotations which specify that the fields in question should never contain thunks (unevaluated expressions). This helps ensure that we don't get huge memory blowups with fields whose values aren't needed for a while and lazily accumulate large unevaluated expressions. Such fields could also potentially cause sudden slowdowns, freezing, etc. when their values are finally needed, so the strictness annotations also help ensure that xmonad runs smoothly by spreading out the work.

• The
  floating
  field stores a
  Map
  from windows (type
  a
  ,remember?) to
  RationalRect
  s, which simply store x position, y position, width, and height. Note that floating windows are still stored in a
  Workspace
  in addition to being a key of
  floating
  , which means that floating/sinking a window is a simple matter of inserting/deleting it from
  floating
  , without having to mess with any
  Workspace
  data.

2

StackSet

functions

new :: (Integral s) => l -> [i] -> [sd] -> StackSet i l a s sd
new l wids m | not (null wids) && length m <= length wids = StackSet cur visi unseen M.empty
  where (seen,unseen) = L.splitAt (length m) $ map (\i -> Workspace i l Nothing) wids
        (cur:visi)    = [ Screen i s sd |  (i, s, sd) <- zip3 seen [0..] m ]
                -- now zip up visibles with their screen id
new _ _ _ = abort "non-positive argument to StackSet.new"

but it isn't actually all that bad. In general, if you just take things slowly and break them down piece by piece, you'll probably be surprised how much you understand after all.

workspaces (depending on the number of physical screens), combining

first screen to be current. If the conditions on the guard are not met, it aborts with an error. Since this function will only ever be

just so we can test to make sure it's never called! If this were a function which might be called by users from their xmonad.hs configuration file, aborting would be a huge no-no: by design, xmonad should never crash for any reason (even user stupidity!).

requested workspace so it is now on the current screen even if it was

just switch the focus to whatever screen it happens to be on. For single-head setups, of course, there isn't any difference in behavior

return a new one computed from the old one. This is a common purely functional paradigm: functions which would modify a data structure in an imperative/non-pure paradigm are recast as functions which take an old version of a data structure as input and produce a new version. This might seem horribly inefficient to someone used to a non-pure paradigm, but it actually isn't, for (at least) two reasons. First, a lot of work has gone into memory allocation and garbage collection, so that in a modern functional language such as Haskell, these processes are quite efficient. Second, and more importantly, the fact that Haskell is pure (modifying values is not allowed) means that when a new structure is constructed out of an old one with only a small change, usually the new structure can actually share most of the old one, with new memory being allocated only for the part that changed. In an impure language, this kind of sharing would be a big no-no, since modifying the old value later would suddenly cause the new value to change as well.

3

Workspace

data Workspace i l a = Workspace  { tag :: !i, layout :: l, stack :: Maybe (Stack a) }
    deriving (Show, Read, Eq)

data Workspace i l a = Workspace i l (Maybe (Stack a))

tag :: Workspace i l a -> i

Hence, we have two ways to get at the internals of any value whose type is defined using record syntax: pattern-matching, or accessor functions.

4

Stack

• Creating a new window or deleting the current one would be O(n) operations, as all the windows to the right of the current location would have to be shifted by one in the array.
• In Haskell, indexing into a list is O(n) anyway, and using an array library would be unwieldy here.
• Much work must go into maintaining guarantees such as always having the current index be a valid index into the array, maintaining the ordering of the windows when shifting them around in the array, and so on.

data Stack a = Stack { focus  :: !a        -- focused thing in this set
                     , up     :: [a]       -- clowns to the left
                     , down   :: [a] }     -- jokers to the right
    deriving (Show, Read, Eq)

• A
  Stack a
  cannot be empty, since it must always contain a current element. Remember, the possibility of an empty workspace is handled by the type of
  Workspace
  's
  stack
  field,
  Maybe (Stack a)
  .
• Shifting focus, adding a new window next to the current one, and reversing the window list are all simple O(1) operations.
• There is not even the possibility of any sort of index-out-of-bounds errors while keeping track of the current window.

For more information on zippers, the Zipper page on the Haskell wiki and the chapter on zippers in the Haskell wikibook are good starting places.

5 Other functions

• The functions
  with
  ,
  modify
  , and
  modify'
  are great examples of higher-order functions, functions which take other functions as input. Haskell (and most functional languages) make such a thing easy and natural. For example,
  with
  applies a function to the current workspace's stack;
  modify
  essentially transforms a function on
  Stack
  s to a function on
  StackSet
  s, with some
  Maybe
  types thrown in to handle empty cases.

• The names of the functions
  integrate
  and
  differentiate
  may strike you as odd unless you know that there is an astonishing connection between derivatives (yes, from calculus) and zipper types. In short, finding the zipper of a given data type corresponds to finding a derivative. For more information, see the Haskell wikibook entry on zippers, or the paper by Conor McBride, The Derivative of a Regular Type is its Type of One-Hole Contexts.

• Note how the implementation of functions such as
  focusUp
  /
  Down
  ,
  swapUp
  /
  Down
  , and
  reverseStack
  are quite simple, thanks to higher-order functions and the zipper structure of
  Stack
  s.

• I sort of lied when I said that moving focus is O(1) with the zipper structure: in the one case that focus wraps around the end of the list, it is O(n). But it is still takes O(1) amortized time.

6 QuickCheck properties

These tests are run automatically with every recorded change to the xmonad source repository -- indeed, they must all pass in order for a change to be recorded.