CODEWITHSUNDEEP
haskellfold
David
David

Reputation: 674

Find the K'th element of a list using foldr

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.

Upvotes: 1

Views: 1529

Answers (3)

Will Ness
Will Ness

Reputation: 71109

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

Upvotes: 5

Arthur Welf
Arthur Welf

Reputation: 176

I suggest to use standard foldr pattern, because it is easier to read and understand the code, when you use standard functions:

  1. foldr has the type foldr :: (a -> b -> b) -> [a] -> b -> [b], where third argument b is the accumulator acc for elements of your list [a].
  2. You need to stop adding elements of your list [a] to acc after you've added desired element of your list. Then you take head of the resulting list [b] and thus get desired element of the list [a].
  3. To get n'th element of the list xs, you need to add length xs - n elements of xs to the accumulator acc, counting from the end of the list.
  4. But where to use an iterator if we want to use the standard foldr function to improve the readability of our code? We can use it in our accumulator, representing it as a tuple (acc, iterator). We subtract 1 from the iterator each turn we add element from our initial list xs to the acc and stop to add elements of xs to the acc when our iterator is equal 0.
  5. Then we apply head . fst to the result of our foldr function to get the desired element of the initial list xs and wrap it with Just constructor.
  6. Of course, if length - 1 of our initial list xs is less than the index of desired element n, the result of the whole function safeSearch will be Nothing.

Here is the code of the function 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

Upvotes: -1

dfeuer
dfeuer

Reputation: 48611

Think about a few things.

  1. What type should init_val have?

  2. What do you need to do with g? g is the trickiest part of this code. If you've ever learned about continuation-passing style, you should probably think of both init_val and g as continuations.

  3. What does x represent? What will you need to do with it?

I wrote up an explanation some time ago about how the definition of foldl in terms of foldr works. You may find it helpful.

Upvotes: 1

Related Questions