Haskell：将函数输出添加到列表直到某个长度

Question

我想编写一个函数，该函数需要一个列表并根据函数的输出构建一定长度的列表的子集。

如果我是在排序列表XS的第50个元素只是感兴趣，然后我会用fst (splitAt 50 (sort xs)).

然而，问题是，在我的列表中的元素依赖于在同一列表中的其他元素。如果我选择元素p，那么我也必须选择元素q和r，即使它们不在我列表的前50个元素中。我使用了一个函数finderFunc，它从列表xs中获取一个元素a，并返回一个列表，其中包含元素a及其所有必需的元素。 finderFunc工作正常。现在，面临的挑战是编写一个函数，根据finderFunc的多个输出生成一个总长度为50的列表。

这是我在这样的尝试：

finish :: [a] -> [a] -> [a] 
--This is the base case, which adds nothing to the final list 
finish [] fs = [] 
--The function is recursive, so the fs variable is necessary so that finish 
-- can forward the incomplete list to itself. 
finish ps fs 
    -- If the final list fs is too small, add elements to it 
    | length fs < 50 && length (fs ++ newrs) <= 50 = fs ++ finish newps newrs 
    -- If the length is met, then add nothing to the list and quit 
    | length fs >= 50 = finish [] fs 
    -- These guard statements are currently lacking, not the main problem 
    | otherwise = finish [] fs 
    where 
     --Sort the candidate list 
     sortedps = sort ps 
     --(finderFunc a) returns a list of type [a] containing a and all the 
     -- elements which are required to go with it. This is the interesting 
     -- bit. rs is also a subset of the candidate list ps. 
     rs = finderFunc (head sortedps) 
     --Remove those elements which are already in the final list, because 
     -- there can be overlap 
     newrs = filter (`notElem` fs) rs 
     --Remove the elements we will add to the list from the new list 
     -- of candidates 
     newps = filter (`notElem` rs) ps 

我认识到，上面的if语句，在某些情况下，没有给我确切地50个元素的列表。这不是主要问题，现在。问题是我的功能完成并不像我预期的那样工作。它不仅会在输出列表中生成重复的元素，而且有时会远远高于列表中要包含的元素的总数。

写这个的方式，我通常会用一个空的列表来调用它，例如：finish xs []，这样它建立的列表就以一个空列表开始。

Answer 1

| length fs < 50 && length (fs ++ newrs) <= 50 = fs ++ finish newps newrs 

也许问题就在这里......在递归调用，newrs将成为fs。因此，在下次递归调用时，它将检查是否newrs < 50，但是您要检查迄今为止累积的总长度（包括“旧”fs）。

所以你可能想要改变你的代码，递归调用是finish newps (fs ++ newrs)。

Answer 2

这是使用累加器的一种非常常见的情况。通常的解决方法是定义

finish1 fs = finish [] fs 

如果漆面只是作为finish1的一部分有用的，你可以这样做：

finish fs = finish1 [] fs where 
    finish1 :: [a] -> [a] -> [a] 
    --This is the base case, which adds nothing to the final list 
    finish1 [] fs = [] 
    --The function is recursive, so the fs variable is necessary so that finish 
    -- can forward the incomplete list to itself. 
    finish1 ps fs = ... 

递归实现阶乘功能时，对相关的问题，请参见Accumulators in haskell。

至于限制长度为50个元素，您可以构造一个长列表，然后使用take函数获取50个第一个元素。由于Haskell特定的平衡顺序，它是高效的。

Answer 3

我意识到我没有清楚地说明我的问题。我需要一个函数，它使用ps列表并返回ps的子列表fs。此外，ps中的元素具有先决条件，这是ps中的其他元素。所以，当向列表fs添加元素a时，该函数还必须将所有的先决条件添加到fs。技巧一点是确保没有重复项被添加到fs。 ps中的不同元素可能具有重叠的先决条件，但fs应该是不同元素的列表。

这终于为我工作：

finish :: [a] -> [a] -> [a] 
finish ps fs 
    | length fs < 50 && length (fs ++ newfs) <= n = finish newps (fs ++ newfs) n 
    --If adding a new perk and its prerequisites will bring me over the limit, then ignore it and move to the next perk 
    | length fs < 50 && length (fs ++ newfs) > n = finish (tail (reverse (sort ps))) fs n 
    | otherwise = fs 
    where 
     --This is the interesting value of the given list ps 
     inter = maximum ps 
     --A list of all values which might be useful for 
     maybeNewfs = perkAndPreqs inter 
     --Whittle that list down to a list of distinctly new elements 
     newfs = filter (`notElem` fs) maybeNewfs 
     --Now remove all items added to fs from the candidate list 
     newps = filter (`notElem` maybeNewfs) ps 

从上面的功能键不同的是，我没有转发newfs来函数的递归，我转发（FS ++ newfs）。