blogger 不靠谱，页面直接乱掉了

喵的，这上面的博文全部废了……杀回到 javaeye 吧，喵的……

Clojure Stream

(define fibs
  (stream-cons 0
    (stream-cons 1
      (stream-add (stream-cdr fibs) fibs))))

The code above is an excerpt from SICP that generates an infinite Fibonacci sequence. I've tried to migrate it to Clojure.

The following code is the implementations of the stream concept mentioned in SICP and the the Fibonacci function. The essential part is this: (defmacro stream-cons [e s] ...). Because Clojure's cons requires that s to be a ISeq or Seqable, that makes the "(stream-cdr fibs)" part always fails. Because this piece of code is executed before the outer stream-cons ever happened. By the time we execute "(stream-cdr fibs)", we haven't had the value of "fibs" yet.

(defn pair [x y] (cons x [y]))
  
(defn pair-car [p] (first p))

(defn pair-cdr [p] (second p))

(defmacro stream-cons [e s]
  `(pair ~e (delay ~s)))
  
(defn stream-car [s]
  (pair-car s))
  
(defn stream-cdr [s]
  (force (pair-cdr s)))
  
(defn stream-map
  ([f s]
    (stream-cons
      (f (stream-car s))
      (stream-map f (stream-cdr s))))
  ([f s & ss]
    (let [step (fn step [ss]
                  (when (not (empty? ss))
                    (stream-cons (map stream-car ss) (step (map stream-cdr ss)))))]
      (stream-map #(apply f %) (step (cons s ss))))))
    
(defn stream-add [& ss]
  (apply stream-map + ss))
  
(defn take-stream [s count]
  (when (> count 0)
    (stream-cons
      (stream-car s)
      (take-stream (stream-cdr s) (dec count)))))
      
(defn print-stream [s]
  (let [step (fn step [s]
                (when (not (empty? s))
                  (print (stream-car s) "")
                  (recur (stream-cdr s))))]
    (step s)
    (println)))
    
(def fibs
  (stream-cons 0
    (stream-cons 1
      (stream-add (stream-cdr fibs) fibs))))
      
(def ones (stream-cons 1 ones))
(def twos (stream-add ones ones))

(print-stream (take-stream twos 10)) ; => 2 2 2 2 2 2 2 2 2 2
(print-stream (take-stream fibs 10)) ; => 0 1 1 2 3 5 8 13 21 34

Interesting enough that I haven't thought of a way to seamlessly integrate the above stream code into Clojure. If we implement it using (deftype LazyStream [] clojure.lang.Seq ...) that would make cons a function instead of a macro. Therefore I temporarily think that it's impossible to seamlessly integrate the implementation.

Definitions of Imperative & Functional Programming from SICP

Programming without any use of assignments is accordingly known as functional programming.

In contrast to functional programming, programming that makes extensive use of assignment is known as imperative programming.

求对数

下面是求以 1.12 为底，2.7 的对数。本方法极其低效，仅仅标记一下以备以后参考。

(ns t
  (:require [clojure.contrib.generic.math-functions :as math]))

(defn abs [x]
  (if (< x 0) (* -1 x) x))

(defn close-enough? [delta]
  #(< (abs (- %1 %2)) delta))
  
(defn calc-log [lg lg-level acc-stack]
  (let [acc (math/pow 1.12 lg)
        close? (close-enough? 0.00000000000000000001M)
        lg-inc (/ 1 (math/pow 10 lg-level))
        finer-lg-inc (/ 1 (math/pow 10 (inc lg-level)))]
    (if (close? acc 2.7)
      lg
      (if (> acc 2.7)
        (recur (+ (- lg lg-inc) finer-lg-inc) (inc lg-level) acc-stack)
        (recur (+ lg lg-inc) lg-level (conj acc-stack acc))))))
      
(println (calc-log 1 0 []))

空间

《Structure and Interpretation of Computer Programs》中提到，“The ability to create pairs whose elements are pairs is the essence of list structure's importance as a representational tool. We refer to this ability as the closure property of cons.”这话表面上是说 cons 作为 LISP 的核心，能够把自己产生的 pair 作为 cons 的参数进而去产生新的组合 pair，是列表数据结构在表示上非常本质的东西。“closure property”我倾向于翻译成封闭性。因为在代数中，给定 f(x) = y，如果任意 x 属于 Z，且 y 也属于 Z，那么 Z 就对 f 是封闭的。

当然我们可以很容易地想到高中数学里面的列表。这跟 LISP 中的列表是完全对应的。正是这种特性造就了 LISP 语言的强大。但是这种模式对于即使不熟悉数学的程序员来说也应该似曾相识。比如 JUnit4 和 JMock 里面用的 Hamcrest Matcher。你可以任意组合各种 matcher 达到想要的效果。比如 assertThat(result, is(not(greaterThan(10)))。它使得 JUnit 摆脱了不停地往 Assert 类里面增加方法的局面。也是为什么 JUnit4 要绑定 Hamcrest Matcher 发布的原因。如今你很难看到一个优秀的测试框架里面不用 Hamcrest Matcher 的。Matcher 的模式就是：makeMatcher(someMather) === AnotherMatcher。也就是说，从逻辑上，makeMatcher 和 Matcher 这个抽象集合组成了一个代数空间。

找到这样的空间，我们就可能找到了非常强大而优雅的工具。比如 SICP 里面提到的 painter。我们可以生成一个给定 painter 的水平镜像 painter、垂直镜像 painter、扭曲 painter，等等。这点对于我们做面向对象设计的时候也极有启发价值。想想 Hamcreset Matcher……

快速排序

看了《The Joy of Clojure》的快速排序，觉得比较丑，而且不通用。所以自己又写了一个。不过有一个比不上书里面的。书里面的支持 lazy-seq，而下面这个不支持。可能正是因为要支持 lazy-seq 所以书里面的那个才会那么繁琐吧……

(defn- split-by [pred coll]
  [(filter pred coll) (remove pred coll)])

(defn qsort-by [comparator work]
  (letfn [(step [ret [pivot & rst :as work]]
            (if-not work
              ret
              (let [[left right] (split-by #(< (comparator % pivot) 0) rst)]
                (if (seq left)
                  (recur ret (concat left [pivot] right))
                  (recur (conj ret pivot) rst)))))]
    (seq (step [] (seq work)))))

(println (qsort-by - [57 66 72 27 16]))
(println (qsort-by - []))
(println (qsort-by - nil))

;=> (16 27 57 66 72)
;=> nil
;=> nil

快速排序（升序）我理解为：给定一个轴（pivot)，遍历所有还没有排序完整的元素（rst），把小于轴的元素放到轴的左边（left），把不小于轴的元素放到轴的右边（right）。完全排序好的元素放到结果集（ret）里。如果左边有元素，说明找到了比轴还要小的元素。那么结果集不动，因为还没有找到最小的元素。如果左边没有元素，说明当前的轴就是最小的，把它加入结果集。

split-by 不同于 split-with。split-with 在遇到第一个不满足条件的元素后就终止了。而 split-by 会把整个集合都遍历一遍（这里的实现是遍历了两遍）。

如果需要排序，请用 Clojure 核心库的 sort 函数。这个函数转调 java.util.Arrays.sort 函数，它是经过高度优化的。我的测试表明我的函数比标准库的慢了两三个数量级…… -_-!

Named arguments in Clojure

Clojure doesn't provide direct support for named arguments, which are supported under some popular dynamic languages like Ruby, Python. The following Python code was exerpted from `The Joy of Clojure':

def slope(p1=(0,0), p2=(1,1)):
return (float(p2[1] - p1[1])) / (p2[0] - p1[0])
slope((4,15), (3,21))
#=> -6.0
slope(p2=(2,1))
#=> 0.5
slope()
#=> 1.0

It calculates the slope of a line, which can be determined by two given points. The following Clojure code mimics the named arguments:

(defn slope
([] (slope [0 0] [1 1]))
([{:keys [p1 p2] :or {p1 [0 0] p2 [1 1]}}] (slope p1 p2))
([p1 p2]
(/ (- (float (p2 1)) (p1 1)) (- (p2 0) (p1 0)))))
(slope [4 15] [3 21])
;=> -6.0
(slope {:p2 [2 1]})
;=> 0.5
(slope)
;=> 1.0

I think it's sufficient for most of the cases. However, if you want to go deeper, let's use the defnk from clojure.contrib.def.

-------------------------
clojure.contrib.def/defnk
([fn-name & fn-tail])
Macro
  Define a function accepting keyword arguments. Symbols up to the first
 keyword in the parameter list are taken as positional arguments.  Then
 an alternating sequence of keywords and defaults values is expected. The
 values of the keyword arguments are available in the function body by
 virtue of the symbol corresponding to the keyword (cf. :keys destructuring).
 defnk accepts an optional docstring as well as an optional metadata map.

Unfornately, no examples were given in the doc string. Here's a simple example:

(require '[clojure.contrib.def :as def])
(def/defnk t [a :b 1] [a b])
(t 3)
;=> [3 1]
(t 3 :b 4)
;=> [3 4]

It should be noted that, the optional/named arguments must be put at the tail of the argument list. i.e. You can't write this: (def/defnk t [a :b 1 c] [a b c]) If you do, weird thing would happen. Or, your function may not even compile.

(def/defnk t [a :b 1 c] [a b c])
(t 1 2 3)
;=> [1 1 nil]
(def/defnk t [a :b 1 c d] [a b c d])
;=> java.lang.Exception: Unable to resolve symbol: d in this context