You are viewing bramcohen

Fri, Oct. 16th, 2009, 10:26 am

This post unintentionally demonstrates that functional-style Python is ugly and bad.

Let us start at the top. At the beginning, it has some sample code which defines a multiple() function, which could be trivially inlined, resulting in code which looks like this (I'm doing all examples in Python 3):
print(sum(x for x in range(1, 1000+1) if x % 3 == 0 or x % 5 == 0))

There's no reason whatsoever to expand that out. This should be an early indication that maybe the code samples here aren't the greatest.

Moving on, there's getting the sum of all fibonacci numbers less than 4 million. This is done in the example using itertools and yield, resulting in a fair amount of ugly code. Here's how a sane person does it:
def fibsum():
	a, b, c = 0, 1, 1
	total = 0
	while c < 4000000:
		total += c
		a, b, c = b, c, b + c
	return total

Now that's much more readable, flexible, and maintainable.

Finally, there's the problem of finding the largest palindrome which is the product of two three digit numbers. Here's my solution, which contains less code, is much more readable, and oh yeah, I threw in an optimization to make it return almost instantly instead of having to crunch for a second:
def bigpalindrome():
	best = 0
	for i in range(999, 0, -1):
		if i * 999 < best:
			return best
		for j in range(999, i-1, -1):
			x = list(str(i*j))
			x.reverse()
			if int(''.join(x)) == i*j:
				best = i*j

Much better. I think these examples do a good job of exploding the idea that the functional style of programming is clearly better and the appropriate first thing to teach people. Obviously some people are being driven to write horribly contorted and ugly code because they started in a functional language when they switch a more, ahem, mainstream one.

Fri, Oct. 16th, 2009 07:03 pm (UTC)
theswede

What I noticed when I learned functional programming is that it improved my way of thinking about problems. While I almost never actually write "pure" functional code, even in languages which allow it, it opened my eyes to new ways of solving problems. Ways which were hidden to me before I had gone down the path of writing programs in Haskell and Lisp and really had to bend my brain in new ways.

So, what I think I'm saying is, functional programming a very good thing to study after first learning how to program. =)

Fri, Oct. 16th, 2009 09:14 pm (UTC)
bos31337

Instead of "I think these examples do a good job of exploding the idea that the functional style of programming is clearly better", I'd say "I think these examples demonstrate that idiots write bad code". Python isn't a functional programming language, and that fellow clearly has no idea how to write idiomatic Python in any case, so he produces this stew of garbage and then makes ridiculous claims. Very annoying.

Fri, Oct. 16th, 2009 11:09 pm (UTC)
bramcohen

Your thesis that he's an idiot doesn't actually contradict my thesis about what specific thing he did lamebrainedly.

Fri, Oct. 16th, 2009 10:01 pm (UTC)
agthorr

def fibsum():
	a, b, c = 0, 1, 1
	total = 0
	while c < 4000000:
		total += c
		a, b, c = b, c, b + c
	return total
You could simplify that further by removing "a", which is assigned but never used. Also, your answer is off by one, because the Fibonacci sequence includes 1 twice but your solution only includes it once. You could fix that by initializing b and c with 0 and 1 instead of 1 and 1.

Below is my O(log n) solution, which is based on the idea that this is actually a math problem not an algorithm problem. :-)
from numpy import *
phi = (1 + sqrt(5)) / 2 # golden ratio
m = matrix([[0,1,0],
            [1,1,0],
            [0,1,1]])

def fibsum(n):
    i = int(floor(log(n*sqrt(5))/log(phi))) # largest i such that F_i < n
    return (m**i)[2,1]


(I agree with your main point that the article's Python examples are unnecessarily convoluted, by the way)

Fri, Oct. 16th, 2009 11:07 pm (UTC)
bramcohen

Oh yeah, I could get rid of the 'a' variable. The problem statement didn't make clear whether the first 1 should be counted or not, since it said 'different' numbers, I assumed that it shouldn't. It is of course possible to do even faster than what you have using just a little bit more math, but the point here was cleanliness of code not fanciness of math.

Fri, Oct. 16th, 2009 11:54 pm (UTC)
agthorr

the point here was cleanliness of code not fanciness of math.

Oh, I know. I just couldn't resist the puzzle. :-) How would you find the answer faster?

Sat, Oct. 17th, 2009 12:38 am (UTC)
bramcohen

You can compute the whole thing in closed form based on what i is, it's a typical summation thing. The amount of speedup is very small though, because it's already hardly taking any time at all.

Fri, Oct. 16th, 2009 10:22 pm (UTC)
darius

FWIW, here's how I'd do the problem. It runs slower, but that's OK; this is my default style because it mirrors the problem statement more directly. (And I guess because I used to use Scheme a lot.) I glanced at the code you linked to, and yeah, convoluted.

def bigpalindrome():
    return max(n for n in products() if is_palindrome(n))

def products():
    return (i*j for i in xrange(100, 1000) for j in xrange(i, 1000))

def is_palindrome(n):
    s = str(n)
    return s[::-1] == s

Fri, Oct. 16th, 2009 11:21 pm (UTC)
bramcohen

Your comparison method of str(n)[::-1] == str(n) is terser and probably more idiomatic than mine, but you have a bunch of bugs in your products() function, which should be written using yield instead of comprehensions.

Sat, Oct. 17th, 2009 12:18 am (UTC)
darius

I realize products() computes a different set of candidates than you did; I went by your English and not your code, taking 42 to not be a 3-digit number. Do you mean something else?

I'd still move the str() in my code to the caller of is_palindrome() -- there's always one more tweak.

Sat, Oct. 17th, 2009 12:35 am (UTC)
bramcohen

Turns out max() is a lot more sophisticated than I thought, so there was actually nothing wrong with your code.

Sat, Oct. 17th, 2009 02:59 am (UTC)
pinkpucker.net

sumOfUniqueFibs x = sum (takeWhile (<x) (drop 1 fibs)) 
fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 
fibs will generate an infinite list of fibonnaci numbers, and sumOfUniqueFibs drops the first 1, grabs all of them that are less than x, and sums them up.

Sat, Oct. 17th, 2009 08:00 pm (UTC)
stigant

I'm not a FP zealot, but I'll respectfully disagree with your comments. I find your code less readable, less flexible, and less maintainable than the Clojure code included on that linked page. (I'm not sure how the Python code which is really not functional at all makes a statement about functional programming) Admittedly, I have a bit of practice reading the functional code, but it's not that hard:

(def fib-seq (lazy-cat [0 1] (map + fib-seq (rest fib-seq))))
Now, this is a bit idiomatic, (but no more so than your imperative implementation of the fib sequence). One way to create the fib sequence is to start three lines like so:

0 1 1 2 3 5 8 13 ...
0 1 1 2 3 5 8 13 ...
2 3 5 8 13 21 ...

Where the second line is the first line shifted 1 number to the right, and the third line is the sum of the first two lines, and the first line is the third line with 0 1 1 appended to the beginning (ie as you create the third line, extend the first line). That may take a little bit of time to wrap your head around, but you can see that it's pretty much the same idea as your code, and once you do, the Clojure code is easy to understand:

(def fib-seq (lazy-cat [0 1] (map + fib-seq (rest fib-seq))))
C A B

A: start with 0 1
B: add the list with its shifted self to create new elements
C: don't do any more than you need (this is a feature that no imperative language will ever have in general).
That's a direct restatement of the algorithm that you implemented (albeit in a slightly idiomatic FP way)

(reduce + (filter even? (take-while #(< % 4000000) fib-seq)))
E D A B C

And this code, which leverages the fib seq code is easy too:
A: Look at the numbers in the fib-seq(C) which are less than 4000000 (B)
D: keep the even ones
E: add them up.
That's a direct restatement of the problem: add the even fib numbers which are less than 4000000.

So I find the Clojure code at least as readable as yours.

Sat, Oct. 17th, 2009 08:10 pm (UTC)
stigant

It's also significantly more modular and hence flexible and maintainable as well. I might note, for example, that your code has an error in it - it adds up all the fib numbers instead of the even ones. This is simply fixed in the Clojure code by adding a (filter even ... bit. In your code, it will be harder to notice and fix because while I'm looking at the low level details of your programming-language-dependent implementation rather than parsing natural English sounding instructions, I'm likely to miss the fact that you didn't include anything to filter out odd numbers.

Your code is less extensible. Consider the following variations on the problem that are suggested by the problem description:
- Add the first 100 fib numbers
- Multiply the first 100 fib numbers
- Add the first 100 prime fib numbers
- Add the second 1000 prime fib numbers
All are easily, and naturally, implemented leveraging and recombining the code for the fib sequence and the routines that filter, add, multiply etc. Since your interleaves the generation of the fib sequence with the code that uses it (ie the adding part), all of the code will need to be duplicated for the new programs.

Had you taken a more functional approach to generating the fib sequence (for example by defining a fib function which maps integers to integers, or by implementing a list/stream), your code would be much better. But these techniques are inherently more difficult in imperative languages. For example, lazy evaluation (which you get for free in Haskell, and with a keyword in Clojure) would require several more lines of code which are difficult to understand to the beginning programmer. A general purpose lazy implementation would be impossible in any imperative language since evaluation order becomes important when you allow state to mutate. Furthermore, I expect you will have a hard time making everything thread safe in such an implementation.

Sat, Oct. 17th, 2009 08:25 pm (UTC)
bramcohen

The lack of filtering for even number is due to me having missed that in the problem statement. Adding an if for it is completely trivial.

I don't know what you're babbling about thread safety. None of these examples have anything to do with thread safety, and trying to make thread safety be embedded into code itself rather than using semaphores is just stupid.

Sat, Oct. 17th, 2009 08:41 pm (UTC)
stigant

>> Adding an if for it is completely trivial.
Sure, but missing the point. ie it makes your code less readable, maintainable, and flexible.

>>None of these examples have anything to do with thread safety,
I was providing that as an example of a way to extend the program's usefulness (ie flexibility). You will have a hard time implementing the fib seq as a list in a way that is thread safe because it will require state changes which will have to be surrounded by semaphores. With the functional/lazy approach you get thread safety for free, no extra effort - no need to embed it in the code. The alternative is to embed the fib seq generation code in your processing code (something I consider to be just as stupid as embedding thread safety) as you have done. Unfortunately, that requires that part of the program to be duplicated for every fib-seq consuming application.

Sat, Oct. 17th, 2009 08:13 pm (UTC)
bramcohen

My post doesn't contain any comments about the clojure code whatsoever.

Sat, Oct. 17th, 2009 08:36 pm (UTC)
stigant

No, but you extrapolated the poor python code to statements about all functional languages.

Sat, Oct. 17th, 2009 09:27 pm (UTC)
bramcohen

You should go re-read my post a bunch of times until you actually parse what I said

Sat, Oct. 17th, 2009 11:21 pm (UTC)
stigant

All right, I did misread your post. I still disagree with your conclusion about thinking like a functional programmer/teaching functional programming to beginners. One certainly needs to be careful when trying to apply functional techniques in a non-functional language. While the python code is pretty indefensible, it does demonstrate that the programmer is thinking about the extensibility of his program. Yes, he has to bend over backwards to implement lazy lists, but the end result (assuming that pile of code ends up allowing him to write code like the Clojure sample) is that he has a modular way to process the fib seq, in the same way that the Clojure sample does - something your code does not accomplish. He's guilty of swinging for the fences when he should be bunting. But the functional thinking can also lead to nicer code (the Clojure sample is much cleaner than any of the imperative code you wrote). This tells me that the functional approach has its merits.

In my experience, programming in a functional language allows the programmer to concentrate on the problem that needs to be solved rather than the details of how the computer is going to handle the data. This is a trait that we should be fostering in all programmers. I think this code suggests:

1. We should also do a better job of teaching people to program in imperative languages (I would say AFTER we teach them how to think in functional languages). This would mean finding more robust ways to translate functional ideas into imperative languages.

2. Mainstream languages would do well to develop some libraries/extend their syntax to support functional ideas in easier ways. The lazy-list handling code should be moved into a library for example to allow the python programmer to use it to write cleaner code in other places. But more generally, they need better/more succinct abstraction tools. As you pointed out in another post, using classes/objects is often like hammering in a nail with a file cabinet.

3. We should develop ways to compile functional languages into mainstream languages. That way, people who grow up thinking functionally (a good thing) can make an easier transition into working with mainstream languages when they enter the workforce. I've been told that there is a well optimized Scheme->c/c++ compiler that gets very good performance (although it is quite slow in the compile time) out of the final code.