Implementing lists through functions

Question

I implemented lists like this:

(pseudocode (or rather slightly changed Python))

function nil():
    function inner(index):
        return null          // saying that the head of an empty list is null
    return inner

function cons(list, element):
    function inner(index):
        if index = 0:
            return element
        else:
            return list(index-1)
    return inner

function head(list):
    return list(0)

function tail(list):
    function inner(index):
        return list(index+1)
return inner

And as a bonus:

function map(list, f):
    if head(list) is null:
        return list
    else:
        return cons(map(tail(list), f), f(head(list)))

However, this seems to be implementing lists as arrays (or hash tables) - an argument called index is used. However, I'd like to implement lists (using functions) without indices being used internally. Is this possible?

Answer 1

Your representation is closest to a linked list, not to an array: you have to traverse through each element until you reach the one you want. You are only using index as a way of addressing the list.

To get a more "faithful" method of addressing, you could replace inner with isnil, head and tail operations, as per the Church encoding of lists.