1

リストのリストから要素の位置を見つけたい。

たとえば、特定のリスト [[1,2,3],[4,5,6],[7,8,9]] で、8 の位置を見つけたいとします。関数は [[3,2] を返す必要があります。 ]]、つまり 3 行目と 2 列目です。リストが [[1,2,8],[4,5,6],[7,8,9]] の場合、次を返す必要があります: [[1,3],[3,2]]見つからない場合、空のリストを返す必要があります

findPosition :: [[Int]]  ->  [(Int,Int)]
findPostion  ..  ?

一番効果的な方法でやりたいです。ありがとう。

4

4 に答える 4

4 
import Data.List

findPosition  :: Int -> [[Int]] -> [(Int,Int)]
findPosition n xs = fp n xs 0

fp n [] i = []
fp n (x:xs) i = p x ++ fp n xs (i+1)
    where 
      p x = zip (repeat i) (elemIndices n x)

例： 

findPosition 3 [[2,3,4,3],[4,5,2,3],[],[3,2,5,6,3],[2],[3]]
   == [(0,1),(0,3),(1,3),(3,0),(3,4),(5,0)]

関数の型アノテーションを次のように変更した場合：

findPosition :: (Eq a1, Num a) => a1 -> [[a1]] -> [(a, Int)]

より一般的な解決策があります。例：

findPosition 'a' ["car","small","caveat","big","","aah!"]
   == [(0,1),(1,2),(2,1),(2,4),(5,0),(5,1)]
于 2013-03-22T02:49:30.720 に答える
4

では、これを分解しましょう。

通常の int のリストにのみ関心がある場合は、

 findPosition :: [Int] -> [Int]

どうすればそれを実装できますか? ええと、あなたが実際に探しているものの入力が必要です!

 findPosition :: Int -> [Int] -> [Int]

うんいいね。したがって、組み込みelem関数は、必要な要素がそこにあるかどうかを教えてくれます。しかし、その位置が必要です。では、どうやって？さて、次のように、すべての要素にその位置を「ラベル付け」できます。

 label :: [x] -> [(Int, x)]
 label = zip [0..]

filterこれで、すべてのアイテムを見つけるために使用できます。

 find :: (Eq x) => x -> [(Int, x)] -> [(Int, x)]
 find x0 = filter (\ (n, x) -> x == x0)

しかし、必要なのは実際の位置だけであり、xs (この時点ではすべて同一です) ではありません。それで、それをmap fst得ることができます。

すべてを組み立てて、

 findPosition :: Int -> [Int] -> [Int]
 findPosition x0 = map fst . filter (\ (n, x) -> x == x0) . zip [0..]

それは素晴らしいことです！しかし、intのリストのリストが必要でしたね。

各「座標」をリストではなくタプルとして返すように要件仕様を変更することをお勧めします。つまり、そうする

findPosition 8 [[1,2,8],[4,5,6],[7,8,9]] => [(1, 3), (3, 2)]

そのほうが混乱しにくいのではないでしょうか。うまくいけば、ここから物事を理解するのに十分なヒントが得られます...

于 2013-03-21T22:11:09.937 に答える
4

型シグネチャが間違っています。そのはず

findPosition :: Eq a => a -> [[a]] -> [(Int, Int)]

なぜなら

  • どの値を探すかを関数に伝える必要があります
  • findPositions のリストのリストのみを検索することに制限する理由はありませんInt--- 内部要素で行う必要があるのは、それらが等しいかどうかを比較することだけです
  • あなたのバージョンは、常に長さ 2 のリストのリストを返します: 内部リストが空であるか、長さが 3 の場合、それはバグです。代わりにペアを使用することで、そのようなバグの可能性を排除できます

またfindPosition、要求した 1 から始まるインデックスの代わりに、0 から始まるインデックス (Haskell の標準リスト関数で使用される) も返されます。

だから私は例えばを持っていfindPosition 8 [[1,2,3],[4,5,6],[7,8,9]] = [(2, 1)]ます。

悲しいことに、Hoogle は type を持つ関数を知りませんEq a => a -> [[a]] -> [(Int, Int)]。しかし、より単純な署名Eq a => a -> [a] -> [Int](リストのリストではなくリストを検索する同様の関数) を検索すると、 が示されelemIndicesます。これは で使用できますfindPosition。

（ああ、疲れすぎてこれを終わらせることができません。うまくいけば、それがあなたに考える材料を与えるでしょう。）

于 2013-03-21T22:17:36.170 に答える
1

考えられる解決策:

import Control.Monad

findPosition :: Eq a => a -> [[a]] -> [(Int,Int)]
findPosition e ll = do
    let annotate = zip [1..]
    (i1,x) <- annotate ll
    (i2,y) <- annotate x
    guard $ y == e
    return (i1,i2)

リストとサブリストの各要素にインデックスで注釈を付け、List の Monad インスタンスを使用して、考えられるすべての出現を検索します。

于 2013-03-21T22:11:36.117 に答える