使用foldr查找列表的第K個元素

Question

我試圖通過列表中的索引實現自己的安全搜索元素。 我認爲，我的功能必須有此簽名：

safe_search :: [a] -> Int -> Maybe a 
safe_search xs n = foldr iteration init_val xs n 
iteration = undefined 
init_val = undefined 

我有問題，實現迭代。我認爲，它必須是這樣的：

safe_search :: [a] -> Int -> Maybe a 
safe_search xs n = foldr iteration init_val xs n 
    where 
    iteration :: a -> (Int -> [a]) -> Int -> a 
    iteration x g 0 = [] 
    iteration x g n = x (n - 1) 
    init_val :: Int -> a 
    init_val = const 0 

但它有很多錯誤。我對haskell的直覺是錯誤的。

Answer 1

你有

safe_search :: [a] -> Int -> Maybe a 
safe_search xs n = foldr iteration init_val xs n 

如果null xs成立，foldr iteration init_val [] =>init_val，所以

init_val n 

必須合理。沒什麼可返回的，所以

   = Nothing 

是我們在這裏所能做的，以適應返回類型。

所以init_val是一個函數，:: Int -> Maybe a。截至foldr的定義，這也是什麼「遞歸」的說法在組合功能「從右邊來了」：

iteration x r 

但此調用也必須返回只是這樣的功能本身（再次，通過foldr定義，foldr f z [a,b,c,...,n] == f a (f b (f c (...(f n z)...)))，f :: a -> b -> b即它必須返回值的相同類型的，因爲它在其第二自變量所得到的），所以

   n | n==0 = Just x 

這很簡單，第0個元素是一個在手， x;如果n > 0怎麼辦？

    | n>0 = ... (n-1) 

對不對？只剩下一步，你可以自己做... :)這不是x（列表的元素），它在那裏的點;它必須是一個功能。我們已經收到了這樣一個功能，作爲一個論點......

要看看是怎麼回事，它可以幫助檢查的情況下，當輸入是一個元素的列表，第一，

safe_search [x] n = foldr iteration init_val [x] n 
        = iteration x init_val n 

，並具有兩個元素，

  [x1, x2] n = iteration x1 (iteration x2 init_val) n 
     --    iteration x r      n 

希望現在很清楚。

Answer 2

想想幾件事。

1. init_val應該有什麼類型？

2. 您需要做什麼g？ g是此代碼中最棘手的部分。如果你已經瞭解了延續傳球的風格，你應該把init_val和g都看作是延續。

3. x代表什麼？你需要用它來做什麼？

我寫了一個explanation前一段時間有關如何在foldr工程方面的foldl定義。您可能會發現它很有幫助。

Answer 3

我建議使用標準foldr模式，因爲它更容易閱讀和理解的代碼，當您使用標準功能：

1. foldr有型foldr :: (a -> b -> b) -> [a] -> b -> [b]， 其中第三個參數b是累加器acc您的列表中的元素[a]。
2. 在添加了所需的列表元素後，您需要停止將列表元素[a]添加到acc。然後你拿head結果列表[b]，從而得到列表[a]所需的元素。
3. 要獲得列表xs的第th個元素，您需要將xs的length xs - n元素添加到累加器acc，從列表末尾開始計數。
4. 但是，如果我們想使用標準foldr函數來提高我們的代碼的可讀性，在哪裏使用迭代器？我們可以在我們的累加器中使用它，將其表示爲一個元組(acc, iterator)。我們減去從iterator每回合我們從最初的名單xs到acc添加元素，停下來的xs元素添加到acc當我們的iterator等於01。
5. 然後，我們將head . fst應用於我們的foldr函數的結果，以獲得初始列表xs的所需元素，並用Just構造函數將其包裝。
6. 當然，如果我們初始清單xs的length - 1小於所需元素n的索引，則整個函數safeSearch的結果將爲Nothing。

下面是函數safeSearch的代碼：

safeSearch :: Int -> [a] -> Maybe a 
safeSearch n xs 
    | (length xs - 1) < n = Nothing 
    | otherwise   = return $ findElem n' xs 
    where findElem num = 
      head . 
      fst . 
      foldr (\x (acc,iterator) -> 
        if iterator /= 0 
         then (x : acc,iterator - 1) 
         else (acc,iterator)) 
       ([],num) 

     n' = length xs - n