Basically, any iterative loop can be written as a recursion. If you deal with a list sequentially, you don't need a counter to point out where we are in a list. All you need is a way to take the head and tail of a list. If a loop has a nested loop, you are actually dealing with two problems. Functional style is forcing you to decompose a problem. For example:
def toPFix(infix, isPost):
expr = infix if isPost else infix[::-1]
stack = []
output = []
toStack, toOutput = ('(', ')') if isPost else (')', '(')
for c in expr:
if c == toStack:
stack.append(c)
elif c in ['+', '-', '*', '/']:
while stack and priority(stack[-1]) >= priority(c):
output.append(stack.pop())
stack.append(c)
elif c == toOutput:
while stack[-1] != toStack:
output.append(stack.pop())
stack.pop()
else:
output.append(c)
while stack:
output.append(stack.pop())
return ''.join(output if isPost else output[::-1])Several loops, isn't it? Just start from the inner loop. In addition to infinite loops, every loop has termination conditions. You have to convert them into recursion termination conditions. Functional style always requires you to think about where boundaries are. Let's deal with the first while loop inside for statement:
def toPFix(infix, isPost):
expr = infix if isPost else infix[::-1]
stack = []
output = []
toStack, toOutput = ('(', ')') if isPost else (')', '(')
def procOpt(c, stack, output):
if stack == [] or priority(stack[-1]) < priority(c):
return (stack + [c], output)
else:
return procOpt(c, stack[0:-1], output + stack[-1:])
for c in expr:
if c == toStack:
stack.append(c)
elif c in ['+', '-', '*', '/']:
# while stack and priority(stack[-1]) >= priority(c):
# output.append(stack.pop())
# stack.append(c)
stack, output = procOpt(c, stack, output)
elif c == toOutput:
while stack[-1] != toStack:
output.append(stack.pop())
stack.pop()
else:
output.append(c)
while stack:
output.append(stack.pop())
return ''.join(output if isPost else output[::-1])procOpt is the solution of the sub-problem, so the return value is assigned to stack and output inside for loop. If you want to move from imperative programming to functional programming, what you need are more exercises. Don't rush all imperative code into function style. Translate them one by one or you'll mess all up. Decomposing a problem is the most important thing to solve a problem functionally. Let's translate the second while in a similar way:
def toPFix(infix, isPost):
expr = infix if isPost else infix[::-1]
stack = []
output = []
toStack, toOutput = ('(', ')') if isPost else (')', '(')
def procOpt(c, stack, output):
if stack == [] or priority(stack[-1]) < priority(c):
return (stack + [c], output)
else:
return procOpt(c, stack[0:-1], output + stack[-1:])
def procPhs(stack, output):
if stack[-1] == toStack:
return (stack[0:-1], output)
else:
return procPhs(stack[0:-1], output + stack[-1:])
for c in expr:
if c == toStack:
stack.append(c)
elif c in ['+', '-', '*', '/']:
stack, output = procOpt(c, stack, output)
elif c == toOutput:
# while stack[-1] != toStack:
# output.append(stack.pop())
# stack.pop()
stack, output = procPhs(stack, output)
else:
output.append(c)
while stack:
output.append(stack.pop())
return ''.join(output if isPost else output[::-1])
Now there's no for loop. Remember, a loop can be viewed as a sub-problem. Finally, let's see how to vanish the for loop:
def toPFix(infix, isPost):
toStack, toOutput = ('(', ')') if isPost else (')', '(')
def procOpt(c, stack, output):
if stack == [] or priority(stack[-1]) < priority(c):
return (stack + [c], output)
else:
return procOpt(c, stack[0:-1], output + stack[-1:])
def procPhs(stack, output):
if stack[-1] == toStack:
return (stack[0:-1], output)
else:
return procPhs(stack[0:-1], output + stack[-1:])
def procExpr(expr, stack = [], output = []):
if expr == "":
return output + stack[::-1]
elif expr[0] == toStack:
return procExpr(expr[1:], stack + [expr[0]], output)
elif expr[0] in ['+', '-', '*', '/']:
return procExpr(expr[1:], *procOpt(expr[0], stack, output))
elif expr[0] == toOutput:
return procExpr(expr[1:], *procPhs(stack, output))
else:
return procExpr(expr[1:], stack, output + [expr[0]])
output = procExpr(infix if isPost else infix[::-1])
return ''.join(output if isPost else output[::-1])Take notice of it. Where's the final while? It's replaced by stack [::-1] inside the first if block of procExpr. Tasks of the final while are to pop an element from stack, append it to output. That means we can just reverse stack, then concatenate it with output, isn't it? You can also write your own recursive function to do so. But in Python, stack[::-1] has the same effect.