這個函數的遞歸定義

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> 

，我們就大功告成了。