4
26
2015
2

发布两个编译好的 Haskell 程序(Arch Linux 64 位版本)

Haskell 程序一向编译起来费力,得先下个巨大的 GHC,然后从 Hackage 上下一堆包然后慢慢编译。所以我在这里把自己用的程序放出来。Arch Linux 的 Haskell 程序打包太复杂了,所以不打包了。连二进制包也懒得打。

这两个程序是 shellcheckcgrep

shellcheck 是一个 bash / POSIX sh 脚本 lint 工具。就是指出程序源码中可能出错的地方,相当于 jshint 之于 JavaScript、pylint 之于 Python(但是不含风格检查)、gcc / clang 的警告之于 C。

cgrep 就是 context-aware grep,比如搜索注释或者字符串里的东西之类的。支持解析几种编程语言。

程序是在 Arch Linux 上编译的,但其它 Linux 也许也可以使用。

下载地址:shellcheck-0.3.7.xz, cgrep-6.4.12.xz.

>>> sha1sum cgrep-6.4.12.xz shellcheck-0.3.7.xz
0588ee29a1a17c1cddc816a8193d8494db7c03cf  cgrep-6.4.12.xz
376b58d485603a7622f83f095a30bddc1da34376  shellcheck-0.3.7.xz
Category: Haskell | Tags: Haskell 下载
1
6
2015
41

众编程语言间的 swapview 之战

swapview 起源于我很早之前看到的一个 shell 脚本。当时正在学习 Haskell,所以就拿 Haskell 给实现了一遍。为了对比,又拿 Python 给实现了一遍。而如今,我又在学习另一门新的语言——Rust,也拿 swapview 来练习了。相比仅仅输出字符串的「Hello World」程序,swapview 无疑更实际一些:

  • 文件系统操作:包括列目录、读取文件内容
  • 数据解析:包括简单的字符串处理和解析,还有格式化输出
  • 数据处理:求和啊排序什么的
  • 流程控制:循环啊判断啊分支什么的都有
  • 错误处理:要忽略文件读取错误的

因此,swapview 成为了依云版的「Hello World」:-)

感谢所有给 swapview 提交代码的朋友们

本文只是借 swapview 这个程序,一窥众编程语言的某些特征。很显然,编程语言们各有所长,在不同的任务下会有不同的表现。而且 swapview 各个版本出自不同的人之手,代码质量也会有所差异。

闪耀!那些令人眼前一亮的语言们

从运行效率上来看,C 如预期的一样是最快的。但令人惊讶的是,由我这个 Rust 初学者写的 Rust 程序竟然紧随其后,超越了 C++。

而原以为会跟在 Rust 之后的 C++,却输给了作为脚本语言存在的 Lua 语言的高效实现 LuaJIT(与 Rust 版本相当)。而且非 JIT 版本的 Lua 5.1 和 5.2 也都挺快的。Lua 这语言自带的功能非常少,语法也简单,但是效率确实高,让人又爱又恨的。

失望!那些没预期中的高效的语言们

没想到 Python 2 也挺快的,很接近 Go 了。PyPy 大概是因为启动比较慢的原因而排在了后面。Python 3 有使用两个版本的代码,Python3_bytes 把文件读取改为使用 bytes,仅在需要的时候才解码成 str。仅此之差,运行速度快了10%。可见 Python 的 Unicode 处理十分耗时,难怪 Python 3 在各种测试中都比 Python 2 要慢上一截。至于 PyPy3,怎么跑到那么靠后的地方去了呢……

Go 很快。至少比 Python 快。但也仅此而已了,不仅比 C++ 慢,甚至连 Lua(非 JIT 版)都不如。Go 语言版本虽然不是我写的,但我看过代码,感觉很原始。至少比 Lua 原始。看起来 Go 只不过是带接口和并发支持的 C 而已。而且,作为静态类型的编译型语言,却我却有一种很不放心的感觉。大约是因为我改动时发现传给 fmt.Printf 的参数类型和数目错了都不会得到警告或者错误的原因。而且我从来没见过 Go 编译时出现警告,对于还没入门的初学者写的、改过的程序,这样子不科学啊。早期我倒是见过 Go 报错了,但那只不过是编译器还不完善的表现而已。

传闻 NodeJS 很快。但至少它在 swapview 这种脚本中没能体现出来。正常版本比 Python 3 还要慢一点。而使用异步啊并行什么的版本还要慢上差不多三分之一,不知道怎么搞的。

编译型的 Chicken、OCaml、Haskell 都排在了一众脚本语言后边,虽然很可能是对语言本身不熟导致写出来的程序比较慢,但还是挺令人失望的。经过高手优化的 Haskell2 版本效率接近于 Python 3,但也到此为止了(因为不想使用 cabal 安装依赖,所以 Haskell2 没有参与这场对决)。我曾见过有人把 Haskell 代码优化到比 C 还快,但我宁愿去看汇编也不要去读那种代码……

Lisp 系(Chicken、Racket、SBCL(标注为 CommonLisp 的项)、Guile)也都挺慢的。不知道 LispWorks 之类的会不会快一大截呢。

预料之中的以及结果截图

Ruby 比 Python 略慢一点。

Java、Elixir 比较靠后。没办法,它们启动慢。也许以后我会出不考虑启动时间的版本。

以下是本文发表前的测试结果截图。其中 Erlang 版本因为有问题被信号所杀所以被扔在了最后。

测试结果截图

测试使用的是benchmark子目录中的 Rust 程序,使用cargo build --release命令即可构建。另外也可以使用 farseerfc 的 Python 脚本。

代码量

Elixir 代码量挺少的。Python、Ruby 也挺不错。Java 版本竟然跟 Haskell 一样。不管是 JavaScript 还是 CoffeeScript 都比较长,比 Java 还长。Rust 比 Python 长不少,但也比 Go 短不少。而 Go 比起 C、C++ 要短一些。最长的,除了我不了解的 Pascal,竟然还有因为程序出错还没有测试的 Erlang!如果不算按行读取的 line_server.erl 的放大,只有不到一百行,倒还不算多。

                  Elixir:   50
                   Julia:   51
           Python3_bytes:   53
                  Python:   56
                    Ruby:   56
                  Racket:   58
                    Bash:   63
                   OCaml:   65
          CommonLisp_old:   67
          CommonLisp_opt:   67
           Bash_parallel:   69
             C++14_boost:   69
                   Guile:   70
                 Haskell:   73
                 Chicken:   75
                    Java:   75
                  NodeJS:   76
                    Vala:   78
                Haskell2:   81
                       D:   86
                    Rust:   88
                   C++14:   89
                  CSharp:   91
                     Lua:   91
            NodeJS_async:   93
            CoffeeScript:   93
   CoffeeScript_parallel:   95
                     PHP:   97
           Rust_parallel:   98
                      Go:  103
                   C++11:  128
                   C++98:  141
                       C:  149
              FreePascal:  185
                  Erlang:  232

编译速度

这个比较非常粗糙,比如联网下载依赖也被算进去了。不过可以肯定,不算下载依赖部分的话,Rust 是最慢的!其次是 Haskell。标榜编译速度非常快的 Go 并不是最快的,和 C++ 不相上下(当然不知道代码复杂之后会如何了)。

0.36 C
0.60 FreePascal
0.80 OCaml
0.83 CoffeeScript_parallel
1.48 CSharp
1.67 Vala
1.68 Erlang
2.13 NodeJS_async
2.27 C++14
2.49 Go
2.53 CoffeeScript
2.90 C++11
3.01 C++98
3.23 Java
3.52 Racket
3.98 NodeJS
6.05 CommonLisp_opt
7.07 D
9.01 C++14_boost
10.41 Haskell
13.07 Rust
14.74 Chicken
15.37 Rust_parallel

结语

这个项目最初只是练习而已。后来不同语言的版本有点多,于是才演变成众编程语言的竞技。也就随意地测试了一下在给定需求下不同语言的表现而已。其实比较有意思的部分,一是使用正在学习的编程语言写作程序的新奇感、新知、新的领悟(这也是我的测试程序使用 Rust 编写的原因),二是对比不同编程语言的风格和对同样需求的处理方式。

各位读者对 swapview 有任何补充和改进,欢迎贡献代码哦~项目地址:https://github.com/lilydjwg/swapview

更新区

2015年1月9日更新:又收到了不少版本和改进,以下是最新的测试结果。很不幸地,现在已经跑得很快的 Erlang 在测试中又没反应被杀掉了。并行版的 Rust 的结果很不稳定,这次跑得好快!C++ 的除了 C++98 版的之外都到 Rust 前边去了。PHP 竟然比 LuaJIT 还要快!D 怎么到 PyPy 后边去了。

2015年1月9日的测试结果截图

2015年1月10日更新:C++ 版本继续改进,好多都超越 C 了,Rust 1.0.0alpha 的并列版本又快又稳定,Erlang 版本终于跑完了全部测试而没有出事,LLVM 版 D 快了好多。

2015年1月10日的测试结果截图

2015年1月18日更新:继续更新。又添加了若干语言,不过期待中的 Nim、Zimbu 以及传统脚本语言 Perl、Tcl 依旧缺席中。另外,正文也进行了更新,重新计算了代码量,添加了编译速度的粗略比较。

2015年1月18日的测试结果截图

12
24
2014
39

Rust 初体验(真快!)

最近又看到 Rust 的相关东西了,入门指南也写得挺不错的。这语言我越看越喜欢。

Rust 的目标是系统级编程,就像 C 那样,快速高效。同时它继承了 Haskell 的诸多特性,包括其类型系统(包括类型类和类型推断)、模式匹配。而读写起来,又和 Python 差不多简单明了。简直是把这三种语言的优点全学到了!(当然 Rust 不仅仅受到了这几种语言的影响啦。)

当然,要体验一门编程语言,最好的方式就是使用它。于是我拿它实现了我最开始用来练习 Haskell 用的 swapview 程序。

swapview 的功能是,读取/proc下每一个进程目录下边的cmdlinesmaps文件,得到其命令行和 swap 使用量,然后排序、格式化,并打印出来。

Haskell 第一版实现挺慢的:

swapview  1.27s user 0.26s system 98% cpu 1.555 total

我随手写了个 Python 版,效率翻了一倍还要多!很令人惊讶的呢。作为解释执行、还一直被认为很慢的 Python 竟然在没有任何优化的情况下就超过了编译型的 Haskell:

swapview.py  0.35s user 0.18s system 97% cpu 0.548 total

后来在 IRC 上遇到一位懂行的人,用了不少手段优化,最终得到了 Haskell 第二版:

swapview2  0.42s user 0.15s system 98% cpu 0.583 total

比 Python 版略慢。

才学 Rust 没几天,我对 Rust 比对 Haskell 更不熟。花了不少时间查阅文档、调整代码。不过因为之前的 Haskell 基础,也没遇到太大的困难。结果如下:

swapview  1.84s user 0.15s system 97% cpu 2.038 total

呃呃呃,怎么比 Haskell 版本还要慢上不少啊?

本来是找 profiling 方法的。翻着 rustc 的 man 文档,看到了-O选项,眼前一亮——我忘记告诉编译器要优化了!这是启用优化的结果,比 Python 版又快了一倍:

swapview  0.10s user 0.13s system 96% cpu 0.237 total

真棒呢~

不过很遗憾的是,它的格式化函数的第一个参数必须是字面量,连常量都不行。因为那是个宏,要在编译期解析格式……另外似乎也不支持现在连 JavaScript 都已经支持了的 generator(只支持 iterator,得先写一个 struct 才能用)。

PS: Rust 的文档挺赞的,和 Python 的一样有 JavaScript 实现的搜索功能,比起 Nimrod 和 Zimbu 的好用太多了。

PPS: 谁有兴趣可以贡献个 Go 版、C 版、C++ 版、LuaJIT 版什么的=w=


2014年12月25日更新:目前的结果是(运行时间):Rust < LuaJIT < C++14 (gcc 4.9.2) < Lua 5.1 / 5.2 << Python 3 < Haskell <<< OCaml < SBCL。手动测试的。有空我再写个好点的自动测试程序。

2015年1月6日更新:添加了更多的编程语言,以及更准确的运行时间测试,请见新文章编程语言对决——战场:swapview

Category: 编程 | Tags: Haskell 编程语言 Rust
10
24
2012
33

欧拉项目第14题,Haskell 和 Erlang 等语言版

看到别人的 Racket 版,心里痒痒,写了个 Haskell 版。只用了尾递归,没用什么高级特性。题目地址。

calc3xp1 :: Int -> Int
calc3xp1 n | even n = n `div` 2
           | otherwise = 3 * n + 1

countlen :: Int -> Int
countlen = countlen_tail 0

countlen_tail :: Int -> Int -> Int
countlen_tail c n | n == 1 = c
                  | otherwise = countlen_tail (c+1) $ calc3xp1 n

findmax :: Int -> Int
findmax = findmax_tail 1 1 1

findmax_tail max maxn n final | n >= final = maxn
                              | otherwise = if new_len > max
                                               then findmax_tail new_len n n' final
                                               else findmax_tail max maxn n' final
                                             where new_len = countlen n
                                                   n' = n + 1

main = print $ findmax 1000000
>>> time ./3xp1
./3xp1  14.92s user 0.02s system 99% cpu 14.955 total

Erlang 版本直接照抄 Haskell 版:

-module(e3xp1).
-export([main/1]).

calc3xp1(N) when N rem 2 == 0 ->
  N div 2;
calc3xp1(N) ->
  3 * N + 1.

countlen(N) -> countlen_tail(0, N).

countlen_tail(C, 1) ->
  C;
countlen_tail(C, N) ->
  countlen_tail(C+1, calc3xp1(N)).

findmax(N) ->
  findmax_tail(1, 1, 1, N).

findmax_tail(_, Maxn, N, Final) when N >= Final ->
  Maxn;
findmax_tail(Max, Maxn, N, Final) ->
  Newlen = countlen(N),
  if Newlen > Max -> findmax_tail(Newlen, N, N+1, Final);
    true -> findmax_tail(Max, Maxn, N+1, Final)
  end.

main(_) ->
  io:format("~B~n", [findmax(1000000)]).

它在六分钟后还没能输出结果……

>>> time escript e3xp1.erl
^C
escript e3xp1.erl  374.55s user 0.94s system 99% cpu 6:15.76 total

Racket 版在同一机器上用时:

>>> time racket 3xp1.racket
racket 3xp1.racket  3.22s user 0.22s system 99% cpu 3.448 total

这是为什么呢?

PS: C 更快,不到半秒就搞定了……

更新:又试了试 Lua 版本的,和 Haskell 版速度相当。但是——LuaJIT 竟然只 2.4s 出结果,因为换了机器,所以实际上它应该比 Racket 版快一倍以上。

再次更新:Erlang 版编译后还是挺快的:

>>> erlc e3xp1.erl
>>> time erl -noshell -s e3xp1 main -s init stop
erl -noshell -s e3xp1 main -s init stop  5.59s user 0.01s system 84% cpu 6.608 total

不过,它什么事都不干启动后立即停止也花了一秒多,比 Java 更厉害:

>>> time erl -noshell -s init stop
erl -noshell -s init stop  0.06s user 0.01s system 6% cpu 1.077 total

2014年12月24日更新:Rust 版也非常快,而且写起来舒服:

fn calc3xpi(n: uint) -> uint {
    if n % 2 == 0 {
        n / 2
    } else {
        3 * n + 1
    }
}

fn countlen(&n: &uint) -> uint {
    let mut c = 0;
    let mut x = n;
    while x != 1 {
        c += 1;
        x = calc3xpi(x);
    }
    c
}

fn findmax(n: uint) -> uint {
    range(1, n).max_by(countlen).unwrap()
}

fn main(){
    let mut stdout = std::io::stdout();
    stdout.write_uint(findmax(1000000));
    stdout.write_char('\n');
}
4
18
2012
5

Haskell 实战:惰性地读取子进程输出

突然想给 locate 命令写个 wrapper,把输出中的家目录和一些因加密而引入的软链接显示为~。自然,这需要读取 locate 命令的输出。在 process 这个库中看到了readProcess函数,似乎是自己想要的(完整代码):

readLocate :: [String] -> IO String
readLocate args = getArgs >>= \cmd ->
  let args' = args ++ cmd
  in readProcess "locate" args' ""

结果却发现,原本 locate 命令是边查找边输出的,现在变成了先静默,然后一下子全部吐出来。没有按 Haskell 惯常的「懒惰」脾气来。这样一来,当我发现输出项目太多想按Ctrl-C中断时已经晚了。

Google 了一下,找到这个

I guess people who want laziness can implement it themselves directly, taking care to get whatever laziness it is that they want.

好吧。我先下回 process 库的源码看看readProcess为什么不是惰性的:

readProcess 
    :: FilePath                 -- ^ command to run
    -> [String]                 -- ^ any arguments
    -> String                   -- ^ standard input
    -> IO String                -- ^ stdout
readProcess cmd args input = do
    (Just inh, Just outh, _, pid) <-
        createProcess (proc cmd args){ std_in  = CreatePipe,
                                       std_out = CreatePipe,
                                       std_err = Inherit }

    -- fork off a thread to start consuming the output
    output  <- hGetContents outh
    outMVar <- newEmptyMVar
    _ <- forkIO $ C.evaluate (length output) >> putMVar outMVar ()

    -- now write and flush any input
    when (not (null input)) $ do hPutStr inh input; hFlush inh
    hClose inh -- done with stdin

    -- wait on the output
    takeMVar outMVar
    hClose outh

    -- wait on the process
    ex <- waitForProcess pid

    case ex of
     ExitSuccess   -> return output
     ExitFailure r -> 
      ioError (mkIOError OtherError ("readProcess: " ++ cmd ++ 
                                     ' ':unwords (map show args) ++ 
                                     " (exit " ++ show r ++ ")")
                                 Nothing Nothing)

原来是另开了一 IO 线程读输出,然后等待进程结束后关闭管道。这解释为什么它不是惰性的——它得进程善后处理。

那好吧,改用createProcess好了:

doLocate :: IO (String, ProcessHandle)
doLocate = do
  argv0 <- getProgName
  let args = case argv0 of
                  "lre" -> ["-b", "--regex"]
                  _ -> []
  args' <- getArgs
  let args'' = args ++ args'
  (_, Just out, _, p) <- createProcess (proc "locate" args''){ std_in = Inherit,
                                                               std_out = CreatePipe,
                                                               std_err = Inherit }
  hSetBuffering out LineBuffering
  (,) <$> hGetContents out <*> return p

改进后的程序,不会等待进程结束,而是返回输出和进程句柄。进程句柄用来等待子进程结束,同时获取退出状态。至于那个管道就不关闭了,留给操作系统解决好了。

main = do
  (out, p) <- doLocate
  putStr $ transform out
  waitForProcess p >>= exitWith

改进版的完整程序在此

Category: Haskell | Tags: Haskell linux
3
2
2012
6

在 fcitx 中切换国标与传统引号

国家标准使用这些引号:‘’“”,而我发现传统中文的引号更漂亮:「」『』。我切换到传统引号已经有一段时间了,但最近发现有时还是需要使用国标引号,而 fcitx 的现任开发者认为不需要加入该切换功能。好在 fcitx 的配置文件都是文本,又有 fcitx-remote 工具,所以自己很容易地手动实现了两个版本的——Haskell 版本纯粹是练习用,因为没有扩展路径中的~的现成函数,所以只好自己找了个实现,代码有些长。

import Control.Applicative ((<$>))
import System.Cmd (rawSystem)
import System.Directory (getHomeDirectory)
import System.Posix.User
import qualified Data.Text as T
import qualified Data.Text.IO as TIO

main = do
  file <- getFile
  TIO.readFile file >>= (TIO.writeFile file) . (T.map (trChar "“”‘’『』「」" "『』「」“”‘’"))
  reloadFcitx

getFile :: IO FilePath
getFile = expandUser "~/.config/fcitx/data/punc.mb.zh_CN"

reloadFcitx :: IO ()
reloadFcitx = rawSystem "fcitx-remote" ["fcitx-remote", "-r"] >> return ()

expandUser :: FilePath -> IO FilePath
expandUser "~"         = getHomeDirectory
expandUser ('~':'/':p) = fmap (++ "/" ++ p) getHomeDirectory
expandUser ('~':up)    = let (u, p) = break (== '/') up
                             in fmap (++ tail p) (homeDirectory <$> getUserEntryForName u)
expandUser p           = return p

trChar :: [Char] -> [Char] -> Char -> Char
trChar from to ch = case i of
                         Just i -> to !! i
                         _      -> ch
                         where i = elemIndex ch from

Python 版本就很简洁了:

#!/usr/bin/env python3
# vim:fileencoding=utf-8

import os

m = str.maketrans('“”‘’『』「」', '『』「」“”‘’')
file = os.path.expanduser("~/.config/fcitx/data/punc.mb.zh_CN")

c = open(file).read().translate(m)
open(file, 'w').write(c)
os.execvp('fcitx-remote', ['fcitx-remote', '-r'])
Category: Linux | Tags: fcitx Haskell python
2
17
2012
5

Haskell 实战:使用 Parsec 解析 lrc 歌词文件

既然来学 Haskell 了,Parsec 不应该错过。lrc 文件的格式大家应该都清楚。虽然说它用正则表达式解析很容易也很可靠,但是,我这不是练习么!

数据类型的定义

首先,我们想想歌词文件解析出来有些什么。主要数据当然是一条条带时间的歌词!除此之外,还会可选地有歌名啦歌手啦之类的东西。

先来定义一条歌词,也就是一个最高精确到百分之一秒的时间,和一个字符串。也就是:

data LrcLine = LrcLine {
  time :: Int,
  line :: String
} deriving (Eq, Show, Ord)

我们需要实现Ord类型类以便比较,因为 lrc 文件的歌词有一种紧凑的格式,在相同的歌词前有多个时间。这时,歌词就不是排好序的了。GHC 会自动推断出比较函数,也就是逐个域地进行比较。也可以手动定义其为Ord的实例:

-- import Data.Function (on)
instance Ord LrcLine where
  compare = compare `on` time

然后是整个歌词文件的信息:

data Lrc = Lrc {
  title :: Maybe String,
  artist :: Maybe String,
  album :: Maybe String,
  by :: Maybe String,
  metadata :: [(String, String)],
  lyrics :: [LrcLine]
}

因为可能会有未知的元信息,所以我们定义了一个metadata域来存储之。其类型为[(String, String)],以便使用lookup函数进行查询。

自顶向下设计解析器:顶层解析器

RWH的说明,似乎一般都不写解析器的类型签名。但既然是初学嘛,我还是写上好了——

lrcParser :: GenParser Char st Lrc

什么意思我还不太懂,不过最后那个Lrc很显然就是解析结果的类型啦。

我们的解析器先从歌词源文件中读取若干行的元信息,接下来读取所有的歌词数据,最后构造个 Lrc类型的数据。

lrcParser = do
  metadata <- many $ try lrcMeta
  ly <- concat <$> many lrcLine
  return Lrc {
    title = lookup "ti" metadata,
    artist = lookup "ar" metadata,
    album = lookup "al" metadata,
    by = lookup "by" metadata,
    metadata = metadata,
    lyrics = sort ly
  }

manytry都是 Parsec 里的函数。many接受一个类型为解析器的参数,在求值时它一直调用这个解析器,直到它不消耗输入为止。如果这个解析器消耗了输入却又没能成功,那么整个many解析器也就失败了。而try在消耗了任意数量的输入但没有最终成功时会把已消耗的输入退回去,结果是没有消耗输入。开个 GHCi 会话演示下:

>>> ghci
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
ghci> import Text.ParserCombinators.Parsec
ghci> let p = string "ab" :: GenParser Char st String
Loading package transformers-0.2.2.0 ... linking ... done.
Loading package mtl-2.0.1.0 ... linking ... done.
Loading package bytestring-0.9.1.10 ... linking ... done.
Loading package array-0.3.0.2 ... linking ... done.
Loading package containers-0.4.0.0 ... linking ... done.
Loading package deepseq-1.1.0.2 ... linking ... done.
Loading package text-0.11.0.5 ... linking ... done.
Loading package parsec-3.1.2 ... linking ... done.
ghci> parse p "<string>" "abc"
Right "ab"
ghci> parse p "<string>" "ac"
Left "<string>" (line 1, column 1):
unexpected "c"
expecting "ab"
ghci> parse p "<string>" "d"
Left "<string>" (line 1, column 1):
unexpected "d"
expecting "ab"
ghci> parse p "<string>" ""
Left "<string>" (line 1, column 1):
unexpected end of input
expecting "ab"
ghci> parse (many p) "<string>" "ababc"
Right ["ab","ab"]
ghci> parse (many p) "<string>" "ababa"
Left "<string>" (line 1, column 5):
unexpected end of input
expecting "ab"
ghci> parse (many $ try p) "<string>" "ababa"
Right ["ab","ab"]

所以,many $ try lrcMeta就是不断尝试解析歌词元信息,直到解析失败时停止。

接下来是对歌词数据的解析。因为一行可能有多个时间,我们把它存储成多条LrcLine,所以需要使用concat来连接下每次调用lrcLine返回的结果列表。

自顶向下设计解析器:余下的部分

lrcMeta很简单,一行文本,由中括号括起来,其中的键和值用冒号隔开:

lrcMeta :: GenParser Char st (String, String)
lrcMeta = do
  char '['
  key <- many $ noneOf ":"
  char ':'
  val <- many $ noneOf "]"
  char ']'
  eol
  return (key, val)

lrcLine差不多,不过涉及到时间的解析:

lrcLine :: GenParser Char st [LrcLine]
lrcLine = do
  times <- many1 lrcTime
  line <- many $ noneOf "\r\n"
  optional eol
  return $ map (\t -> LrcLine {
    time = t,
    line = line
  }) times

嗯?没看到对时间的解析?哦,它在这里:

lrcTime :: GenParser Char st Int
lrcTime = do
  char '['
  minutes <- readInt
  char ':'
  second <- readInt
  centisec <- option 0 $ char '.' >> readInt
  char ']'
  return $ 60 * 100 * minutes + 100 * second + centisec
  where readInt = read <$> many digit

好了,你可以编译下试试了。RWH说过了,Compile early, compile often。这样在你不小心出错时,强大的编译器能够及时提示你。

哦,下边是 import 列表:

import Data.Char (isDigit)
import Data.Functor ((<$>))
import Data.List (sort)
import Data.Maybe (isJust, fromJust)
import Text.ParserCombinators.Parsec

你试过了吗?发生了什么?

是的,我还有个「抄袭」RWH的换行符解析器没列出来。链接在文末给出了,大家自己去找吧 ;-)

什么?你没找到?好吧,那你加上这个,也可以编译的了。其实类型的语句早该写的。

eol :: GenParser Char st String
eol = undefined

这样就定义了eol函数,它被定义为一个匹配任意类型的「未定义」值。

最后加点工具函数

一个给把 offset 加到歌词数据里的,另一个则是给歌词在时间轴上偏移一定时间的。

lrcAddOffset :: Lrc -> Lrc
lrcAddOffset l = l { lyrics = ly', metadata = meta' }
  where ly = lyrics l
    meta = metadata l
    offset = lookup "offset" meta >>= parseInt
    ly' = case offset of
          Just t -> addTime (fromInteger t `div` 10) ly
          otherwise -> ly
    meta' = filter notOffset meta
    notOffset = (/= "offset") . fst

addTime :: Int -> [LrcLine] -> [LrcLine]
addTime t = map $ \l -> l { time = (t + time l) }

嗯,还是个parseInt用来把字符串转成整数,并且很好地处理异常。

parseInt :: String -> Maybe Integer
parseInt s = case reads s of
  [(int, "")] -> Just int
  otherwise   -> Nothing

完整代码

-- module Text.Lrc (
--   parseLrc,
--   addTime,
--   lrcAddOffset,
--   Lrc(..),
-- ) where
-- 为测试,这个被注释掉了

import Data.Char (isDigit)
import Data.Functor ((<$>))
import Data.List (sort)
import Data.Maybe (isJust, fromJust)
import Text.ParserCombinators.Parsec

data Lrc = Lrc {
  title :: Maybe String,
  artist :: Maybe String,
  album :: Maybe String,
  by :: Maybe String,
  metadata :: [(String, String)],
  lyrics :: [LrcLine]
}

data LrcLine = LrcLine {
  time :: Int,
  line :: String
} deriving (Eq, Show, Ord)

lrcParser :: GenParser Char st Lrc
lrcParser = do
  metadata <- many $ try lrcMeta
  ly <- concat <$> many lrcLine
  return Lrc {
    title = lookup "ti" metadata,
    artist = lookup "ar" metadata,
    album = lookup "al" metadata,
    by = lookup "by" metadata,
    metadata = metadata,
    lyrics = sort ly
  }

lrcMeta :: GenParser Char st (String, String)
lrcMeta = do
  char '['
  key <- many $ noneOf ":"
  char ':'
  val <- many $ noneOf "]"
  char ']'
  eol
  return (key, val)

lrcLine :: GenParser Char st [LrcLine]
lrcLine = do
  times <- many1 lrcTime
  line <- many $ noneOf "\r\n"
  optional eol
  return $ map (\t -> LrcLine {
    time = t,
    line = line
  }) times

lrcTime :: GenParser Char st Int
lrcTime = do
  char '['
  minutes <- readInt
  char ':'
  second <- readInt
  centisec <- option 0 $ char '.' >> readInt
  char ']'
  return $ 60 * 100 * minutes + 100 * second + centisec
  where readInt = read <$> many digit

eol :: GenParser Char st String
eol = try (string "\n\r")
  <|> try (string "\r\n")
  <|> string "\n"
  <|> string "\r"
  <?> "end of line"

lrcAddOffset :: Lrc -> Lrc
lrcAddOffset l = l { lyrics = ly', metadata = meta' }
  where ly = lyrics l
        meta = metadata l
        offset = lookup "offset" meta >>= parseInt
        ly' = case offset of
                   Just t -> addTime (fromInteger t `div` 10) ly
                   otherwise -> ly
        meta' = filter notOffset meta
        notOffset = (/= "offset") . fst

addTime :: Int -> [LrcLine] -> [LrcLine]
addTime t = map $ \l -> l { time = (t + time l) }

parseInt :: String -> Maybe Integer
parseInt s = case reads s of
  [(int, "")] -> Just int
  otherwise   -> Nothing

main = getContents >>= \lrcfile -> case parse lrcParser "<stdin>" lrcfile of
  Left err -> print err >> error "Failed."
  Right lrc -> mapM_ print $ lyrics $ lrcAddOffset lrc

参考链接

Category: Haskell | Tags: Haskell
1
7
2012
26

Haskell 实战:获取ArchLinux已安装的所有架构相关的软件包名

学而不用则惘。

任务内容

通过读取 pacman 数据库,获取本机已安装软件包中所有架构相关的软件包名。pacman 的数据库中,包描述文件位于/var/lib/pacman/local/*/desc,其中星号部分为软件包名加版本号。该文件中,%NAME%的下一行为软件包名,%ARCH%的下一行为架构,我这里是i686或者any。任务就是找出所有 i686 的软件包名。

任务解析

先写个纯函数,通过一块描述文本(Data.Text)判断这个包是否是架构相关的。类型声明为:

import qualified Data.Text as T
isArchDependent :: T.Text -> Bool

然后看看我们怎么才能办到这点。首先,用T.lines把这「块」文本解析成行的列表。然后我们来找为%ARCH%的这一行。怎么找呢,把前边的行丢掉好了:

(dropWhile (/= archstart)) . T.lines
  where archstart = T.pack "%ARCH%"

现在列表的第二项就是我们要的架构类别。先取两行,最后一行就是了:

last . (take 2) . (dropWhile (/= archstart)) . T.lines

然后做比较,得到最终的结果:

isArchDependent = (/= anyarch) . last . (take 2) . (dropWhile (/= archstart)) . T.lines
                  where archstart = T.pack "%ARCH%"
                        anyarch = T.pack "any"

知道一个包是不是我们要的了,但我们还不知道它的名字。此信息我可以肯定在第二行,就不慢慢 drop 了:

getPackageName :: T.Text -> T.Text
getPackageName = last . (take 2) . T.lines

再来个筛选函数,把将要显示的包描述信息找出来:

filterArchDependent :: [T.Text] -> [T.Text]
filterArchDependent = filter isArchDependent

接下来,是程序中「不纯」的部分。我们需要列出目录/var/lib/pacman/local下的所有目录,然后读取其中的desc文件。

getPackagePaths :: IO [FilePath]
getPackagePaths = (filter ((/= '.') . head)) `fmap` getDirectoryContents "."

getPackageDesc :: FilePath -> IO T.Text
getPackageDesc = TIO.readFile . (++ "/desc")

最后,把以上这些函数组合起来:

topDir = "/var/lib/pacman/local"

main = do
  setCurrentDirectory topDir
  getPackagePaths >>= mapM getPackageDesc >>= ((mapM TIO.putStrLn) . (map getPackageName) . filterArchDependent)

首先为了避免一大堆的路径拼接,进入topDir里边来。然后(main的第三行)写到:获取所有软件包的路径;对于每个路径,获取对应软件包的描述信息并处理;怎么处理呢?先过滤filterArchDependent,再逐个获取包名,最后把它打印出来。

代码

完整的代码如下:

import qualified Data.Text as T
import qualified Data.Text.IO as TIO
import System.Directory (getDirectoryContents, setCurrentDirectory)
import Control.Monad

isArchDependent :: T.Text -> Bool
isArchDependent = (/= anyarch) . last . (take 2) . (dropWhile (/= archstart)) . T.lines
                  where archstart = T.pack "%ARCH%"
                        anyarch = T.pack "any"

filterArchDependent :: [T.Text] -> [T.Text]
filterArchDependent = filter isArchDependent

getPackageName :: T.Text -> T.Text
getPackageName = last . (take 2) . T.lines

topDir = "/var/lib/pacman/local"

getPackagePaths :: IO [FilePath]
getPackagePaths = (filter ((/= '.') . head)) `fmap` getDirectoryContents "."

getPackageDesc :: FilePath -> IO T.Text
getPackageDesc = TIO.readFile . (++ "/desc")

main = do
  setCurrentDirectory topDir
  getPackagePaths >>= mapM getPackageDesc >>= ((mapM TIO.putStrLn) . (map getPackageName) . filterArchDependent)

性能分析

我使用这个 Perl 脚本来计时,跑 20 次取平均时间。Shell 算起算术来太麻烦了 :-(

#!/usr/bin/perl
 
use Time::HiRes qw(gettimeofday);
 
sub gettime {
  my ($sec, $usec) = gettimeofday;
  $sec * 1000_100 + $usec;
}
 
my $times = 20;
my $start = gettime;
for(my $var = 0; $var < $times; $var++){
  `$ARGV[0]`;
}
my $end = gettime;
printf "%lfus\n", ($end - $start) / $times;

作为对照的是个 Python 脚本:

#!/usr/bin/env python3

import os

topDir = "/var/lib/pacman/local"

def checkPackage(file):
  for l in open(file):
    l = l.rstrip()
    if l == '%NAME%':
      next = 'name'
    elif l == '%ARCH%':
      next = 'arch'
    else:
      if next == 'name':
        name = l
      elif next == 'arch':
        return name, l != 'any'
      next = ''

def main():
  for name in os.listdir(topDir):
    if name.startswith('.'):
      continue
    file = '%s/%s/desc' % (topDir, name)
    name, show = checkPackage(file)
    if show:
      print(name)

if __name__ == '__main__':
  main()

这两个脚本长度都差不多,但效率相差挺显著的:

>>> ~tmp/t.pl './packagestat > /dev/null'
86055.100000us
>>> ~tmp/t.pl './packagestat.py > /dev/null'
248090.450000us

花絮

最开始,我用的是Data.Text.LazyData.Text.Lazy.IO这个包里的 Lazy 文本类型,结果是——

>>> ./packagestat
packagestat: glpng-1.45-4/desc: openFile: resource exhausted (Too many open files)

评论

写完这两个脚本,我体会到了Real World Haskell里说的,Even with years of experience, we remain astonished and pleased by how often our Haskell programs simply work on the first try, once we fix those compilation errors. Haskell 程序基本上编译通过后就能正确运行——只是要先修正各种编译错误。Python 那个跑了几遍才得到正确的结果。不过我觉得,除了 GHC 的强大之外,编写逻辑简单、没有状态变量也是正确率高的重要原因之一。

疑问

如果我想同时统计这些软件包的总大小(包描述信息里有),怎么才能只读一遍这些文件就同时做到这两件事呢?

Category: Haskell | Tags: Haskell
1
3
2012
41

为什么业界很少使用 Haskell?

这是 Stackoverflow 中一篇答案的粗略翻译,原文地址 http://stackoverflow.com/a/2302230/296473已失效

  1. 没有人听说过它。没有人会使用他们根本不知道的东西。

  2. 不够流行。人们认为最流行的语言就是最好的语言,因为如果它不好的话,它就不会流行。实际上这根本不成立。最流行的语言最流行,仅此而已。Haskell 不流行是因为它不流行。这就是 Haskell 里经常用到的「递归」。不管来自命令式编程世界的人们怎么说,递归在现实世界中非常常见。

  3. 它不一样。人们总是害怕新事物。

  4. 它很难。人们认为 Haskell 难学难用。这显然和第三点有关。Haskell 里充斥着一些高深晦涩的术语,如「单子就是自函子范畴中的独异点,有什么问题吗?」(译注:这句话真难译 :-( )。普通人可理解不了这个。

  5. 有风险。大多数公司不想第一个吃螃蟹。Haskell 的用户太少了,所以很少有用户愿意尝试它。(看吧,又是递归。)

  6. 招不到程序员。首先,按第二点,会 Haskell 的人很少。然后,大多数人相信第四点,所以找不到愿意学习的程序员。使用一门招不到程序员的编程语言风险太大了。(好吧,我们回到第五点了。)

  7. 库。这可能是最重要的一点,所以我多说一些。

    A. 质量。有很多库,可是质量参差不齐。大多数 Haskell 库(Hackage)是个人的业余项目,文档欠缺。有些不完整,有些已经不再能用,有些在特定情况下会出错。

    B. 多个不兼容的库。能够使用 Haskell 连接到数据库。但问题是,存在一堆这样的库,让人很难分辨出哪些是被支持的库,哪些在几年前就已经烂掉了。而且,在 Haskell 中连接数据库也不像开个 ODBC 连接那样简单。针对每种数据库,每个库都用不同的后端。在数据库支持的广泛性上 Haskell 做得不错,连新出现的 Mongo 或者 Cassandra 数据库都支持。开源可能没有给予 Haskell 以深度,但给予了其以广度。

    C. Windows。几乎所有重要的库(比如加密、二进制数据文件格式、网络协议、数据压缩、连接数据库等)是 C 语言库的包装。它们在 Windows 上编译不了。因为 Windows 是市场上最大的目标平台,这是个大问题

  8. 效率无法预测。由于对 Haskell 缺乏了解,很多人甚至都不知道这一点。很多人直接就认为「Haskell 效率低下」。这不对。事实是,很难预测一个 Haskell 程序的效率。微妙的、没有明显关联的不同有时可能导致效率的巨大差异。(译注:蝴蝶效应啊?)

  9. 正确性。大多数公司对正确性并不重视。它们不在意质量。它们只要尽可能迅速地把代码扔出去赚大把大把的钞票就好了。如果代码有 bug 的话,它们就向客户卖补丁。把代码写对没用;重要的是快速把代码写出来。Haskell 会用优美的解来回馈那些坐下来深入分析问题的人。大多数公司不喜欢这样;他们只要尽可能快地把产品搞出来,以后再修正它,如果还有以后的话。

的确有少数地方正确性很重要。这些地方基本上要么是级别甚高的安全系统,要么是金融系统。(译注:交集不为空?)就我所知,Haskell 在这些领域还是比较流行的。

最后说两点:

  • 我还记得不是太久前人们还叫嚷着「C++ 是给菜鸟的玩具!你应该用像 C 这样真正的编程语言。」现在再看看有多少大型 C++ 程序?

  • 人们总是在说 Lisp 是「下一个里程碑性语言」。他们说了多久?已经 40 年了?Lisp 比几乎所有主流编程语言都要老。现在看看有多少大型 Lisp 程序?

我不知道 Haskell 的命运终将如何。我觉得,Haskell 好的思想会被像 C# 或者 F#、OCaml 这样的杂交语言偷取。人们依旧不会使用 Haskell。它太不一样了。

不管怎么说,关于为什么业界不用 Haskell,见以上观点。它太罕见、太不流行、太奇特,库也不完善。大约就是这样。


后记:

也许,照耀大地的永远是在众恒星中普普通通的太阳,人们永远不会知道在宇宙的某个角落里曾经诞生过一颗绝美无比的小星星。这个世界是不完美的,否则如果它是完善的,缺少了不完美,它还完美吗?这个世界是不公平的,流星划过苍穹,带给多少人希望,而它自己却身殒,不留下一点痕迹。

Category: Haskell | Tags: Haskell 译作

部分静态文件存储由又拍云存储提供。 | Theme: Aeros 2.0 by TheBuckmaker.com