Minor Foray into Functional Programming
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[0] == curseq[0]:
return sequence_length(lr, u"".join([s[0],curseq]), s)
else:
return flr(lr, s[0], 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[0], string[0], 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[0],curseq]) with newseq = u"".join([s[0],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.
23 Feb 2010 at 16:07
Best introduction to functional programming I’ve found is MIT’s “Structure and Interpretation of Computer Programs” – the course material to which is all available free online.
It requires a fair amount of commitment to get through it all (I haven’t watched all the lectures yet personally) but its of a very high quality:
http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/
23 Feb 2010 at 17:30
It’s been a long time since I’ve flexed my Scheme muscle, but I did this exercise, for kicks:
(define (longest-rep str) (let ((x (string->list str))) (caddr (longest-helper (car x) (cdr x))))) (define (longest-helper char rest) (if (null? rest) (list char 1 char 1) (let ((result (longest-helper (car rest) (cdr rest)))) (if (eq? (car result) char) (if (> (+ (cadr result) 1) (cadddr result)) (list char (+ (cadr result) 1) char (+ (cadr result) 1)) (append (list char (+ cadr result 1)) (cddr result)) ) (append (list char 1) (cddr result)) ))))Could be a lot cleaner (less list manipulation and I could use let* but I wanted to make it as syntactic-sugar-free as I could)
And yes, I referenced SICP for this. :)
23 Feb 2010 at 21:57
You may want to evaluate this option (not sure if the indentation will get preserved)
strng = 'aasdkjfbbbbdfjdslfaaaaaaasdlkfjcccc' def contiguous(strng): curr = strng[0] for c in strng[1:] : if c in curr : curr = "".join((curr,c)) else : yield curr curr = c yield curr print reduce(lambda curr, other : curr if len(curr) > len(other) else other,contiguous(strng),"")23 Feb 2010 at 22:59
Use this one instead
strng = 'aasdkjfbbbbdfjdslfaaaaaaasdlkfjcccc'
def contiguous_blocks(strng):
curr = [strng[0]]
for c in strng[1:] :
if c in curr :
curr.append(c)
else :
yield "".join(curr)
curr = [c]
yield "".join(curr)
def longest(curr, other) :
if len(curr) > len(other) :
return curr
else :
return other
print reduce(longest,contiguous_blocks(strng),"")
Note: String FP rules would prefer curr = curr + [c] instead of curr.append(c)
26 Feb 2010 at 01:50
Niall: thanks for that link, it looks like the information there is excellent. I’ve barely scratched the surface of the (CC-licensed) textbook for it and it looks great. Is it going to make me determined to learn Scheme?
Barak: that looks both interesting and weird… presumably because I don’t have LISP experience. I did expect it to come in significantly shorter than the Python, although I know you said you avoided syntactic sugar.
Dhananjay Nene: Thanks for that suggestion, making a function out of finding contiguous blocks and then comparing them definitely seems like the right way to approach it. I wrote a post about trying to find a way to do that without using the assignment operator.