Hey all. Back from vacation, with a shiny new xmonad StackSet implementation based on a 'zipper'. The benefit: 50 lines less code (particularly, Operations.hs gets simpler by far) tracks focus automatically by design (no delete-transient focus-lost bug) I'll have a rather long blog article on the zipper type tomorrow. Spencer, can you have a look. I'd like to merge this in. Needs some merging with the changes during the last week. http://www.cse.unsw.edu.au/~dons/code/xmonad/StackSet.hs http://www.cse.unsw.edu.au/~dons/code/xmonad/Operations.hs -- Don
Hi And once again, firing Catch (google:catch haskell) off on this code: * new calls error, not a big surprise that this makes it incomplete * view also calls error * swap calls tail, which isn't safe unless you know some seriously deep stuff about index, and keep a detailed mapping between elements. The basic problem is that Catch can't know that successive calls to Map.lookup with the same key give the same results. You can probably eliminate this by only performing one lookup, which is also faster. * delete and focusWindow both call focus, which is incomplete. Both feature very similar code, and could do with abstracting out. The basic pattern is: focus (stack (current s)) which is unsafe - since stack may return Empty, for which focus is incomplete. * new relies on the Integral type having sensible semantics, if you pass Int or Integer its fine (machine checked), but if you create a crazy type, make it an instance of Integral then [0..n-1] may generate no elements, and your (h:t) match will fail. All the rest of the program is safe, including the partial 'with' function, as specifically annotated by dons to check. Thanks Neil
ndmitchell:
Hi
And once again, firing Catch (google:catch haskell) off on this code:
* new calls error, not a big surprise that this makes it incomplete
* view also calls error
* swap calls tail, which isn't safe unless you know some seriously deep stuff about index, and keep a detailed mapping between elements. The basic problem is that Catch can't know that successive calls to Map.lookup with the same key give the same results. You can probably eliminate this by only performing one lookup, which is also faster.
Good suggestion.
* delete and focusWindow both call focus, which is incomplete. Both feature very similar code, and could do with abstracting out. The basic pattern is:
focus (stack (current s))
which is unsafe - since stack may return Empty, for which focus is incomplete.
A bug! Well spotted.
* new relies on the Integral type having sensible semantics, if you pass Int or Integer its fine (machine checked), but if you create a crazy type, make it an instance of Integral then [0..n-1] may generate no elements, and your (h:t) match will fail.
Tricky.
All the rest of the program is safe, including the partial 'with' function, as specifically annotated by dons to check.
Very good Neil, thanks! I've written up the idea behind implementing xmonad as a zipper-based data structure which tracks focus for us here, http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17#xmonad_part1b_zipper For those wondering how the new StackSet data type will work. The plan is to merge in my zipper branch in the next few days. -- Don
On Thu, May 17, 2007 at 02:19:03PM +1000, Donald Bruce Stewart wrote:
I've written up the idea behind implementing xmonad as a zipper-based data structure which tracks focus for us here,
http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17#xmonad_part1b_zipper
For those wondering how the new StackSet data type will work. The plan is to merge in my zipper branch in the next few days.
I have a few comments. First and foremost: it seems that your zipper idea is taking a change in the user interface, and expressing it in the data structure. Wouldn't it make more sense to first have the discussion of what user interface is desired, and then implement it afterwards? Or did this discussion already occur on IRC, and everyone agreed that they didn't like the focus-stack behavior? Personally, I prefer the idea of a focus stack, but will concur that your non-stack approach isn't much worse. And the data structure is certainly beautiful--except that it presumes that there exists a fixed layout based on order of windows, which I don't prefer as a UI. But I understand that most of you do. (totally different--related--topic...) The dynamical number of workspaces is one of the reasons I like ion3--and it's something your current code change would remove from xmonad. It's not advertised, but the number of workspaces is fixed in xmonad only because of the default choice of key bindings, and I like that. I certainly have been using a dynamical set of workspaces via emulation (and someone else is doing the same, see FindEmptyWorkspace). And actually, I have just one idea specific to your suggested API: new :: Int -> StackSet a new n | n > 0 = StackSet t [] rs where (t:rs) = [ Workspace i Empty | i <- [0 ..n-1]] Why not make this empty :: StackSet i a insertWorkspace :: StackSet i a -> StackSet i a -- insertWorkspace sets the focus on the new workspace, and works like -- insert does on windows, obeying the same properties. deleteWorkspace :: i -> StackSet i a -> StackSet i a This gives us control of workspaces if we choose, and costs you nothing. For those of us who like RotView, and FindEmptyWorkspace, we'd get these behaviors for free, and those who prefer to have a fixed number of (possibly empty) workspaces, they could have that for free also. And of course, new n = foldr (const insertWorkspace) empty [1..n] I'd also vote for removing the tag :: Int from the Workspace. It only costs O(N) to count workspaces to get to the Nth one, and N in general is a small number. And the common operations are all O(1) since they access the first workspace. The behavior wouldn't be affected, except that insertWorkspace could change the numbering scheme. But, I don't see that as a real problem. You currently don't have an API for insertWorkspace, and I expect that those who use it will easily adapt to the idea that it works the same as windows. -- David Roundy http://www.darcs.net
On Thu, 2007-05-17 at 05:24 -0700, David Roundy wrote:
First and foremost: it seems that your zipper idea is taking a change in the user interface, and expressing it in the data structure. Wouldn't it make more sense to first have the discussion of what user interface is desired, and then implement it afterwards? Or did this discussion already occur on IRC, and everyone agreed that they didn't like the focus-stack behavior?
Personally, I prefer the idea of a focus stack, but will concur that your non-stack approach isn't much worse. And the data structure is certainly beautiful--except that it presumes that there exists a fixed layout based on order of windows, which I don't prefer as a UI. But I understand that most of you do.
Just to touch on this - the subject did come up on IRC. It shouldn't be
difficult to separate the focus and layout again by adding a layout list
while keeping the focus zipper. It should even be simpler for some tasks
such as adding new windows to the master position. But it is extra
book-keeping and it seems most users prefer focus order = layout order
for tiling mode.
--
Robert Marlow
droundy:
On Thu, May 17, 2007 at 02:19:03PM +1000, Donald Bruce Stewart wrote:
I've written up the idea behind implementing xmonad as a zipper-based data structure which tracks focus for us here,
http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17#xmonad_part1b_zipper
For those wondering how the new StackSet data type will work. The plan is to merge in my zipper branch in the next few days.
I have a few comments.
First and foremost: it seems that your zipper idea is taking a change in the user interface, and expressing it in the data structure. Wouldn't it make more sense to first have the discussion of what user interface is desired, and then implement it afterwards? Or did this discussion already occur on IRC, and everyone agreed that they didn't like the focus-stack behavior?
Right, its an attempt to implement the delete . insert == id model of focus behaviour, which is the alternative to the focus stack model. I promised to go off an implement this when we talked about the focus stack idea, on irc, I think. So this is a behaviour change from the focus stack code comitted while I was away. I prefer it, since it is much simpler to understand the focus movement behaviour, which fits with out goals of full predictability of each operation. Surely focus stack handling is an elaboration that could be achieved via a contrib module?
Personally, I prefer the idea of a focus stack, but will concur that your non-stack approach isn't much worse. And the data structure is certainly beautiful--except that it presumes that there exists a fixed layout based on order of windows, which I don't prefer as a UI. But I understand that most of you do.
Or more that it tries to return the same window list as the current implmentation, while tracking focus in a more obvious manner. A focus tracking workspace is just the one-hole context of a stack, after all! :-)
(totally different--related--topic...)
The dynamical number of workspaces is one of the reasons I like ion3--and it's something your current code change would remove from xmonad. It's not advertised, but the number of workspaces is fixed in xmonad only because of the default choice of key bindings, and I like that. I certainly have been using a dynamical set of workspaces via emulation (and someone else is doing the same, see FindEmptyWorkspace).
Now this is interesting, and I see no obvious reason not to do this.
And actually, I have just one idea specific to your suggested API:
new :: Int -> StackSet a new n | n > 0 = StackSet t [] rs where (t:rs) = [ Workspace i Empty | i <- [0 ..n-1]]
Why not make this
empty :: StackSet i a insertWorkspace :: StackSet i a -> StackSet i a -- insertWorkspace sets the focus on the new workspace, and works like -- insert does on windows, obeying the same properties. deleteWorkspace :: i -> StackSet i a -> StackSet i a
This gives us control of workspaces if we choose, and costs you nothing. For those of us who like RotView, and FindEmptyWorkspace, we'd get these behaviors for free, and those who prefer to have a fixed number of (possibly empty) workspaces, they could have that for free also.
And of course,
new n = foldr (const insertWorkspace) empty [1..n]
I'd also vote for removing the tag :: Int from the Workspace. It only costs O(N) to count workspaces to get to the Nth one, and N in general is a small number. And the common operations are all O(1) since they access the first workspace. The behavior wouldn't be affected, except that
Yes, that's true. We could avoid the tag -- its not terribly useful. Its been pointed out that the 'master' tag is also not required, since the 'integration' (idea from Conor's zipper paper :-) of the Stack cursor gives us the list with master at the top anyway.
insertWorkspace could change the numbering scheme. But, I don't see that as a real problem. You currently don't have an API for insertWorkspace, and I expect that those who use it will easily adapt to the idea that it works the same as windows.
Yes, I think we can look at this next. -- Don
Hi
* new relies on the Integral type having sensible semantics, if you pass Int or Integer its fine (machine checked), but if you create a crazy type, make it an instance of Integral then [0..n-1] may generate no elements, and your (h:t) match will fail.
Tricky.
You can fix this with: where (h:ts) = Workspace 0 Empty : [ Workspace i Empty | i <- [1 ..n-1]] or: new n m | n > 0 && m > 0 = StackSet n (Workspace 0 Empty) [] ts xine where ts = [ Workspace i Empty | i <- [1 ..n-1]] Either one will guarantee safety. Of course, you can just have Catch check this property only on Int - however you no longer have a proof that XMonad is safe - depends how important that "verified by Catch" button is (button coming soon!). Thanks Neil
ndmitchell:
Hi
* new relies on the Integral type having sensible semantics, if you pass Int or Integer its fine (machine checked), but if you create a crazy type, make it an instance of Integral then [0..n-1] may generate no elements, and your (h:t) match will fail.
Tricky.
You can fix this with:
where (h:ts) = Workspace 0 Empty : [ Workspace i Empty | i <- [1 ..n-1]]
Yep. I was referring more to the fact that funny instances can lead to funny enumFromTos. instances can be evil! -- Don
participants (4)
-
David Roundy -
dons＠cse.unsw.edu.au -
Neil Mitchell -
Robert Marlow