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

想一些事情。

init_val应该有什么类型？
你需要g做什么？ g 是这段代码中最棘手的部分。如果您了解过延续传递样式，您可能应该将 init_val 和 g 都视为延续。
x代表什么？你需要用它做什么？

我前段时间写了一篇 explanation 关于 foldl 在 foldr 中的定义是如何工作的。您可能会发现它有帮助。

Answer 2

你有

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

一定有道理。没什么return，所以

             = Nothing

是我们在这里所能做的，以适应 return 类型。

所以init_val是一个函数，:: Int -> Maybe a。根据 foldr 的定义，这也是组合函数的“递归”参数，“来自右边”：

iteration x r

但是这个调用也必须 return 就是这样一个函数本身（同样，根据 foldr、foldr f z [a,b,c,...,n] == f a (f b (f c (...(f n z)...)))、f :: a -> b -> b 的定义，即它必须 return 与它在第二个参数中获得的类型相同的值), 所以

               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

希望现在已经清楚了。

编辑： 所以，这类似于通常的基于 foldr 的 zip 实现与 n 向下的降序枚举相融合，确实编码了

的更高级定义

foo xs n = ($ zip xs [n,n-1..]) $ 
                        dropWhile ((>0) . snd) >>>
                        map fst >>>
                        take 1 >>> listToMaybe
         = drop n >>> take 1 >>> listToMaybe $ xs

Answer 3

我建议使用标准 foldr 模式，因为这样更容易阅读和理解代码，当您使用标准函数时：

foldr 具有类型 foldr :: (a -> b -> b) -> [a] -> b -> [b]，其中第三个参数 b 是列表 [a].

acc

在列表中添加所需元素后，您需要停止添加列表 [a] 到 acc 中的元素。然后你从结果列表 [b] 中取出 head，从而得到列表 [a] 的所需元素。
要获得列表 xs 的第 n 个元素，您需要将 xs 的 length xs - n 个元素添加到累加器 acc，计数从列表的末尾开始。
但是如果我们想使用标准的 foldr 函数来提高代码的可读性，在哪里使用迭代器呢？我们可以在我们的累加器中使用它，将它表示为元组 (acc, iterator)。我们从 iterator 中减去 1 每一轮我们将初始列表 xs 中的元素添加到 acc 并停止将 xs 的元素添加到 acc 当我们的 iterator 等于 0 时。
然后我们将 head . fst 应用于 foldr 函数的结果，以获取初始列表 xs 的所需元素，并使用 Just 构造函数对其进行包装。
当然，如果我们的初始列表 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

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

Find the K'th element of a list using foldr

haskell

fold