[plt-scheme] Project Euler was Hash Table implementation

On 8/3/07, David Einstein <deinst at gmail.com> wrote:
> Inspired by Jens and Grant, I decided to try my hand at some of the Project
> Euler problems using PLT scheme, to see what it was capable of.  It has
> proven itself capable on the few problems that I have completed so far, but
> I just ran into what appears to be a bug of sorts.  It appears that the
> hash-table implementation does not expand as more keys are added, and so if
> the table reaches a certain size things slow down dramatically.  For example

I've also had a lot of fun doing the Project Euler problems in various
languages.  I find it interesting to see which lanuage features are
useful for these sorts of programming exercises.  After solving a
given problem, you get to see how other people solved it in their
respective languages of choice, which is always interesting as well.
Some of my observations:

1.  You really want a language with good syntactic support for BigNums
/ infinite-precision / exact integers.  In Java/C/C#, you can use some
sort of add-on BigNum class, but the code starts looking ugly, and
poorly reflects the underlying math.
2.  For maximum reuse, streams are essential.  Many of the problems
have you searching a sequence of numbers for some property, and you
don't know in advance how many elements of that sequence you will need
to generate.  When you read through C solutions, they typically say,
"I started by generating the first 10,000 primes and trying to solve
the problem with those.  When that didn't work, I started over again,
but using a table of 20,000 primes..."  You really want to be using
streams, and a language with a rich set of constructs for combining,
filtering, and mapping streams.
3.  Comprehensions are wonderful syntactic sugar.  They noticeably cut
down the length of code while increasing clarity.  When reading
through the solutions, the shortest programs are typically in Haskell,
Python, J, or Mathematica.  The shortness of the J or Mathematica code
usually comes from some built-in function that suits the mathematical
problem.  The Haskell and Python code is short because of the
expressiveness of the languages, and the use of comprehensions.

Other things are of course important as well, but these are probably
the top three.  I have worked through many of the Project Euler
problems in Scheme, Haskell, Python, and Scala.

Scheme satisfies the first criterion, but not the second and third.
Of course, you can extend Scheme however you would like, but there is
no "off-the-shelf" solution for comprehension manipulation of streams.
 The syntax for vectors and hash tables are also more verbose than
their counterparts in other languages.  As a result, the Scheme
programs tend to end up on the verbose side, and is not my preferred
language for Project Euler.  (Scheme's built-in support for fractions
has come in handy on a couple of problems, however).

I have found Haskell to be a good fit for many of the Project Euler
problems.  I've run into problems, however, when I needed to use
memoization, or other non-pure optimization techniques.

Python works surprisingly well for Project Euler problems.  Many of
the "streams" can be expressed very elegantly as iterators using
Python's nice "yield" syntax (although you have to do a bit more work
if you want to cache the stream for multiple passes).  For problems
with a more "iterative" feel, or with a lot of string mainpulation,
hash table manipulation, or i/o, Python often feels more pleasant than
Haskell.

Scala allows you to write "iterative" or "recursive" style code
equally well.  It has functional and non-functional versions of most
data structures, including built-in support for comprehensions,
filter, map, etc. over both (non-functional) iterators a la Python and
(functional) cached streams a la Haskell.  Although ints are 32-bit by
default, the BigInt class is much less obtrusive than in other OO
languages because ints are auto-converted to BigInts if any of the
numbers in the arithmetic expression are of BigInt type (sort of like
the way Scheme's inexact numbers cause exact numbers to be converted).
 My main objection to Scala is that the static type system is fairly
complicated.  For these sorts of short programming tasks, it seems
unnecessarily verbose.

Anyone else want to comment on the relative strengths of languages for
Project Euler?

--Mark