3

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 correct 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?

Improve this question

2 Answers 2

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Thanks! That makes sense. But wait... to math [] _, starting with [1,2,3,4] and 5, I have to use the inductive case 4 times, right?
If n is too large, you'll hit the base case of elem_at [] _. This is good because if you compare the n to the length, you end up traversing the list once to get the length and then again to find the element.
@Tim you are right. Supplementary question: does Haskell store the length of a list internally so that querying it could be real fast?
Nope. You could write your own list that did, but then you couldn't use the built-in functions that operate on lists. There has been some talk of making the list type into a typeclass so it could be generalized, but I don't think anything has been done on that. Besides, @Don Stewart would be better at continuing that line of thought so I leave off here.
@Frank: no, lists are the simple recursive type, data [a] = [] | a : [a]. That's it. If your algorithm depends on indexing or length-taking, consider using finger trees or vectors (Data.Sequence or Data.Vector).
|
2

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.

Improve this answer

2 Comments

My "issue" is that I like the code above very much, because it's so concise. It would be ideal if I could write nothing more, and still have very efficient code at runtime. I have written another version that triggers the error on out of bounds faster (I think), but it's not as elegant.
If you have a static list and you just want quick look-ups, you might get an efficiency improvement by converting your list to an array. haskell.org/haskellwiki/Modern_array_libraries

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.