给xbindkeys添加key sequence支持

xbindkeys不支持emacs风格的key sequence,不过由于它可以调用guile来支持scheme的配置文件。xbindkeystarball里有一个配置文件,支持key sequence的特殊形式:两个键的序列。

最近正好学了些scheme,就好好折腾了一把,写了一份配置文件,可以支持任意长的key sequence(当然太长的一般用不到)。

Read More

网络学堂feeds2mail

用网页来看网络学堂的公告很费时间,就打算像 rss2email 那样,把消息制作成邮件。 用 Rubymechanize 来和网站交互,读取“课程公告”和“课程文件”中的消息, 把链接 sha1 后判断是否生成过提示邮件,没有则跟踪链接,用 w3m 输出成纯文本, 生成的邮件用 sendmail 投递。

Read More

八数码

八数码问题,已访问状态采用 factorial number system 表示,未访问的未使用(简化代码) 实现了 Breadth First SearchHeuristic Search 两种算法。 带上命令行选项 -g 能输出 Graphvizdot 格式的状态树。 比较满意的地方是把两种搜索算法的共同部分抽象出来了,写成了单独的 search 函数。

Read More

我的xmonad配置

缺点

  • 依赖的模块较多,升级 ghc 或被 xmonad/xmonad-contrib 依赖的包后需要按照拓扑序更新整个被 xmonad 依赖的树。 如果平时不大升级的就不用在意这一点。
  • 没有 systray 等其他 desktop environment 集成的组件,这方面 tiling window manager 世界中的 Awesome 可谓是佼佼者, 其他 wm 都需要手动配置很多组件,Xmonad 也不例外。

优点

  • Xmonad 用 Haskell 配置,因为这一点注定了当配置复杂到一定程度后,会远远胜过 那些自定义配置语言的 wm。
  • 得到 monad transformer 精髓的 layout transformer 使得复合 layout 变得非常容易, 可以轻易定制出在其他 wm 中不可能实现的 layout。

Read More

Haskell实现的Splay树

三周的军训总算挺过去了,这里的网络条件比想象中要糟糕不少。 其实有很多要说,还是等到“十一长假”回家了再慢慢说吧。

废话不多说了,这是一个用 Haskell 实现的 Top-down Splay tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
module SplayTree (
SplayTree,
splay,
insert,
delete,
empty,
) where

data SplayTree a = Nil | Node a (SplayTree a) (SplayTree a)
deriving (Eq, Show)

splay :: (Ord a) => (a -> Ordering) -> SplayTree a -> SplayTree a
splay comp t = walk t Nil Nil
where
walk Nil _ _ = Nil
walk t@(Node nx l r) lspine rspine =
case comp nx of
LT -> case l of
Nil -> final t lspine rspine
Node nl a b -> if comp nl == LT && a /= Nil then walk a lspine (Node nl rspine (Node nx b r))
else walk l lspine (Node nx rspine r)
GT -> case r of
Nil -> final t lspine rspine

Node nr c d -> if comp nr == GT && d /= Nil then walk d (Node nr (Node nx l c) lspine) rspine
else walk r (Node nx l lspine) rspine
EQ -> final t lspine rspine

final g@(Node x l r) lspine rspine = Node x (lfinal l lspine) (rfinal r rspine)
lfinal l Nil = l
lfinal l (Node y a b) = lfinal (Node y a l) b
rfinal r Nil = r
rfinal r (Node y a b) = rfinal (Node y r b) a

insert :: (Ord a) => a -> SplayTree a -> SplayTree a
insert key Nil = Node key Nil Nil
insert key t =
let t'@(Node nx l r) = splay (compare key) t
in if key < nx then Node key l (Node nx Nil r)
else Node key (Node nx l Nil) r

delete :: (Ord a) => a -> SplayTree a -> SplayTree a
delete key Nil = Nil
delete key t =
let t'@(Node nx l r) = splay (compare key) t
in case compare key nx of
EQ -> if l == Nil then r
else (\(Node nl a _) -> Node nl a r) $ splay (const GT) l
_ -> t'

empty = Nil

-- Test.QuickCheck

prop_insert_delete :: [Int] -> Bool
prop_insert_delete xs = foldr delete (foldr insert empty xs) xs == Nil