我想概括的例子
下面的函数使用从1到top的整数生成每个长度为2的列表[a,b],a < b.
ascendingPairs top = [ [x,y]
| x <- [1..top],
y <- [x+1..top] ]
> mapM_ (putStrLn . show) $ f 4
[1,2]
[1,3]
[1,4]
[2,3]
[2,4]
[3,4]
我想要的泛化
ascendingPairs仅在生成的列表长度为2的特殊情况下定义。如果我不知道输出列表应该有多长，并且希望这个长度作为参数，该怎么办?
一些不好的策略
这里有一个提供额外长度参数的愚蠢方法:
partial :: Int -> Int -> [[Int]]
partial 1 top = [ [x]
| x <- [1..top] ]
partial 2 top = [ [x,y]
| x <- [1..top],
y <- [x+1 .. top] ]
partial 3 top = [ [x,y,z]
| x <- [1..top],
y <- [x+1 .. top],
z <- [y+1 .. top] ]
partial 4 top = ...
partial 5 top = ...
...
用这种方式写partial，实际上需要永远覆盖所有情况。
这是一种涵盖所有情况的方法。(这种方式实际上不需要list单子)
slow :: Int -> Int -> [[Int]]
slow top size =
filter monotonicAscending $
mapM (x -> [1..top]) [1..size]
monotonicAscending :: [Int] -> Bool
monotonicAscending (a:b:rest) = a < b
&& monotonicAscending (b:rest)
monotonicAscending _ = True
slow节省了人类的时间，但代价是大量的机器时间，因为它产生了太多的尺度，filter monotonicAscending立即下降。计算length $ f 41 7至少需要一分钟，可能需要几个小时(我把它剪掉了)。对于我的目的，我实际上更喜欢partial而不是slow。
一个我希望比必要的更复杂的解决方案
最后我确实找到了一个方法，但我觉得我是在野蛮地强迫它。
monoAscending :: Int -> Int -> [[Int]]
monoAscending top size =
map reverse $
incrementNTimes top (size-1) $ [ [a]
| a <- [1..top] ]
incrementNTimes :: Int -> Int -> [[Int]] -> [[Int]]
incrementNTimes top 0 lists = lists
incrementNTimes top n lists = let
x :: [[Int]]
x = concatMap (increments top) lists
in incrementNTimes top (n-1) x
-- | All the ways of prepending a bigger element to the input list.
-- This assumes the input list is in descending order.
increments :: Int -> [Int] -> [[Int]]
increments top (a:as) = [ b:a:as
| b <- [a+1 .. top]]
工作原理:
> mapM_ (putStrLn . show) $ monoAscending 4 3
[1,2,3]
[1,2,4]
[1,3,4]
[2,3,4]
但是有更好的方法吗?
我建议直接扩展您的第一个想法，用于partial。只是…使用递归!
notPartial 0 bot top = [[]]
notPartial n bot top = [ x:xs
| x <- [bot..top]
, xs <- notPartial (n-1) (x+1) top
]
如果你喜欢，你可以创建一个别名来修复bot。
monoAscending n top = notPartial n 1 top
Try it out:
> monoAscending 3 5
[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
您的解决方案存在三个可解决的复杂性。
- 您有两个基本情况(
monoAscending中incrementNTimes的最后一个参数是基本情况，以及incrementNTimes中的基本情况)。 - 你将结果作为参数传递，而不是简单地使用它作为结果(几乎就像你过早地优化了尾部调用)。
- 你在搞倒车。
幸运的是，这三个都是可以简化的!
首先，让我们从一个基本情况开始:
mkLists :: Int -> Int -> [[Int]]
mkLists _top 0 = [[]]
mkLists top size = ...
存在一个可能的零长度列表，即空列表，因此返回包含空列表的列表。
现在，让我们使用没有尾调用优化的递归调用的结果:mkLists top size = concatMap increments $ mkLists top (size - 1)
where
increments ...
如果可以用concatMap go直接操作递归调用，则不需要将递归调用作为参数传递给任何地方。
最后，让我们编写一个版本的increments，它将小元素添加到列表的开头，而不是大元素，这样我们就不需要在末尾反转列表。
where
increments [] = pure <$> [1..top]
increments xs@(x:_) = (:xs) <$> [1..(x-1)]
当increments获得空列表时，这可能意味着递归调用是针对size=0的，因此我们从1..top生成所有的单例列表。对于所有其他情况，我们希望在给定列表的前面放置一个较小的元素。
mkLists :: Int -> Int -> [[Int]]
mkLists _top 0 = [[]]
mkLists top size = concatMap increments $ mkLists top (size-1)
where
increments [] = pure <$> [1..top]
increments xs@(x:_) = (:xs) <$> [1..(x-1)]
从这里开始，如果你愿意，你可以把这个代码写得更低。辅助函数increments可以写成一行代码(increments xs = (:xs) <$> [1..(maybe top (subtract 1) $ headMay xs)])，递归本身可以重写为一个折叠。