0

選択された要素が互いに依存するシーケンスのリストを返すリスト内包表記があるとします (以下の例を参照)。以前の計算に基づいて、要素の数とそれに関連する条件を (便利に) プログラムする方法はありますか? たとえば、プログラム内の別の値に応じて、型 [[a,b,c]] または [[a,b,c,d,e]] を返しますか? また、同じアイデアを定式化するためのリスト内包表記以外の/より良い方法はありますか?

(面倒で制限はあるものの、最初はより大きなリスト内包表記を書き出して、1 つ以上の要素を後で簡単にフィルター処理できる値にすることができるパラメーターとヘルパー関数をsに追加することで、それをトリミングすることは可能だと考えました。および関連する条件はデフォルトで True です。)

s = [[a, b, c, d] | a <- list, someCondition a, 
                    b <- list, b /= a, not (someCondition b), 
                    otherCondition a b,
                    c <- list, c /= a, c /= b, not (someCondition c),
                    otherCondition b c,
                    d <- list, d /= a, d /= b, d /= c,
                    someCondition d, someCondition (last d),
                    otherCondition c d]
4

4 に答える 4

4

質問は非常に理解するのが難しいです。

以前の計算に基づいて、要素の数とそれに関連する条件を (便利に) プログラムする方法はありますか?

問題は、この文の「プログラム」は実際には理解できる動詞ではないということです。なぜなら、人間はコンピューターをプログラムしたり、VCR をプログラムしたりしますが、「数値をプログラムする」ことはできないからです。だからここで何を言おうとしているのか理解できない。

しかし、コード レビューを行うことはできます。コード レビューを通じて、あなたが求めている質問を理解できるかもしれません。

未承諾のコード レビュー

行き止まりをなくして迷路を解こうとしているようですね。

あなたのコードが実際に行うことは次のとおりです。

  1. 行き止まりではない、または行き止まりに隣接していないセルのリストを生成します。filtered

  2. ステップ 1 から一連の隣接セルを生成し、sequences

  3. このような隣接する 4 つのシーケンスをルートに連結します。

大きな問題: これは、正しいルートの長さが正確に 8 タイルの場合にのみ機能します! この迷路を解いてみてください:

[E]-[ ]-[ ]-[ ]
             | |
[ ]-[ ]-[ ]-[ ]
 | |
[ ]-[ ]-[ ]-[ ]
             | |
[ ]-[ ]-[ ]-[ ]
 | |
[ ]-[ ]-[ ]-[E]

したがって、コードレビューからさかのぼって作業すると、あなたの質問は次のようになります。

リストの長さが事前にわからない場合、どうすればリストを生成できますか?

ソリューション

検索で迷路を解くことができます (DFS、BFS、A*)。

import Control.Monad

-- | Maze cells are identified by integers
type Cell = Int

-- | A maze is a map from cells to adjacent cells
type Maze = Cell -> [Cell]

maze :: Maze
maze = ([[1],     [0,2,5],     [1,3],   [2],
         [5],     [4,6,1,9],   [5,7],   [6,11],
         [12],    [5,13],      [9],     [7,15],
         [8,16],  [14,9,17],   [13,15], [14,11],
         [12,17], [13,16,18],  [17,19], [18]] !!)

-- | Find paths from the given start to the end
solve :: Maze -> Cell -> Cell -> [[Cell]]
solve maze start = solve' [] where
  solve' path end =
    let path' = end : path
    in if start == end 
       then return path'
       else do neighbor <- maze end
               guard (neighbor `notElem` path)
               solve' path' neighbor

この関数solveは、深さ優先検索によって機能します。すべてを単一のリスト内包表記に入れるのではなく、再帰的に機能します。

  1. startからへのパスを見つけるためにend、 の場合start /= end、

  2. 端に隣接するすべてのセルを見てください, neighbor <- maze end,

  3. guard (negihbor `notElem` path)cellをバックトラックしていないことを確認してください。

  4. startからへのパスを検索してみてくださいneighbor。

一度に関数全体を理解しようとせず、再帰について少しだけ理解してください。

概要

セル 0 からセル 19 へのルートを見つけたい場合は、再帰します。セル 18 と 19 が接続されていることがわかっているので (これらは直接接続されているため)、代わりにセル 0 からセル 19 へのルートを見つける問題を解決することができます。セル18。

これが再帰です。

脚注

警備員、

someCondition a == True

に相当します。

someCondition a

したがって、次と同等です。

(someCondition a == True) == True

または、

(someCondition a == (True == True)) == (True == (True == True))

または、

someCondition a == (someCondition a == someCondition a)

最初のsomeCondition a, は問題ありません。

do表記に関する脚注

上記の例のdo表記は、リスト内包表記と同等です。

do neighbor <- maze end
   guard (neighbor `notElem` path)
   solve' path' neighbor

リスト内包表記の同等のコードは次のとおりです。

[result | neighbor <- maze end,
          neighbor `notElem` path,
          result <- solve' path' neighbor]
于 2013-02-14T12:13:58.573 に答える
1

Data.List.subsequencesがあります

リスト内包表記をモナド形式で書くことができます ( Monad Comprehensions のガードを参照してください):

(説明: モナドは、失敗をサポートするMonadPlusのインスタンスでなければなりません。

guard Falseモナドが mzero への評価に失敗するようにします。その後の結果には List モナドの mplus = (++) が追加されます。)

import Control.Monad (guard)

myDomain = [1..9]   -- or whatever

validCombinations :: [a] -> [[a]]
validCombinations domainList = do
        combi <- List.subsequences domainList
        case combi of
                [a,b] -> do
                        guard (propertyA a && propertyB b)
                        return combi

                [a,b,c] -> do
                        guard (propertyA a && propertyB b && propertyC c)
                        return combi

                _ -> guard False

main = do
         forM_ (validCombinations myDomain) print

再度更新し、要素を再帰的に取得し、組み合わせとチェックを保存します

import Control.Monad

validCombinations :: Eq a => Int -> Int -> [a] -> [(a -> Bool)] -> [a] -> [[a]]
validCombinations indx size domainList propList accum = do

    elt <- domainList   -- try all domain elements

    let prop = propList!!indx
    guard $ prop elt               -- some property
    guard $ elt `notElem` accum    -- not repeated 

    {-
    case accum of
        prevElt : _ -> guard $ some_combined_check_with_previous elt prevElt
        _ -> guard True
        -}

    if size > 1 then do
         -- append recursively subsequent positions

         other <- validCombinations (indx+1) (size-1) domainList propList (elt : accum)

         return $ elt : other
    else
         return [elt]

myDomain = [1..3] :: [Int]

myProps = repeat (>1)

main = do
           forM_ (validCombinations 0 size myDomain myProps []) print 
   where
      size = 2

重要な結果を伴うサイズ 2 の結果:

    [2,3]
    [3,2]
于 2013-02-14T16:30:35.110 に答える