What you get from functional programming is not only functional code but also our thinking about problems. It refactors the design of the algorithm.
The following program is used to permute a list:
def rotated(list, i, j):
lt = list[i:j + 1]
return list[0:i] + lt[-1:] + lt[0:-1] + list[j + 1:]
def perm(list, i, colt):
if i < len(list):
for j in range(i, len(list)):
perm(rotated(list, i, j), i + 1, colt)
else:
colt.append(list)
colt = []
perm([1, 2, 3, 4], 0, colt)
for list in colt:
print(list)Basically, function code doesn't use loops so let's change it to:
def rotated(list, i, j):
lt = list[i:j + 1]
return list[0:i] + lt[-1:] + lt[0:-1] + list[j + 1:]
def perm(list, i, colt):
def doFor(j):
if j < len(list):
perm(rotated(list, i, j), i + 1, colt)
doFor(j + 1)
if i < len(list):
doFor(i)
else:
colt.append(list)
colt = []
perm([1, 2, 3, 4], 0, colt)
for list in colt:
print(list)Here come some questions. First, the function doFor is named heedlessly because I cannot pick know a suitable name for it. It's used to replace the for loop. According to what it does, you may give it a name such as rotateAndPermSub. This implies that it does two things at the same time so it's difficult to return just one value. If you don't refactor doFor, perm will also be difficult to return just one value. You can only use colt to collect all permutations.
The key point of functional programming is to decompose a problem into sub-problems. Just talked, doFor does two things at the same time. If you want to decompose a problem, doFor is an obvious target. doFor does two things: rotating a part of a list and permuting the tail of the new list. This process will continue until i reaches the list end. As you can see, perm calls doFor and doFor calls perm recursively. Two recursions make the algorithm too complicated.
Let's think it again. doFor does two things: Rotating a part of a list and permuting the tail of the new list...rotating...permuting...rotating...permuting... Well, what if you get all list rotations and then permute all tails of rotated lists? So first, let's define an allRotated function:
def allRotated(list):
def rotatedTo(i):
return [list[i]] + list[0:i] + list[i + 1:]
return [rotatedTo(i) for i in range(len(list))]Give allRotated any list. It will be rotated from the head to the end. Once allRotated is defined, it's easy to define a perm function. It simply needs to call itself recursively.
def perm(list):
if list == []:
return [[]]
else:
lts = allRotated(list)
return reduce(lambda a, b: a + b,
[[[lt[0]] + pl for pl in perm(lt[1:])] for lt in lts])You can compare it with the original program. You will find it's not necessary to use an index i to point out where we are processing. We can simply permute the tail of a rotated list every time. Python's syntax, lt[1:], is convenient here. The revision of the original code are:
from functools import reduce
def allRotated(list):
def rotatedTo(i):
return [list[i]] + list[0:i] + list[i + 1:]
return [rotatedTo(i) for i in range(len(list))]
def perm(list):
if list == []:
return [[]]
else:
lts = allRotated(list)
return reduce(lambda a, b: a + b,
[[[lt[0]] + pl for pl in perm(lt[1:])] for lt in lts])
for list in perm([1, 2, 3, 4]):
print(list)After you refactor code functionally, even if you get back to solve the problem imperatively, the logic is still clearer.
def allRotated(list):
def rotatedTo(i):
rotated = []
rotated.append(list[i])
rotated.extend(list[0:i])
rotated.extend(list[i + 1:])
return rotated
all = []
for i in range(len(list)):
all.append(rotatedTo(i))
return all
def perm(list):
pls = []
if list == []:
pls.append([])
else:
for lt in allRotated(list):
for tailPl in perm(lt[1:]):
pl = []
pl.append(lt[0])
pl.extend(tailPl)
pls.append(pl)
return pls
for list in perm([1, 2, 3, 4]):
print(list)Compared with the imperative code of the original example, it's really much clearer. Although it's a bit boring to write imperative code in Python, it's very important for programming languages without functional features, such as Java. If you use Java to implement the beginning and last code, you'll find their readability and logic are very different.