Hacker News Reader

Comment by bunderbunder | Hacker News Reader

The best point to be made from this isn't that it's more computationally efficient. It's that, compared to something like

  sum [x | x <- [1..999], (mod x 3 == 0) || (mod x 5 == 0)]

which is really just bluntly translating the question into a programming language and letting it take care of the rest, your approach involves some actual insight into the underlying math.

View on HN

You can do the same in Python, which steals Haskell’s list comprehension.

By the way doesn’t the original problem say exclude multiples of 15?

IMO Python’s generators and coroutines are one of its most useful yet least appreciated features. Being able to suspend a function, resume it, get values from it, send values or exceptions to it is a highly powerful feature. You can use them to implement user-space cooperative threads, write a scheduler for that, implement message-passing concurrency, and do highly efficient multiplexed I/O in the style of asyncio.

and Python got this from....? (which language)

Well Python got it from Haskell. I thought I made it clear enough.

See https://docs.python.org/3/howto/functional.html

Well years ago, I saw a discussion that put this in the context of python's generators being inspired by what was in Icon.

I'm just now looking at Icon code for the first time, but, to me, Python's list comprehension syntax looks more similar to Haskell's than Icon's.

Right. We don't actually know whether this Haskell code is less efficient - that depends entirely on the implementation.

Compared to grandparent's method of calculation (9 multiplications, 3 additions, no comparisons, no iteration), the Haskell code is almost certainly less efficient. I can't imagine the Haskell maintainers would spend time on an optimization that is so impractically purpose-specific.

I don't think it's unreasonable to expect it. E.g. clang -O1 (https://godbolt.org/g/7qzSF9 ) is able to use the closed form for a sum on a simple C++ loop. It's not unreasonable that a language with deeper introspection could identify more closed forms. I agree that I don't think the Haskell maintainers would put this specific example in, but I wonder whether they could build it up from simpler primitives.

Haskell optimizer does not feature an arithmetic Oracle nor polynomial optimizer. It cannot even optimize Peano arithmetic much less a series.

This might be fixed some time or never. There is little push for ultimate performance and actually identifying arithmetic forms in recursive loops in the front-end is hard. (Heck it sometimes fails to tail optimize.)

I'd be interested to see how this weighs out in 5-10 years. Since there's no I/O here, I don't see why a clever compiler writer couldn't optimize this whole expression away at compile time, generating an executable just prints a constant.

What language is this?

Haskell

It’s a Haskell list comprehension. You read it as:

The sum of x for x from one to 999 where x mod three is zero or x mod five is zero.

well, the bit in square brackets is a comprehension. `sum `is just ordinary function application.

Reply on news.ycombinator.com