Last night a friend asked me what functional programming was, and as part of my answer I decided to rewrite a trivial program in the functional style to see what it was like. I did this in Python without using the functional module.
The program finds the longest sequence of repeated characters in a string; if there’s a tie, it returns the first sequence of that length. My (imperative) version was six lines of Python:
def findlongestrepeater(string): longest, curr = "", "" for c in string: curr = "".join([curr, c]) if c in curr else c longest = curr if len(curr) > len(longest) else longest return longest
There are doubtless better ways to do it, but this is relatively succinct and clear. I can’t say the same about the functional version I came up with.
With my attempt at this example, “functional programming” basically meant “not using the assignment operator”.
I couldn’t see any way to do it without recursion, and it came out looking like a recursive decision tree:
def findlongestrepeater(string): def flr(lr, curseq, s): return lr if len(s) == 0 else character_match(lr, curseq, s) def character_match(lr, curseq, s): if s == curseq: return sequence_length(lr, u"".join([s,curseq]), s) else: return flr(lr, s, s[1:]) def sequence_length(lr, newseq, s): if len(newseq) > len(lr): return flr(newseq, newseq, s[1:]) else: return flr(lr, newseq, s[1:]) return flr(string, string, string[1:])
flr takes arguments of the longest repeating sequence found so far, the current sequence, and the rest of the string. We kick it off by passing it the first character as the first two arguments, and then the rest of the string after the first character.
If the rest of string has a length of zero, we’ve reached the end of the string and flr returns the longest repeating sequence it was passed.
Otherwise, it calls character_match, which checks whether or not the current sequence matches the first character in the string. If not, it goes back to flr passing in the next character and the rest of the string; if so, it goes on to sequence_length passing in the longest repeater, the new sequence (which is the first character in the string plus the current sequence), and the string. sequence_length will then call flr with either the new sequence as the longest repeater, or the current longest repeater as the longest repeater.
It was pretty hard for me to approach the problem this way. It took me about forty minutes to get a working version, and another fifteen to clean it up (the first version was big jumble of conditionals). It’s also much harder to troubleshoot than the imperative version, at least for me. Recursion isn’t that hard to handle, but I really wanted to use variables just to make things clearer—for example, in character_match, I really want to replace u"".join([s,curseq]) with newseq = u"".join([s,curseq]) and then call sequence_length with newseq as the second argument, purely to make what’s going on more explicit.
It was definitely an interesting experiment, and in future I might try some exercises where I have to take functions and rewrite them without using assignment. I’m sure there are cases where this makes sense; I’m also sure that the above script would be a lot easier to deal with in a proper functional language (or perhaps using the functional module).
After doing that last night, this morning I came across an introduction to functional programming with Python.