Рекурсивное определение этой функции

Question

У меня есть эта функция, написанная в Haskell, которая использует понимание списка.

search :: String -> Char -> [Int] 
search str letter = [ num | (x, num) <- (zip str [0..]), letter == x] 

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

Спасибо за вашу помощь

Answer 1

Вот несколько предложений.

Негативное, но рабочее решение можно найти по этой схеме рекурсии.

search :: String -> Char -> [Int] 
search []  letter = ??? 
search (x:xs) letter = doSomethingWith (search xs letter) 
    where doSomethingWith :: [Int] -> [Int] 
      doSomethingWith ns = ??? 

Подумайте, как вы могли бы превратить результат рекурсивного вызова в фактический результат. Например:

search "abcb" 'b' = doSomethingWith (search "bcb" 'b') 
        = doSomethingWith [0,2] 
        should be 
        [1,3] 

search "bbcb" 'b' = doSomethingWith (search "bcb" 'b') 
        = doSomethingWith [0,2] 
        should be 
        [0,1,3] 

Обратите внимание, что в doSomethingWith вы можете обратиться к x и проверить, является ли она равна letter.

---

Для лучшего решения попробуйте добавить дополнительный параметр, чтобы пропустить индекс текущей позиции. Например:

search :: String -> Char -> [Int] 
search str letter = searchWorker str letter 0 -- initial position is 0 

searchWorker :: String -> Char -> Int -> [Int] 
searchWorker []  letter position = ??? 
searchWorker (x:xs) letter position = 
    -- increment position at every recursive call 
    doSomethingWith (searchWorker xs letter (position+1)) 
    where doSomethingWith :: [Int] -> [Int] 
      doSomethingWith ns = ??? 

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

searchWorker "abcb" 'b' 0 
        = doSomethingWith (searchWorker "bcb" 'b' 1) 
        = doSomethingWith [1,3] 
        should be 
        [1,3] 

searchWorker "bbcb" 'b' 0 
        = doSomethingWith (searchWorker "bcb" 'b' 1) 
        = doSomethingWith [1,3] 
        should be 
        [0,1,3] 

Answer 2

Вы

search :: String -> Char -> [Int] 
search str letter = [ num | (x, num) <- (zip str [0..]), letter == x] 

, что это делает он идет по списку ввода символов (строка), а при увеличении значения индекса на 1 для каждого нового персонажа. И при этом он проверяет, совпадает ли символ с указанным, и если да, то он производит его (или, скорее, его индекс).

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

search str letter = go str <initial-index-value> 
    where 

здесь мы хозяева нашей области, мы можем, однако, имеют много параметров для нашей внутренней функции мы хотим – мы не ограничены молниях пар, которые диктуются <- оператором список понимание в. Более того, мы можем рассчитывать сами, создавая новые индексы по мере необходимости.

 go [] _ = -- we've reached the end of the input. 
       -- we should finish up our output 
       .... -- ok, it's the end of any list - an empty list 
    go (x:xs) i 
     | x == letter = 

мы имеем доступ к letter потому что go внутренняя функция к нашей search, так что мы можем сравнить их. Здесь мы хотим, чтобы произвести этот показатель сразу

      i : <a recursive call with updated parameters> 
     | otherwise = 

ничего производить здесь, просто сделать

       <a recursive call to continue the search 
           on input list's tail, with the new 
           current index value> 

И мы сделали.