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

David 发表于 Dev

大卫

我尝试通过列表中的索引实现自己的安全搜索元素。我认为我的函数必须具有以下签名：

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的直觉是错误的。

内斯

你有

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

希望现在清楚了。

编辑：因此，这类似于通常的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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。