Find the K'th element of a list using foldr

Question

I try to implement own safe search element by index in list. I think, that my function have to have this signature:

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

I have problem with implementation of iteration. I think, that it has to look like this:

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

But It has to many errors. My intuition about haskell is wrong.

Answer 1

you have

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

if null xs holds, foldr iteration init_val [] => init_val, so

init_val n

must make sense. Nothing to return, so

             = Nothing

is all we can do here, to fit the return type.

So init_val is a function, :: Int -> Maybe a. By the definition of foldr, this is also what the "recursive" argument to the combining function is, "coming from the right":

iteration x r 

but then this call must also return just such a function itself (again, by the definition of foldr, foldr f z [a,b,c,...,n] == f a (f b (f c (...(f n z)...))), f :: a -> b -> b i.e. it must return a value of the same type as it gets in its 2nd argument ), so

               n | n==0 = Just x

That was easy, 0-th element is the one at hand, x; what if n > 0?

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

Right? Just one more step left for you to do on your own... :) It's not x (the list's element) that goes on the dots there; it must be a function. We've already received such a function, as an argument...

To see what's going on here, it might help to check the case when the input is a one-element list, first,

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

and with two elements,

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

Hope it is clear now.

edit: So, this resembles the usual foldr-based implementation of zip fused with the descending enumeration from n down, indeed encoding the more higher-level definition of

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