Naturally my first inclination is to write the thing in a completely self contained purely functional form, which I do below. I think this will be fairly effic

Naturally my first inclination is to write the thing in a completely self contained purely functional form, which I do below. I think this will be fairly efficient under lazy evaluation, since the bottom line is to count off the given number of positions from the front of the list, and then use the tail of that list to step through the original list. Here's the whole thing starting from scratch: # Optional values (also known as the "Maybe" type) # # The (absent) function represents a value that is absent. # The (present value) function represents a value that is present. \absent = (\absent\present absent) \present = (\value \absent\present present value) # Natural numbers. # # The (zero) function represents the number 0. # The (succ n) function represents the number 1+n (the successor of n). # # A natural number is really just an optional predecessor, # so the constructors are just synonyms for the Maybe type. \zero=absent \succ=present # Lists. \null = (\null\cons null) \cons = (\head\tail \null\cons cons head tail) # Subtraction of natural numbers. Computes z = x - y. # # Returns (present z) if x >= y. # Returns absent if x < y. \sub = (\x\y y (present x) # y = zero \yp x absent # y = (succ yp) and x = zero \xp sub xp yp # y = (succ yp) and x = (succ xp) ) # Compute the length of a list. \len = (\list list zero \head\tail succ (len tail)) # Return the item at the position in the list, starting with 0. \item = (\list\pos list absent # list = null \head\tail # list = (cons head tail) pos (present head) # pos = zero, item found \np item tail np # pos = (succ np), keep looking ) # Return the item at the position from the end of the list, starting with 0. \item_end = (\list\pos sub (len list) (succ pos) # Subtract 1+pos from length of list absent # that's out of bounds, no item found \new_pos item list new_pos # look for item normally at new pos )