Is this Haskell code efficient?

As a beginner exercise, I've implemented the following function to find the n-th element in a list:

elem_at (h:_) 0 = h  
elem_at (_:t) n = elem_at t (n-1)  
elem_at _ _     = error "Index out of bounds"

However, if I call: elem_at [1,2,3,4] 5, is it corr开发者_C百科ect that it will return "Index out of bounds" only after having traversed the whole list, so that the last line matches the pattern _ _ with [] 1? More generally, if the list were big wouldn't that be a performance issue? Can ghc somehow optimize that situation?

In fact, this is precisely the canonical way to index a list, almost. You need to add in checking for negative numbers

elem_at xs n | n < 0 =  error "elem_at: negative index"

And you could add a specific match for the empty list:

elem_at [] _         =  error "elem_at: index too large"

And the base and inductive case:

elem_at (x:_)  0         =  x
elem_at (_:xs) n         =  elem_at xs (n-1)

and you've got the Prelude definition of list indexing, the (!!) operator.

A slightly more efficient version can be yielded via the worker wrapper, floating the index test to the top level.

I believe that the haskell implementation is about as efficient as traversing a singly-linked list in any language. If the data were stored in a different structure, then the you could answer the question without traversing the list.