Loops and state with pure functions

How would you write a loop in Python without ‘for/while’ ?

this:

i = 0
while i < 10:
   print i
   i = i +1

can be replaced by a recursive function like this:

def f(i):
   if i < 10: 
       print i
       f(i+1)
 
f(0)

In fact we can do to other variables what we’ve just done with the loop counter i, use a function parameter to pass new values

j = []
i = 0
while i < 10:
   j.append(i)
   i = i +1
 
print j

becomes

def f(i, j):
   if i < 10:  
       return f(i+1, j + [i])
   else:
       return j
 
print f(0, [])

So functions let us loop and change state.
While these transformations are pretty simple, they can be tricky to apply on a bigger piece of code…

Here is the Python code I wanted to rewrite:

def tokenize(s):
    "Convert a string into a list of tokens."
    return s.replace('(',' ( ').replace(')',' ) ').split()
 
def read_from(tokens):
    "Read an expression from a sequence of tokens."
    if len(tokens) == 0:
        raise SyntaxError('unexpected EOF while reading')
    token = tokens.pop(0)
    if '(' == token:
        L = []
        while tokens[0] != ')':
            L.append(read_from(tokens))
        tokens.pop(0) # pop off ')'
        return L
    elif ')' == token:
        raise SyntaxError('unexpected )')
    else:
        return token
 
print read_from(tokenize("(*(+ 3 4)(+ 6 7))"))

And here is the version without loop construct and mutation…

def tokenize(s):
    "Convert a string into a list of tokens."
    return s.replace('(',' ( ').replace(')',' ) ').split()
 
def parse_fun(tokens):
    _, ast = parse_fun_aux(tokens)
    return ast
 
def parse_fun_aux(tokens):
    if len(tokens) == []:
        raise SyntaxError('unexpected EOF')
    if tokens[0] == '(' :
        return loop(tokens[1:],[])
    elif tokens[0] == ')' :
        raise SyntaxError('unexpected )')
    else:
        return (tokens[1:], tokens[0])
 
def loop(tokens, ast):
    if tokens[0] == ')':
        return (tokens[1:], ast)
    else:
        tokens_left, token = parse_fun_aux(tokens)
        return loop(tokens_left, ast + [token])
 
print parse_fun(tokenize("(*(+ 3 4)(+ 6 7))"))

Les commentaires sont fermés.