时间戳

首页 > 解决方案 > 从字典和维度生成所有可能组合的函数式尾递归方式

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

问题描述

我想找出实现以下指定功能的简洁、功能和尾递归（如果可能）的方式：

(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 也可以。我正在尝试找到可能使用相互或嵌套递归的尾递归解决方案，但目前没有运气。

非常感谢你！

标签： haskellrecursionfunctional-programmingschemesml

解决方案

那个，在 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 中，使用尾递归可能不是一个好主意。

附录回复：内存效率：

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

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

因此，这是您必须在优雅和效率之间进行权衡的情况之一。这个问题最近在这个相关的 SO question中在非常相似的replicateM库函数的上下文中进行了讨论；根据 KA Buhr 的答案，可以利用 Haskell列表理解构造提出一种在恒定内存中运行的 makeDomain 版本。

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，并且在普通 Intel x86-64 PC 上以每个输出列表大约 30 纳秒的速度运行。这是完全合理的。

推荐阅读