haskell - 为什么我的实施如此缓慢？（在 99 个 Haskell 问题中排名第 26）

Question

在解决问题 26（“生成从列表的 N 个元素中选择的 K 个不同对象的组合”）时，我提出了以下实现：

combi :: Int -> [a] -> [[a]]
combi 0 _ = [[]]
combi n ys@(x:xs) = [ y:xs' | y <- ys, xs' <- combi (n-1) xs ]

建议的解决方案之一是：

combinations :: Int -> [a] -> [[a]]
combinations 0 _  = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combinations (n-1) xs']

虽然有点相似，但提供的解决方案运行速度明显快于我的。

为什么？

Answer 1

1. 您的解决方案不正确。例如combi 2 [1,2]，[[1,2], [2,2]]代替[[1,2]].

2. 您的递归案例总是计算combi (n-1) xs, where length xs == length ys - 1。在正确的解决方案中，xs'每一步的长度都会减少。这似乎是一个很小的差异，但递归将其复杂化。