[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