1

我想编写一个函数，它接受一个列表并根据函数的输出构造一个特定长度的列表的子集。

如果我只是对排序列表 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 []，这样它建立的列表就以一个空列表开始。

4

3 回答 3

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

也许问题就在这里……在递归调用中，newrs会变成fs. 因此，在下一次递归调用中，它会检查是否newrs < 50，但您想检查到目前为止累积的总长度（包括“旧” fs）。

因此，您可能希望将递归调用更改为finish newps (fs ++ newrs).

于 2011-11-16T23:12:53.573 回答
0

这是使用累加器的一个非常常见的场景。通常的解决方案是定义

finish1 fs = finish [] fs

如果finish仅作为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 = ...

递归实现阶乘函数时的相关问题，请参见Haskell 中的累加器。

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

于 2011-11-16T23:00:23.713 回答
0

我意识到我没有清楚地说明我的问题。我需要一个函数，它接受一个列表 ps 并返回一个 ps 的子列表 fs。此外，ps中的元素有先决条件，这是ps中的其他元素。因此，在将元素 a 添加到列表 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）。

于 2011-11-18T01:47:04.197 回答