Scala for Project Euler | Hacker News Reader

Scala for Project Euler

pavelfatin.com

37 pointsisomorph16 comments

I just watched a great talk about Scala yesterday by Dean Wampler called "Seductions of Scala"

I've never felt comfortable about functional programming, (I still have nightmares about Prolog from my AI class at uni), but the way Scala mixes OO with the conciseness of FP felt good.

The Actor message model is ripped straight from Erlang, which is well respected, and features liked mixins appealed to my C++ heart.

Scala is on the list of stuff to tinker with over xmas now along with node.js and Go .

I love ML and Scala. Couldn't get my head around Prolog. Gonna flunk the exam. Lol.

Thanks for that link. I only knew the $100 o'reilly version until now. :)

Holy cow, those solutions are tiny. They make me feel small and inadequate. Once I'm comfortable with functional programming, those solutions become readable? Or is it a fundamental truth about functional code that it tends to be concise but suffers in terms of being able to easily see at-a-glance what it's actually doing?

No, a large part of your problem is fluency. The ability to read code like this, code written by someone whose knowledge is more advanced is a matter of literacy. Your 'vocabulary' doesn't match his (his is larger). Further, all languages have some degree of idiomatic expression. Such expression tends to be pretty much opaque to beginners or even mid level programmers until the necessary 'ah ha!' moment. Keep at it--- likely by the time you finish up the list of challenges, you will not only want to re-write your initial work but will have a much better understanding of the code shown.

You're up against two challenges: Understanding functional programming, and understanding Scala's syntax. Without grounding in either, the solutions will look doubly opaque.

But there is a consistent vocabulary that shows up in functional programming, things like: map, reduce, fold, take, lambda, etc. You also need to understand lazy data structures. Once you have those ideas under your belt, a lot of the early Euler solutions are fairly obvious, and will wind up looking essentially identical across languages.

None of this is very difficult on its own, especially for someone with actual development experience like yourself. Are there any specific answers that you find particularly confusing? I'd be happy to translate them into Python or pseudocode and explain what's going on -- I promise it's not as crazy as it looks.

There is no need to feel small. It is just using declarative constructs that require imperative code in non-functional languages.

A great blog entry about getting started with all of this is the following: http://blog.stefandeboey.be/34563653

The author shows a functional way of achieving something and afterwards shows the Java-version of the same code.

As an example, say you have a List of Person-objects:

persons.foreach({ p => println(p.name) })

is the same as

for (p : persons) System.out.println(p.name);

What if you want to extract the persons name and have them as a list?

persons.map({ p => p.name })

the imperative version:

Collection<String> names = new ArrayList<String>(); for (p : persons) names.add(p.name);

Note that you can omit the "." and "(",")" for method invocations in Scala, because the compiler will add them automatically. This means that

persons.foreach({ p => println(p.name) })

can be reduced to the following:

persons foreach { p => println(p.name) }

Another nice addition is the fact that Scala adds a "default variable name" that represents current element of the colleciton you're iterating over. The variable to use is the underscore "_". This means the code can be even more concise:

persons map { _.name }

As seen above the map function is used to somewhat transform one data-representation (the persons list) into another (a list of names of these persons.

All you need to do to achieve this, is supply a function that helps this transformation process to perform the actual transformation step. The power lies within the fact that you dont need to give a damn about how to iterate over the persons list. You just tell Scala the "WHAT" and now the "HOW".

All that being said, for more information on the subject, you should definetly check out the blog post mentioned above. It does a great job at explaining this in more detail and with other examples.

Not surprisingly, functional solutions to problems are often like mathematics solutions. Reading through them takes more time but for those in the know it'll be much more efficient.

I can read most procedural programs like I was reading a novel. Just read each line without thinking a lot about specifics, and the whole picture kinda paints out in front of me. It's a mistake I also often make that I try to read programs written in the FP paradigm (or math!) the same way.

I'm pretty comfortable with functional programming, but have never touched Scala, and after a quick skim through I can get a pretty good sense of what's going on in most of the problems. The beauty of functional programming is that there is so much richness in the abstractions. If you see a 'for' or 'while' loop there's no way to tell what it's doing, but just seeing map, reduce (foldl, foldr), filter etc I know a lot more about what's going on.

compare http://haskell.org/haskellwiki/Euler_problems - you're just unfamiliar with the functional idiom

A particularly opaque example of density: http://haskell.org/haskellwiki/Euler_problems/11_to_20#Probl...

  problem_18 = head $ foldr1 g tri 
  where
    f x y z = x + max y z
    g xs ys = zipWith3 f xs ys $ tail ys
    tri = [
        [75],
        [95,64],
        [17,47,82],
        ... snip ...

Compare this with two python solutions. The first was when I was learning python and is similar to how I would solve it in C. The second is a copy of that haskell solution:

  tri = [[75],[95, 64]...]
  maxes = [x[:] for x in tri]
  for y in range(len(maxes)-2, -1, -1):
    for x in range(len(maxes[y])-1, -1, -1):
      maxes[y][x] = maxes[y][x] + max(maxes[y+1][x], maxes[y+1][x+1])
  print maxes[0][0]

  print reduce(
    lambda y, x: map(
      lambda(t): t[0] + max(t[1], t[2]),
      zip(x, y, y[1:])),
    tri[::-1])[0]

I find the first one much easier to comprehend even though they do the same thing and use the same general algorithm of reduce()ing the rows. In general, I find procedural code much easier to read when I take a look at it months down the line.

Forget "Hello, World", Project Euler is the way to test drive a new programming language.

It's a very good means for some attributes of a language (I've done a handful in 3 or 4 languages), but it doesn't tend to exercise any object-like behaviors or give you any idea of how the language helps you manage complexity. Lots and lots and lots of practice with arrays and core math libraries, a smallish chunk with strings and even less file IO, but not a whole lot else. The utility of PE for language testing / fluency drops off dramatically after a short while, and starts being almost exclusively about the algorithms, which translate almost identically across similar language types.

Agreed. Haskell is amazing at Project Euler... but it doesn't prove anything about it's real world applicability.

Most of the problems challenge your skills in algorithm design rather than your knowledge of mathematics.

I completely disagree. Once you get past the beginning few problems you'll find that a large spread of esoteric and high-level mathematical knowledge is required.

Reply on news.ycombinator.com