# Is it possible to model arrays as functions while preserving O(1) access times?

It is quite easy to model linked-lists as functions, without any underlying collection data type, like so:

```
-- This is Lua code, but the specific language shouldn't matter
function createList(first, rest)
return function(isFirst)
if isFirst
then
return first
else
return rest
end
end
end
function nth(list, n)
-- replace with n==0 for 0 indexing,
if (n == 1)
then
return list(true)
else
return nth(list(false), n-1)
end
end
```

However, this has the disadvantage when compared to arrays that index access has `O(n)`

time complexity. I had been thinking that array literals would be easy to implement thusly:

```
-- {1, 2, 4, 8} ==
function someArray(n)
if (n == 1)
return 1
elseif (n == 2)
return 2
elseif (n == 3)
return 4
elseif (n == 4)
return 8
end
end
```

But I realized that going through each `elseif`

one at a time would still be access time `O(n)`

. I considered a switch statement, as I was under the impression that C's switch statements jumped directly to the tag that matches the result of the condition, but this does not appear to be correct. It appears that with `n`

branches, C's switch selects a branch in `O(n)`

time. Is it possible to select a branch in constant time without using arrays? Is there some other technique for a constant time access to an array modelled as a function that I have missed?