通过功能实现列表

Question

我实现了这样的列表：

(伪代码(或者稍微修改一下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

另外，作为奖励：

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

但是，这似乎是将列表实现为数组(或哈希表)--使用了一个名为index的参数。但是，我希望实现列表(使用函数)，而不需要在内部使用索引。这个是可能的吗？

Answer 1

表示最接近链接列表，而不是数组:必须遍历每个元素，直到到达所需的元素为止。您只使用index作为寻址列表的一种方式。

为了获得一种更“忠实”的寻址方法，您可以将inner替换为isnil、head和tail操作，就像名单的教会编码那样。