1

リストを取り、関数の出力に基づいて特定の長さのリストのサブセットを構築する関数を書きたいと思います。

ソートされたリスト xs の最初の 50 個の要素に興味があるだけなら、fst (splitAt 50 (sort xs)).

ただし、問題は、リスト内の要素が同じリスト内の他の要素に依存していることです。要素 p を選択した場合、リストの最初の 50 個の要素に含まれていなくても、要素 q と r も選択する必要があります。リストxsから要素aを取得し、要素aとそのすべての必要な要素を含むリストを返す関数finderFuncを使用しています。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

終了が終了1の一部としてのみ役立つ場合は、次のようにすることができます:

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 に答える