My Blogs
Posts tagged with "Clojure"
Lambda演算之Y-Combinator的推导
Published 2014年09月18日 12:00 by james
上一节中，我们讲到了如何使用λ演算来描述自然数，可以看出λ演算的表现力确实非常强大，然而遗憾的是，由于lambda演算中使用的都是匿名函数，所以它无法很直观地表述递归。 如果缺少了递归，λ演算的能力无疑会大打折扣。
所有基于λ演算的语言中，其实都是支持对过程进行命名的，那为什么这里我们还需要探讨匿名函数的递归呢？
- 为了保持纯洁性，我们希望仅仅通过λ演算的规则本身来解决递归的问题。
- 部分语言对过程的命名必须等到该过程定义完成后才可以进行，这个时候我们必须找到一种方式使其能够很容易地获得递归的能力。
下面我们就是用factorial函数为原型，来看看如何使用lambda演算基本的规则，为其增加递归的能力。
传统定义方式，不过这个方式不符合我们的需求，因为它使用到了函数自身fact。
(defn fact [n] (if (<= n 0) 1 (* n (fact (dec n))))) …Lambda演算之自然数
Published 2014年09月10日 12:00 by james
λ演算（英语：lambda calculus，λ-calculus）是一套用于研究函数定义、函数应用和递归的形式系统。它由阿隆佐·邱奇和他的学生斯蒂芬·科尔·克莱尼在20世纪30年代引入。这种演算可以用来清晰地定义什么是一个可计算函数。
λ演算规则
<expression> := <name> | <function> | <application>
<function> := λ<name>.<expression>
<application …回溯算法Clojure实现
Published 2014年05月29日 15:10 by james
什么是回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
算法实现
算法准备
准备一个默认的打印函数，把数组a中的数组转换成字母打印出来。
(defn display [c]
(println (map #(char (+ 65 %)) c)))
实现方式，在这里，我们设计回溯法的实现需要接受是个参数，分别是n, m, …