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

if null xshold,foldr iteration init_val []=> init_val,so

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

希望现在很清楚.