Как получить индекс элемента в списке, не используя «списки»?

Question

Я новичок в программировании на Haskell и пытаюсь решить проблему, не используя списочные выражения.

Проблема состоит в том, чтобы найти индекс элемента в списке и вернуть список индексов (где были найдены элементы в списке).

Я уже решил проблему, используя списочные выражения, но теперь у меня есть некоторые проблемы, чтобы решить проблему без использования списочных пониманий.

На моем рекурсивном пути:

Я попытался сжать список [0..(length list)] и сам список. затем, если элемент a равен элементу в списке -> создайте новый список с первым элементом Tupel zip list(my index) и после этого ищите функцию рекурсивным способом, пока список не станет [].

Это мой список понимания (работы):

positions :: Eq a => a -> [a] -> [Int]
positions a list = [x | (x,y) <- zip [0..(length list)] list, a == y]

Это мой рекурсивный способ (не работает):

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    let ((n,m):ns) = zip [0..(length (x:xs))] (x:xs)
    in if (a == m) then n:(positions' a xs)
       else (positions' a xs) 

* извините, я не знаю, как выделить слова

но ghci говорит:

*Main> positions' 2 [1,2,3,4,5,6,7,8,8,9,2]
[0,0]

и так должно быть (мое понимание списка):

*Main> positions 2 [1,2,3,4,5,6,7,8,8,9,2]
[1,10]

Где моя ошибка?

Answer 1

Мы можем использовать подход filter :: (a -> Bool) -> [a] -> [a] и map :: (a -> b) -> [a] -> [b], например:

positions  :: Eq a => a -> [a] -> [Int]
positions x = map fst . filter ((x ==) . snd) . zip [0..]

Таким образом, мы сначала строим кортежи вида (i, y<sub>i</sub>), затем мы фильтруем их так, что мы сохраняем только те кортежи, для которых x == y<sub>i</sub>, и, наконец, получаем первый элемент этих кортежей.

Например:

Prelude> positions 'o' "foobaraboof" 
[1,2,8,9]

Answer 2

Проблема с вашей попыткой заключается в том, что когда вы говорите:

let ((n,m):ns) = zip [0..(length (x:xs))] (x:xs)

тогда n всегда будет 0. Это потому, что вы сопоставляете (n,m) с первым элементом zip [0..(length (x:xs))] (x:xs), который всегда будет (0,x).

Само по себе это не проблема, но это означает, что вы должны правильно обработать рекурсивный шаг. То, как у вас это сейчас, positions _ _, если не пусто, будет всегда иметь 0 в качестве первого элемента, потому что единственный способ позволить ему найти совпадение, это если он находится во главе списка, в результате чего индекс 0. Это означает, что ваш результат всегда будет списком правильной длины, но со всеми элементами 0 - как вы видите.

Проблема не в вашей схеме рекурсии, а в том, что вы не модифицируете результат, чтобы учесть тот факт, что вы не всегда хотите, чтобы 0 добавлялся в начало результата список. Поскольку каждый рекурсивный вызов просто добавляет 1 к индексу, который вы хотите найти, все, что вам нужно сделать, это map функция приращения (+1) над рекурсивным результатом:

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    let ((0,m):ns) = zip [0..(length (x:xs))] (x:xs)
    in if (a == m) then 0:(map (+1) (positions' a xs))
       else (map (+1) (positions' a xs))

(Обратите внимание, что я изменил ваш let, чтобы он был явным, что n всегда будет 0 - я предпочитаю быть явным таким образом, но это само по себе не меняет вывод.) Поскольку m всегда связан с x, а ns вообще не используется, мы можем исключить let, вставив определение m:

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    if a == x
    then 0 : map (+1) (positions' a xs)
    else     map (+1) (positions' a xs)

Вы можете продолжить выделять повторяющиеся map (+1) (positions' a xs), если хотите.

Кстати, вам не требовалась явная рекурсия, чтобы избежать понимания списка здесь. Во-первых, списки являются заменой для использования map и filter. Я собирался записать это явно, но я вижу, что @WillemVanOnsem дал это как ответ, поэтому я просто отсылаю вас к его ответу.

Другой способ, хотя, возможно, и неприемлемый, если вас попросят реализовать это самостоятельно, это просто использовать встроенную функцию elemIndices , которая делает именно то, что вы пытаетесь реализовать здесь.

Answer 3

Ваш

    let ((n,m):ns) = zip [0..(length (x:xs))] (x:xs)

эквивалентен

== {- by laziness -}
    let ((n,m):ns) = zip [0..] (x:xs)
== {- by definition of zip -}
    let ((n,m):ns) = (0,x) : zip [1..] xs
== {- by pattern matching -}
    let {(n,m)     = (0,x)
        ;      ns  =         zip [1..] xs }
== {- by pattern matching -}
    let { n        =  0
        ;   m      =    x
        ;      ns  =         zip [1..] xs }

, но вы никогда не ссылаетесь на ns!Так что нам вообще не нужна его привязка:

positions' a (x:xs) =
    let { n = 0  ;  m = x } in
    if (a == m) then n : (positions' a xs)
                else     (positions' a xs) 

и, таким образом, заменив, у вас фактически есть

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    if (a == x) then 0 : (positions' a xs)      -- NB: 0 
                else     (positions' a xs) 

И вот почему все, что вы когда-либо производили, это 0s.Но вы хотите получить правильный индекс: 0, 1, 2, 3, ....

Во-первых, давайте немного подправим ваш код в

positions' :: Eq a => a -> [a] -> [Int]
positions' a  =  go xs
  where
  go  []  = []
  go (x:xs) | a == x    =  0 : go xs            -- NB: 0 
            | otherwise =      go xs 

Это называется преобразованием "рабочий / упаковщик".go - рабочий, positions' - оболочка.Нет необходимости передавать a от звонка к звонку, он не меняется, и мы все равно имеем к нему доступ.Он входит в объем по отношению к внутренней функции , go.Мы также использовали охранники вместо более многословного и менее наглядного if ... then ... else.

Теперь нам просто нужно использовать что-то - правильное значение индекса - вместо 0.

Чтобы использовать это, мы должны сначала иметь это.Что это?Он начинается с 0, а затем увеличивается на каждом шаге по списку ввода.

Когда мы сделаем шаг по списку ввода?При рекурсивном вызове:

positions' :: Eq a => a -> [a] -> [Int]
positions' a  =  go xs 0
  where
  go  []    _ = []
  go (x:xs) i | a == x    =  0 : go xs (i+1)    -- NB: 0 
              | otherwise =      go xs (i+1)

_ как шаблон означает, что мы не заботимся о значении аргумента - он есть, но мы не собираемся его использовать.

Теперь нам осталось только использовать i вместо 0.