How to find the kth element of an 'infinite' Foldable structure in Haskell?

Question

I'd like to define a function, safeIndex that works on Foldable types

safeIndex :: (Foldable t, Integral i) => t a -> i -> Maybe a
safeIndex = foldr step (const Nothing)
  where
    step :: Integral i => a -> (i -> Maybe a) -> i -> Maybe a
    step x f i = if i == 0
               then Just x
               else f (i - 1)

But it doesn't work for infinite lists. For foldr to stop in the middle, I think we have to determine whether it should stop only with the first argument of step, which seems impossible.

Is it possible to fix the function so that it works on infinite structures? If not, what typeclasses should we restrict t to?

Answer 1

Actually the definition in the question description already works for infinite built-in list. It was some other mistakes that make me thought it couldn't ;) (See the comments.)

Answer 2

If you don't mind taking on a dependency, the foldl library from Gabriel Gonzalez provides index and genericIndex folds which suit your purpose.

For example, you could write

safeIndex :: (Foldable f, Integral a) => a -> f b -> Maybe b
safeIndex = fold . genericIndex

Besides that, the code you posted seems to do what you intend.

EDIT: I spaced the "infinite lists" bit.

This will work for infinite lists, but I don't know that there's a sensible way to define it for all Foldables.

safeIndex' :: Int -> [a] -> Maybe a
safeIndex' n = listToMaybe . foldr (.) id (replicate n (drop 1))

EDIT 2:

Scratch that, what you've got in the original post ought to work for any Foldable.