определение позиции элемента из списка списка

Question

Я хочу найти позицию элемента из списка.

Например, в данном списке [[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 .. ? 

Я хочу сделать это с наиболее эффективным способом. Спасибо.

Answer 1

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

Answer 2

ОК, поэтому давайте сломаем это.

Если вы заинтересованы только в обычном списке Интс, вы получили

findPosition :: [Int] -> [Int] 

Как вы можете осуществить это? Ну, ну, вам нужен вход для того, что вы на самом деле ищете!

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

OK, прохладный. Таким образом, встроенная функция elem сообщает вам , если Элемент, который вы хотите, есть. Но мы хотим, чтобы это было позиция. Так как? Ну, вы можете «ярлык» каждый элемент с его положением, например, так:

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

Теперь мы можем использовать filter, чтобы найти все элементы:

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

Но мы хотим только фактические позиции, не x s (все они идентичны в этой точке). Таким образом, мы можем получить map fst.

Сборка все,

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

---

Это здорово! Но вам нужен список списков от ints, не так ли?

Я предлагаю вам изменить спецификацию требований, чтобы возвращать каждую «координату» как кортеж, а не список. То есть, сделайте так

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

Это, вероятно, менее запутанно. Надеюсь, я дал вам достаточно намеков, чтобы понять вещи отсюда ...

Answer 3

Возможное решение:

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) 

Мы аннотировать каждый элемент в списке и подсписков с индексом, и использовать экземпляр Monad для списка для поиска всех возможных сообщений.

Answer 4

Ваш тип подписи неправильный.Он должен быть

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

потому

• вам нужно указать функцию, какое значение для поиска
• нет никаких оснований ограничивать findPosition только поиск списков списков Int с --- все он должен делать с внутренними элементами, сравнивая их для равенства
• Ваша версия вернет список списков, которые всегда были длиной 2: если внутренний список был пустым или имел длину три, это было бы ошибкой; мы можем исключить возможность такого рода ошибки с помощью пары вместо

Я хотел бы также иметь findPosition результат нулевой на основе индексов (в качестве используемых стандартных функций список в Haskell) вместо одного на основе индексов вы просили для.

Таким образом, у меня будет, например, findPosition 8 [[1,2,3],[4,5,6],[7,8,9]] = [(2, 1)].

---

К сожалению Hoogle не знает никаких функций с типом Eq a => a -> [[a]] -> [(Int, Int)]. Но поиск более простой подписи Eq a => a -> [a] -> [Int] (аналогичная функция, которая ищет список, а не список списков) указывает нам на elemIndices. Мы можем использовать это в findPosition.

(. О, я слишком устал, чтобы закончить это Надеюсь, это даст вам пищу для размышлений.)