[plt-scheme] Project Euler was Hash Table implementation
Mark, why don't you try two different things:
1. use the srfis for lazy streams and comprehension to rewrite the
solutions
2. use Lazy Scheme and hack together a comprehension macro.
These are interesting design experiments that Matthew can use for his
comprehension work and you could report on it with a paper at the
next Scheme workshop, which will be in the US. I bet that Bruce (also
in Seattle) would love to "play" with you on this code and experiment.
-- Matthias
On Aug 3, 2007, at 4:55 PM, Mark Engelberg wrote:
> 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
> _________________________________________________
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme