[plt-scheme] Project Euler was Hash Table implementation

From: Jos Koot (jos.koot at telefonica.net)
Date: Fri Aug 3 18:40:14 EDT 2007

Hi Mark,
I did a number of Euler problems in PLT Scheme.
Streams are readily available in PLT scheme (lib "40.ss" "srfi").
Therefore I think PLT-scheme does satify your second criterium.
Moreover (odd) streams are so easily made in R5RS that I did not even use (lib 
"40.ss" "srfi") for Euler problems.
Streams are not the only solution to attack infinite sets or sets of 
unpredictable size. Did you see the beautyful piece of serializing code Matthias 
Felleisen showed us in another thread? (auxiliary macros)
As for the comprehension: less characters do not automatically increase 
comprehension.
Take APL as an example: very short code, but much of it unreadable (mho)
As far as the parenthesis problem as often raised against Scheme and Lisp (: not 
by you :) it is a non problem.
Good luck with your Euler problems.
Jos Koot

----- Original Message ----- 
From: "Mark Engelberg" <mark.engelberg at gmail.com>
To: "David Einstein" <deinst at gmail.com>
Cc: "PLT Scheme" <plt-scheme at list.cs.brown.edu>
Sent: Friday, August 03, 2007 10:55 PM
Subject: [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
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> 



Posted on the users mailing list.