Hacker News Reader

Comment by Veedrac | Hacker News Reader

This has nothing to do with functional programming. Here's an iterative Python solution that's almost a direct translation but uses explicit iteration and avoids `filter`/`map`/etc.

    from itertools import permutations

    def n_queens(n):
        for p in permutations(range(n)):
            if len({c + i for i, c in enumerate(p)}) == len({c - i for i, c in enumerate(p)}) == n:
                yield p

View on HN

Python 3's `yield from` lets you write that in one statement:

    def n_queens(n):
        yield from (p for p in permutations(range(n))
            if len({c + i for i, c in enumerate(p)}) ==
                len({c - i for i, c in enumerate(p)}) == n)

It also illustrates how much neater list comprehensions can be in Python versus map/filter since its lambda functions are fairly verbose (even though there's a straightforward correspondence between them):

    def n_queens(n):
        return filter(lambda p:
            len(set(map(lambda x: x[1] + x[0], enumerate(p)))) ==
                len(set(map(lambda x: x[1] - x[0], enumerate(p)))) == n,
            permutations(range(n)))

Or you can just `return (p for p in ...)`.

Looks quite functional to me. Except that it uses "for comprehension" instead of map/filter (a matter of preference).

Well then functional doesn't mean very much :P.

Python's iterators are mutation-based, so not really functional. `yield` is based around pause-resume of function execution, so not really functional. `permutations` is just a function that wraps a list (or iterator coercible to one (which mutates the iterator)) and returns a (mutable) iterator.

A `for` comprehension desugars to a `for` loop with `yield` if it's a lazy comprehension, `append` if it's a list comprehension or `add` if it's a set comprehension, which of course involves mutation.

Basically nothing here is mutation free. That, at least IMO, means it's not functional.

You seem to be confusing interface and implementation. Lazy lists and for comprehensions appeared in functional programming languages first; and that Python code looks to have borrowed them.

Addition appeared in imperative languages first. Does that mean addition is imperative?

It's great that functional languages were first to catch onto these ideas, but that doesn't mean that anything else that uses them becomes functional. The interface isn't even functional, since in code like

    foo = iter((1, 2, 3))
    {x for x in foo}

`foo` is mutated. No "true" functional language would accept that ;).

Addition, as implemented by Python, is functional. There are no side effects. A fully imperative encoding of addition would be eg. the x86 add instructions. John Backus gave us "functional" arithmetic with Fortran, but realised all values should should be treated this way, not just numbers. I take your point about the iterators being mutated and the loss referential transparency. That's certainly not functional programming.

> Addition, as implemented by Python, is functional.

Sure, but Python wasn't the first imperative programming language. (An aside: that's not strictly true anyway; the error thrown when you do 1 + [] is a side effect.)

Functional typically implies higher-order functions, of which there are none in that Python code.

There is no well defined definition of functional programming. Since almost every mainstream imperative language supports higher-order functions, I would suggest that criteria is inadequate. A better definition is programming without side-effects.

Output is a side effect.

Not in Haskell and other pure languages. Pure functional programming is used to construct larger programs from smaller ones, which only when finally executed by the runtime produce output.

Are there any programs that produce output before they are executed?

It is not easy describing pure functional programming in two sentences. I encourage you to read up on it yourself. Again, IO is not a side-effect in pure languages such as Haskell. And again, the absence of side-effects best defines functional programming, not any particular feature, which imperative languages can and do steal.

Reply on news.ycombinator.com