回复 86# starwing83
关于缓式求值。在默认缓式求值的语言中，缓式求值是普遍深入的。
C（generator本来就只是模拟缓式求值的机制，而C连模拟generate都困难）里，只能一边产生组合，一边剪枝。
你给的第2个lua版本，是将产生所有组合的方式利用generator缓式化，对么？ 当需要一个组合时，就resume得到一个， 再判断它与3的关系。
但在默认缓式求值的语言中， 连产生一个组合 —— bit32.totable —— 都是缓式的。
当你需要某个组合中的某个元素时，它的计算才会被求值。
缓式求值显然是有代价的，肯定需要计算本身（相对于计算结果）记录在某些地方。
但一个显然的好处是它将原先的产生组合的过程从整个dfs中剥离了出来。 这部分就可以复用。
也许这些函数式的可复用代码拼凑在一起后可能达到手工拼凑dfs的效果 —— 手工dfs也需要自己记录一些，比如i， selected， 递归也是利用函数调用栈。
能达到手工拼凑的例子有。比如count_if(elems, pred)。
haskell里 count_if 可以用 filter 与 length 定义， 并且filter 产生的中间list可以被消除。
http://stackoverflow.com/questions/9070570/counting-number-of-elements-in-a-list-that-satisfy-the-given-predicate
在其他语言里通常就不能这么干。
用缓式的totable拼出一个组合， 再缓式拼出所有组合， 这部分是范化的通用代码； 最后在它们的基础上编写逻辑相关的剪枝 —— 我不能肯定是否能达到手工将3者全写在一起的效率。
我觉得对你举的这个例子应该没戏……至少在空间效率方面肯定败了。需要保存的中间结果太小， 就一个N大小的数组……
而对一些逻辑更复杂的，并且是有经验的haskell程序员， 也许就可以。
BTW： 这也是bench不好做的一个例子。
haskell其实效率很高， 但需要有很深入的了解才知道它那些机制会产生怎样的代价， 这种代价与手写是否相同， 或者即使差一点也值得用运行时间来换开发时间？
haskell的效率很难估计， 它的抽象层次与机器相差太远了， 很容易写出低效的代码。
你前面举的那个gambit慢的文章， 就也许类似我看到过的一个说haskell慢的文章。 你猜他怎么比的……
它用一个不纯的而且是严格求值的函数式语言， 命令式地建一个大的hash表。 然后将这代码直译到haskell……
回复 91# OwnWaterloo
要不对这个问题你给个haskell代码？我也很好奇这是怎么做的。
缓式缓式，但是缓式也得有被求值的时候。这里最麻烦的是次序问题。缓式求值只能避过不必要的求值，却没有办法改变求值的逻辑顺序。这里的问题是。组合是**早就产生**的，我们是在已经产生后的组合上进行**筛选**，而dfs的情况下，组合是**延后产生**的，我们是确定产生的组合无效的前提下进行**剪枝**，这里的逻辑次序都不一样。一个是产生组合->验证组合，还有一个是验证组合->产生组合。就算是缓式求值，在第二个方案中，你也必须在列出组合以后再验证是不是合法组合，而合格验证过程对其后的产生、验证过程毫无好处。因此即使是缓式求值我也认为**完全**没有作用，这是算法上的问题，不是写法上的问题。
这就是我说的第二个算法完全没有价值的原因：它在**算法**上就杜绝了所有**实现**上的优化。因为它的顺序错了（先产生后验证，验证udi产生没有好处），一个相似的例子是朴素求素数和筛法，一个是产生并验证，效率低，一个直接跳，其实就是验证再产生。
我认为lisp是相同的问题，是先理论在实现，最后发现实现有问题，没法和计算机模型匹配。而其他语言是先考虑实现复杂度再抽象出理论。这样就和计算机模型兼容了，对计算机来说自然。但是这样就很考验一个人的理论水平了，不然就会变成ruby或者python式的patch语言。
这就是我举这个例子的含义。
对了，这个题你试着用haskell写写看哈，就当是教教我怎么写haskell呗。
回复 90# starwing83
比如我举的那个 define/set!(scheme), defun(common lisp/emacs lisp)与 set(emacs lisp)的比较。
这样吧…… 就举set/setq， 貌似cl与el都支持的。
有两种需求：
1. 需要设置某个变量的值， 该变量编译时可知
2. 需要设置某个变量的值， 该变量只有运行时才知道
set可以完成两种。
(set 'x 12) ; x => 12
(set v 26) ; (eval v) => 26
而setq就只能完成前一种。 在这个层面来说， 它是一种特殊化的set —— 编译时必须可知的set。
如果对一种范化机制的专门化使用， 能达到特殊机制的效率， 为什么还要提供那种特殊机制？
理由依然也有。 但其实是两种看待问题的方式。
例如scheme与lua支持尾调用优化， 而clojure不支持。 对一个纯函数式语言不支持尾调用优化是很要命的事， 所以它支持一种特殊的loop/recur， 然后将它翻译为goto。
如果换另一种角度看待loop/recur。
假设某种语言的尾调用优化支持并不完善， 但该语言依然鼓励程序员去使用， 因为总有一天这东西可以被完善。
而对那些必须不增长栈的尾调用， 可以将loop/recur当作一种询问： 这地方我确实需要它被优化， 编译器你能保证么？
还是以scheme与lua为例（支持尾调用优化的语言不多……），但它们都不支持：
(define factorial
(lambda (x)
(if (> x 0) (* x (factorial (- x 1))) 1)))
必须得显式地写出那个accumulator。
这确实不算是尾调用， 但这种模式实在是太常见， 为什么要程序员一次又一次去自己写那个accumulator？ 编译器不能帮助翻译吗？
这时就可以让loop/recur作为一种询问，假设这样：
(define factorial
(lambda (x)
(if (> x 0) (recur (* x (factorial (- x 1)))) 1)))
编译器能将代码进行某种转换后，保证recur可以复用栈空间吗？ 如果可以，就执行； 如果不可以， 那我人工转换， 直到某个版本支持这种转换。
这是两种看待问题的方式： 优先考虑程序员表达与优先考虑编译器实现 —— lisp与Fortran。
set比setq更范化， 所以优先提供前者， 并尽量让前者的专门化使用能达到后者的效率。
如果暂时没能达到， 可以让setq作为一种优化的hint。
如果这目标达到了无论是一开始就达到还是后续达到了再将setq废弃， 至少后续程序员就不需要了解setq这个东西。
而如果优先提供setq， 程序员就需要去找set， 或者根本就限制了程序员， 让他根本就想不到原来还可以这样。
用set/setq做类比， lisp已经在考虑setq的事情了。
r6rs里对翻译到C/JVM/CLI的实现方式来说， 要高效地实现尾调用优化确实很困难， 依然坚持将尾调用优化作为强制要求只是为了维持向后兼容。
类似的还有mutable/immutable cons/string。
最后， 即使添加了许多限制， 也依然没能伤害到lisp的精髓。
而且这种从一开始就考虑范化/通用化的设计的语言， 肯定比那些从一开始就只考一种又一种特殊化/专门化的设计的语言更简练。
它只在不得不特殊化的地方才做妥协。
lua的coroutine相比python的generator的例子你也清楚……
回复 92# starwing83
你说的次序可以包含在产生内。
我都忘了你说的是要找=3还是找>=3的……假设是找>=3吧。
你所说的剪枝是否是后面4种组合肯定满足，不需要在验证了，直接产生？
后面的4种组合肯定不满足，直接丢弃。
而如果一次产生一个完整的排列，比如就被重复验证了4次，同样？
可以不产生每个完整的排列，而直接产生决策树嘛……
不是验证一个完整的排列的序列， 而是验证产生排列的树， 如果没达到要求，直接放弃整个子树。
依然可以将产生与决策剥离。
嗯，产生完整排列的序列确实没希望了……
紧急召唤瓜瓜来把你们两个禁言了，都歪到第10页了
回复 94# OwnWaterloo
是吧……
我说的第二种方式就是产生整个组合，而产生决策树说白了就是dfs。
本帖最后由 2gua 于 2012-03-04 08:32 编辑
歪题就此打住！继续者禁言！
回复 92# starwing83
歪题就此打住！继续者禁言！
回复 94# OwnWaterloo
歪题就此打住！继续者禁言！
帖子中给的链接 点不进去了.