1

我想从列表列表中找到元素的位置。

例如，在给定的列表 [[1,2,3],[4,5,6],[7,8,9]] 我想找到 8 的位置。函数应该返回 [[3,2 ]]，即第三行第二列。如果列表是 [[1,2,8],[4,5,6],[7,8,9]] 那么它应该返回： [[1,3],[3,2]] 如果可以找不到那么它应该返回空列表

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

我想以最有效的方式做到这一点。谢谢。

4

4 回答 4

4

好的，让我们分解一下。

如果您只对正常的整数列表感兴趣，那么您有

 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..]

那太棒了！但是你想要一个整数列表的列表，对吧？

我建议您更改您的需求规范以将每个“坐标”作为元组而不是列表返回。也就是说，让它这样

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)]

因为

  • 您需要告诉函数要查找的值
  • 没有理由仅限findPosition于搜索 s 列表的列表Int--- 它需要对内部元素做的就是比较它们是否相等
  • 您的版本将返回一个总是长度为 2 的列表列表：如果内部列表为空或长度为 3，那将是一个错误；我们可以通过使用一对来排除这种错误的可能性

我也会findPosition产生从零开始的索引（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 回答
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 回答
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 回答