haskell - 从字典和维度生成所有可能组合的功能性尾递归方式

Question

我想找出实现以下指定函数的简洁、函数式和尾递归(如果可能)的方法:

(define (make-domain digits dimension)
    ;; Implementation)
;; Usage
(make-domain '(0 1) 0) => (())
(make-domain '(0 1) 1) => ((0) (1))
(make-domain '(0 1) 2) => ((0 0) (0 1) (1 0) (1 1))
(make-domain '(0 1) 3) => ((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1))

我更喜欢使用尽可能少的辅助函数或库函数来实现 Scheme，但 SML 或 Haskell 也可以。我正在尝试找到可能使用相互递归或嵌套递归的尾递归解决方案，但目前运气不佳。

非常感谢!

Answer 1

那个，在 Haskell 中，至少是“功能性的”和简洁的(我认为):

makeDomain :: [α] -> Int -> [[α]]
makeDomain xs 0  =  [[]]
makeDomain xs n  =  let  mdn1 = makeDomain xs (n-1)
                         fn x = map (x:) mdn1
                    in   concat (map fn xs)

试用:

 λ> 
 λ> makeDomain [0,1] 2
[[0,0],[0,1],[1,0],[1,1]]
 λ> 
 λ> makeDomain [0,1] 3
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
 λ> 

如评论中所述，至少在 Haskell 中，尾递归可能不是一个好主意。

关于内存效率的附录:

您没有在需求中列出性能问题(是因为您认为尾递归函数往往性能更好吗？)。

makeDomain 的上述版本，如 amalloy 的评论中所暗示的那样内存消耗呈指数级增长，至少对于某些编译器版本/优化级别而言。这是因为编译器可以将 makeDomain xs (n-1) 视为要保留的循环不变值。

因此，在这种情况下，您必须在优雅和效率之间做出权衡。这个问题最近在这个 related SO question 中讨论过。在非常相似的背景下replicateM库函数；根据 K. A. Buhr 的回答，可以想出一个在常量内存中运行的 makeDomain 版本，利用 Haskell list comprehension构造。

makeDomain1 :: [α] -> Int -> [[α]]
makeDomain1 xs n =
    map reverse (helper xs n)
        where
            helper xs 0 = [[]]
            helper xs n = [ x:ys  |  ys <- helper xs (n-1),  x <- xs ]

测试:在 1200 MB 的操作系统强制内存硬限制下运行。

 λ> 
 λ> import Control.Monad (replicateM)
 λ> replicateM 3 [0,1]
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
 λ> 
 λ> makeDomain1 [0,1] 3
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
 λ> 
 λ> length $ replicateM 30 [0,1]
<interactive>: internal error: Unable to commit 1048576 bytes of memory
...

 λ> 
 λ> length $ makeDomain [0,1] 30
<interactive>: internal error: Unable to commit 1048576 bytes of memory
...

 λ> 
 λ> length $ makeDomain1 [0,1] 30
1073741824
 λ> 

使用带有 -O2 选项的 GHC v8.6.5，最后一个版本永远不会占用超过 150 MB 的内存，并且在 vanilla Intel x86-64 PC 上以每个输出列表大约 30 纳秒的速度运行。这是完全合理的。