list - Haskell：列表边界

Question

我有一个双打列表（myList），我想将其添加到一个新列表（someList）中，但是一旦新列表达到设定的大小，即 25，我想停止添加它。我曾尝试使用 sum 实现此功能，但没有成功。下面的示例代码。
一些列表 = [(a)| a <- myList, sum someList < 30]

Answer 1

@DanielFischer 表达问题的方式与 Haskell 的思维方式兼容。

您是否希望 someList 成为 myList 的总和 < 30 的最长前缀？

这是我的处理方法：假设我们的列表是

>>> let list = [1..20]

我们可以使用以下方法找到“累积和”：

>>> let sums = tail . scanl (+) 0
>>> sums list
[1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210]

现在将其与原始列表压缩以获得总和到该点的元素对

>>> zip list (sums list)
[(1,1),(2,3),(3,6),(4,10),(5,15),(6,21),(7,28),(8,36),
 (9,45),(10,55),(11,66),(12,78),(13,91),(14,105),(15,120),
 (16,136),(17,153),(18,171),(19,190),(20,210)]

然后我们可以通过takeWhile这个列表来获取我们想要的前缀：

>>> takeWhile (\x -> snd x < 30) (zip list (sums list))
[(1,1),(2,3),(3,6),(4,10),(5,15),(6,21),(7,28)]

最后，我们可以摆脱用于执行此计算的累积和：

>>> map fst (takeWhile (\x -> snd x < 30) (zip list (sums list)))
[1,2,3,4,5,6,7]

请注意，由于懒惰，这与递归解决方案一样有效——只需计算它们未通过测试的总和。可以看出这是因为该解决方案适用于无限列表（因为如果我们需要计算所有总和，我们将永远无法完成）。

我可能会抽象这个并将限制作为参数：

>>> :{
... let initial lim list =
...        map fst (takeWhile (\x -> snd x < lim) (zip list (sums list)))
... :}

这个函数有一个明显的属性它应该满足，即列表的总和应该总是小于限制（只要限制大于0）。所以我们可以使用 QuickCheck 来确保我们做对了：

>>> import Test.QuickCheck
>>> quickCheck (\lim list -> lim > 0 ==> sum (initial lim list) < lim)
+++ OK, passed 100 tests.

Answer 2

someList = makeList myList [] 0 where
    makeList (x:xs) ys total = let newTot = total + x
                               in if newTot >= 25
                                  then ys
                                  else makeList xs (ys ++ [x]) newTot

这会从 myList 中获取元素，只要它们的总和小于 25。

逻辑发生在makeList. 它获取输入列表的第一个元素并将其添加到运行总数中，看看它是否大于 25。如果是，我们不应该将它添加到输出列表中，我们完成递归。否则，我们将x输出列表 ( ys) 放在末尾，并继续处理输入列表的其余部分。

Answer 3

你想要的行为是

ghci> appendWhileUnder 25 [1..5] [1..5]
[1,2,3,4,5,1,2,3]

因为总和是 21，加上 4 会变成 25。

好的，解决此问题的一种方法是仅将它们附加，++然后获取 25 岁以下的初始段。

appendWhileUnder n xs ys = takeWhileUnder n (xs++ys)

我不想继续对中间列表求和，所以我会跟踪我被允许的数量（n）。

takeWhileUnder n [] = []
takeWhileUnder n (x:xs) | x < n = x:takeWhileUnder (n-x) xs
                        | otherwise = []

在这里我允许x通过，如果它不带我超出我剩余的津贴。

可能不受欢迎的副作用：如果总和超过 25，它将删除原始列表的位。解决方法：使用

appendWhileUnder' n xs ys = xs ++ takeWhileUnder (n - sum xs)

xs无论它是否带你过来，它都会保留整个n。