Write a function that takes in no arguments and returns two functions, prepend and get, which represent the “add to front of list” and “get the ith item” operations, respectively. Do not use any python built-in data structures like lists or dictionaries. You do not necessarily need to use all the lines
def nonlocalist():
get = lambda x: "Index out of range!"
def prepend(value):
nonlocal get
f = get
def get(i):
if i == 0:
return value
return f(i - 1)
return prepend, lambda x: get(x)
can someone help explain how these codes work, i have no idea from the beginning how to write it.
In a nutshell, this works by storing data in closures, and using recursion to retrieve them. As a very short primer on closures:
def foo(value):
def bar():
print(value)
return bar
b = foo(42)
b() # prints 42
The value
here is being "closed over". This means even though the execution of foo
has already ended and the variable value
should have gone out of scope and been garbage collected, since bar
refers to it, it is still kept around and is in fact accessible to bar
when called.
Your linked list code uses this principle to store values in more and more nested scopes, and uses recursion to traverse back up the scopes and retrieve them.
Here's a visualisation of this abomination in action:
You can play around with it yourself here.
When calling nonlocalist
, you get two functions back: prepend
, and a function that calls the "latest version" of get
.
prepend
always does the same thing:
value
argument.get
in f
.get
with a new function which either:
value
(as demonstrated in the closure example above), orget
(now called f
), which has the previous value
closed overWhen you call the second "getter" function that nonlocalist
gave you, it:
get
and calls it, whichvalue
it has closed over or the result of its previous version.