Haskell 笔记:data, type, newtype

新类型有自己的 data constructor (literals 可以看成特殊的 data constructor),由这一点来区分是否创建了新类型。

  • data 创建了新类型,可以有多个 data constructor。
  • newtype 创建了新类型,只能有一个 data constructor,同时新类型的内存布局与原来的类型相同。
  • type 没有创建新类型,只是建立了 alias,没有新的 data constructor。

type

常用于语义化类型,是业务逻辑层的概念。

1
2
3
4
5
6
7
8
9
10
11
type ID = Int
a = 1 :: ID
b = a + 2 -- legal
showID :: ID -> IO ()
showID x = print x -- legal, since Int has already been an instance of class Show
-- illegal, since Int has already been instantiated
instance Show ID where
-- ...

newtype

在编译期创建新类型,但差异在运行期被抹去。带有一个构造器。

1
2
3
4
5
6
7
8
9
10
11
12
13
newtype ID' = ID' Int
a = ID' 1
b = a + 2 -- illegal, since Int and ID' are totally different types
showID' :: ID' -> IO ()
showID' x = print x -- illegal, since ID' is not an instance of Show
-- either
showID' (ID' x) = print x
-- or
instance Show ID' where
show (ID' x) = show x

Haskell 笔记:folds

Prelude.foldl

foldl 为 left-associative folding。

1
2
3
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

foldl (+) 0 [1..3] 等价于 (((0 + 1) + 2) + 3)

  • 尾递归,因此有 strict 版本 foldl'
  • 求值时必须先到达栈底,遍历完列表,因此无法处理无穷列表

Data.List.foldl’

foldl'foldl 的 TRO 版本。

Prelude.foldr

foldr 为 right-associative folding。

1
2
3
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

foldr (+) 0 [1..3] 等价于 (0 + (1 + (2 + 3)))

  • 没有尾递归,有爆栈的危险。
  • 有向右展开的特点,而 Haskell 中许多数据结构都有向右递归的特点(如 Cons),因此可以很好地处理无穷递归的数据,从而更加通用。

Prelude.foldl1 && Prelude.foldr1

Helper functions。将 operator 限制为同一种类型,同时约去 accumulator。

1
2
3
4
5
6
7
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = error
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f (x:xs) = foldr f x xs
foldr1 _ [] = error

即,foldr1 将列表的第一个值作为 accumulator,将剩余部分作为 list,传给 foldrfoldl 同理。

实践

用 folds 实现 reverse

1
2
3
4
reversel, reverser :: [a] -> [a]
reversel list = foldl (\acc x -> x : acc) [] list
reverser list = foldr (\x acc -> acc ++ [x]) [] list

用 foldr 实现 foldl

先归纳出 foldr 的泛性质。如果一个函数 g s.t.

1
2
g [] = v
g (x:xs) = f x (g xs)

g list === foldr f v list.

再看 foldl 的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
===>
foldl f v list = g list v
where
g [] v = v
g (x:xs) v = g xs (f v x)
-- 从左到右依次更新 v
===>
foldl f v list = g list v
where
g [] = id
g (x:xs) = \v -> g xs (f v x)

应有 g (x:xs) === k x (g xs),我们计算 k

1
2
3
4
5
6
g (x:xs) === k x (g xs)
g (x:xs) v === k x (g xs) v
g xs (f v x) === k x (g xs) v
(g xs) (f v x) === k x (g xs) v
g' (f v x) === k x g' v
k === \x g' v -> g' (f v x)

所以

1
2
3
4
5
6
foldl f v xs =
(foldr
(\x g' v -> g' (f v x))
id
xs
) v

使用 Aria2 在 Ubuntu 中下载百度云资源

可以实现满带宽下载。

配置 Aria2

Github 下载源码 ./configure && make -j8 && sudo make install

配置 Chrome 插件

clone https://github.com/acgotaku/BaiduExporter

1
2
3
4
5
6
7
$ cd ariac
$ cat > start.sh
> #!/bin/bash
> aria2c --conf=aria2.conf
> ^D
$ chmod +x start.sh
$ ./start.sh

安装 Chrome 插件

打开 chrome://extensionsLoad Unpacked 选择 chrome/release

完成后在百度云页面上会有 导出下载 按钮。


从伪并行的 Python 多线程说起

写在前面

  • 作者电脑 CPU 为 4 核,因此使用 4 个线程测试是合理的
  • 本文使用的 cpython 版本为 3.6.4
  • 本文使用的 pypy 版本为 5.9.0-beta0,兼容 Python 3.5 语法
  • 本文使用的 jython 版本为 2.7.0,兼容 Python 2.7 语法
  • 若无特殊说明,作语言解时,python 指 Python 语言;作解释器解时,pythoncpython

Read More


RMPE 论文读书笔记

论文地址:https://arxiv.org/pdf/1612.00137

Read More


一个 Reentrant Error 引发的对 Python 信号机制的探索和思考

写在前面

前几天工作时遇到了一个匪夷所思的问题。经过几次尝试后问题得以解决,但问题产生的原因却仍令人费解。查找 SO 无果,我决定翻看 Python 的源码。断断续续地研究了几天,终于恍然大悟。撰此文以记。

Read More


Linux 文件权限

概念

Linux 中的每一个文件都有其 所属用户所属用户组,根据这两个属性可将文件访问者分为三类:所属用户自己所属用户组中的用户其他用户,我们可以针对不同的访问者设置不同的用户权限。

“访问”可分为三类:执行。我们可以用 ls -l 命令查看一个文件的权限:

1
2
3
$ touch test
$ ls -l test
-rw-rw-r-- 1 hsfzxjy hsfzxjy 0 Jul 3 23:44 test

首部的 -rw-rw-r-- 即为文件的权限位。权限应该分为四部分来看:-/rw-/rw-/r--。第一部分标志文件的类型,如 普通文件(-)、目录(d)、UNIX 套接字(s)、符号链接(l)、块设备(b)等等。接下来的三个部分依次代表 所属用户所属用户组其他用户 的权限,每部分由三个标志位组成:读标志位写标志位执行标志位

目录的权限

目录是一种特殊的文件,因此也拥有文件权限的概念,但权限的语义与普通文件稍有差异:

  • 读:读取目录下文件列表,相关命令如 ls
  • 写:创建、删除目录下的文件,相关命令如 touch(当文件不存在时)、rm
  • 执行:进入目录,相关命令如 cd

特殊权限

出于某些特殊目的,Linux 中存在两个特殊的权限位:粘滞位(t)、Set Id(s)。这两个权限可以 叠加 在执行权限位上,其中 Set Id 可以置于 所属用户所属用户组 的权限组上,而 粘滞位 只能置于 其他用户 权限组上。当特殊权限被设置时,执行权限位上即会显示 s/t (已有 x 权限)或 S/T (尚未有 x 权限)。

粘滞位

粘滞位的作用是 防止他人误删自己的文件。当某个目录的其他用户权限组有 w 权限时,系统中的其他用户即可随意删除目录中的文件。而一旦叠加上 t 权限,只有文件的所有者方能删除文件。一个经典的例子是 /tmp

1
2
$ ls -l /
drwxrwxrwt 13 root root 12288 Jul 4 00:15 tmp/

Set Id

Linux 中的进程也有自己所属用户与用户组。一般而言,进程的所属用户即为其发起者,但这会引起一些麻烦。一个例子是 passwd 命令,该命令需要修改属于 root 用户的系统文件以保存密码,倘若进程所属用户即为所属者,此功能则无法实现。

Set Id 权限的作用是:在文件被执行时,将其有效用户/用户组设置为文件的用户/用户组,而不是当前执行者。下面是一个演示:

设当前用户为 hsfzxjy,我们在 /tmp 下创建一个 test 文件,并删去其他用户的 r 权限:

1
2
3
4
5
$ cd /tmp
$ echo test text > test
$ chmod o-r test
$ ll test
-rw-rw---- 1 hsfzxjy hsfzxjy 0 Jul 4 00:28 test

由于 test 文件的所属用户是 hsfzxjy,其他用户没有权限读取其中的内容:

1
2
$ sudo -u mysql cat test
cat: test: Permission denied

现在我们修改一下 cat 命令的权限,为了不影响系统文件,我们拷贝一份 cat 副本至当前目录:

1
2
3
4
$ cp /bin/cat .
$ chmod u+s cat
$ ll cat
-rwsr-xr-x 1 hsfzxjy hsfzxjy 52080 Jul 4 00:34 cat*

再以 mysql 的身份执行命令:

1
2
$ sudo -u mysql ./cat test
test text

可见 ./cat 在执行时所属用户是 hsfzxjy。我们可以使用 ps 命令更清楚地看到这点:

1
2
3
4
5
6
7
8
9
10
11
$ sudo -u mysql cat
# 在另一个终端中
$ ps -eo euser,ruser,comm | grep cat
mysql mysql cat
# -----------
$ sudo -u mysql ./cat
# 在另一个终端中
$ ps -eo euser,ruser,comm | grep cat
hsfzxjy mysql cat

HSFZMUN 4.0 部署小记

技术流水账一篇,记录踩过的坑

Channels 异构

Django Channels 官方文档宣称 channels 的最佳配置是使用其自带的服务器组件 Daphne,但在开发中我发现 daphne 处理普通请求比在 WSGI 架构下慢了好几倍,更何况使用 daphne 派发静态文件是十分不切实际的。于是我将 http.requestwebsocket.* 两个 channel 解耦,前者使用 nginx 配合 uwsgi 处理,后者使用 nginx 反向代理至 daphne 处理。这样一来便可充分利用两种架构的优势。

旧架构:

新架构:

Read More


揭秘·变态的平方根倒数算法

神的时代已离去神的故事却化为传说流落凡间供凡人传颂、膜拜

这是什么

在上世纪 90 年代,出现过一款不可思议的游戏——雷神之锤(Quake series)。除了优秀的情节设定和精美的画面,最让人称道的莫过于它的运行效率——要知道在那个计算机配置低下的时代,一段小动画都是一个奇迹,但 Quake 却能流畅地运行于各种配置的电脑上。

直至 2005 年,当 Quake Engine 开源时,Quake 系列的秘密才被揭开。在代码库中,人们发现了许多堪称神来之笔的算法。它们以极其变态的高效率,压榨着计算机的性能,进而才支撑起了 90 年代 3D 游戏的传奇。其中的某些算法,甚至比系统原生的实现还要快!

我们今天的主角——快速平方根倒数算法(Fast Inverse Square Root)就是其中一个。

Read More


神坑·Python 装饰类无限递归

《神坑》系列将会不定期更新一些可遇而不可求的坑防止他人入坑,也防止自己再次入坑

简化版问题

现有两个 View 类:

1
2
3
4
5
6
7
8
9
10
11
class View(object):
def method(self):
# Do something...
pass
class ChildView(View):
def method(self):
# Do something else ...
super(ChildView, self).method()

以及一个用于修饰该类的装饰器函数 register——用于装饰类的装饰器很常见(如 django.contrib.adminregister),通常可极大地减少定义相似类时的工作量:

1
2
3
4
5
6
7
8
9
10
class Mixin(object):
pass
def register(cls):
return type(
'DecoratedView',
(Mixin, cls),
{}
)

这个装饰器为被装饰类附加上一个额外的父类 Mixin,以增添自定义的功能。

完整的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Mixin(object):
pass
def register(cls):
return type(
cls.__name__,
(Mixin, cls),
{}
)
class View(object):
def method(self):
# Do something...
pass
@register
class ChildView(View):
def method(self):
# Do something else ...
super(ChildView, self).method()

看上去似乎没什么问题。然而一旦调用 View().method(),却会报出诡异的 无限递归 错误:

1
2
3
4
5
6
7
8
# ...
File "test.py", line 23, in method
super(ChildView, self).method()
File "test.py", line 23, in method
super(ChildView, self).method()
File "test.py", line 23, in method
super(ChildView, self).method()
RuntimeError: maximum recursion depth exceeded while calling a Python object

【一脸懵逼】

猜想 & 验证

从 Traceback 中可以发现:是 super(ChildView, self).method() 在不停地调用自己——这着实让我吃了一惊,因为 按理说 super 应该沿着继承链查找父类,可为什么在这里 super 神秘地失效了呢?

为了验证 super(...).method 的指向,可以尝试将该语句改为 print(super(ChildView, self).method),并观察结果:

1
<bound method ChildView.method of <__main__.ChildView object at 0xb70fec6c>>

输出表明: method 的指向确实有误,此处本应为 View.method

super 是 python 内置方法,肯定不会出错。那,会不会是 super 的参数有误呢?

super 的签名为 super(cls, instance),宏观效果为 遍历 cls 的继承链查找父类方法,并以 instance 作为 self 进行调用。如今查找结果有误,说明 继承链是错误的,因而极有可能是 cls 出错。

因此,有必要探测一下 ChildView 的指向。在 method 中加上一句: print(ChildView)

1
<class '__main__.DecoratedView'>

原来,作用域中的 ChildView 已经被改变了。

真相

一切都源于装饰器语法糖。我们回忆一下装饰器的等价语法:

1
2
3
@decorator
class Class:
pass

等价于

1
2
3
4
class Class:
pass
Class = decorator(Class)

这说明:装饰器会更改该作用域内被装饰名称的指向

这本来没什么,但和 super 一起使用时却会出问题。通常情况下我们会将本类的名称传给 super(在这里为 ChildView),而本类名称和装饰器语法存在于同一作用域中,从而在装饰时被一同修改了(在本例中指向了子类 DecoratedView),进而使 super(...).method 指向了 DecoratedView 的最近祖先也就是 ChildView 自身的 method 方法,导致递归调用。

解决方案

找到了病因,就不难想到解决方法了。核心思路就是:不要更改被装饰名称的引用

如果你只是想在内部使用装饰后的新类,可以在装饰器方法中使用 DecoratedView,而在装饰器返回时 return cls,以保持引用不变:

1
2
3
4
5
6
7
8
9
10
11
def register(cls):
decorated = type(
'DecoratedView',
(Mixin, cls),
{}
)
# Do something with decorated
return cls

这种方法的缺点是:从外部无法使用 ChildView.another_method 调用 Mixin 上的方法。可如果真的有这样的需求,可以采用另一个解决方案:

1
2
3
4
def register(cls):
cls.another_method = Mixin.another_method
return cls

即通过赋值的方式为 cls 添加 Mixin 上的新方法,缺点是较为繁琐。

两种方法各有利弊,要根据实际场景权衡使用。