其实C++代码中核心部分就是generate函数。但是如果仔细看,会发现思路是不一样的。
一个是从首位开始依次尝试从n各方案中pick一个,其本质是递归版的“深度优先”搜索;这也是众多组合数学教科书上的样板方法。
另一个是从首位枚举所有方案和后继节点展开的结果组合(cons),我个人认为是“广度优先”,这是因为lazy求值的原因。
我完全没有比较C++和Haskell的意图。只是因为试图用lisp写这个算法时遇到了困难,所以拿熟悉的C++来打草稿,这也是为何所有的功能都亲自手动实现了一遍的原因,这样将来用lisp写时就几乎是照猫画虎了。好在这些辅助函数都不麻烦。
我还是觉得搜索到这个haskell的方法满有意思的,因为对比教科书上的方法,这个开阔了思路。一个自然而然的有趣题目就是,用C++实现一个list enumeration。这个会很有意思。
另外,看了一下haskell中delete x xs的源代码,也是中规中矩,并不复杂:
代码:
delete :: (Eq a) => a -> [a] -> [a]
delete = deleteBy (==)
-- | The 'deleteBy' function behaves like 'delete', but takes a
-- user-supplied equality predicate.
deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
deleteBy _ _ [] = []
deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys