使用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