[plt-scheme] Switching to Scheme

From: Mark Engelberg (mark.engelberg at gmail.com)
Date: Fri Jun 30 22:40:00 EDT 2006

I'm hoping to teach Scheme in the fall, so I thought it might help get
my brain back in Scheme-mode if I did some of my day to day
programming in Scheme.

These days, I do most of my programming in Python.  I'm looking back
over my code to see what kinds of Python features I'm using on a
regular basis, and thinking about how I'd do those things in Scheme.

1.  One of Python's primary data structures is called a list, but I
believe is actually an auto-resizing vector.  It supports fast
insertion and deletion from the end of the list, and constant time
access to the length of the list, and to any element.  I don't really
use the constant time access a whole lot (except perhaps for looking
up the length), so most of my code would convert just fine to Scheme's
list, except for one thing -- I find it very useful that when I
traverse a Python "list", the items are in the same order which I
inserted them into the list.  In Scheme, the items would be in reverse
order because you add and delete from the front.  Now, one option
would be to reverse the list before traversing, but that could be
inefficient if I alternate frequently between adding elements and
traversing the list.  It looks like I really need to implement a
queue.  Now I'm capable of implementing a queue on my own, but for a
common data structure on which I will be heavily relying I always
prefer to use a solution that's been well thought out and "peer
reviewed" to make it as efficient as possible.  For example, I
remember a very clever implementation of queues in Okasaki's
Functional Data Structures.  I did a search in the PLT Help desk for
"queue" but it didn't turn up anything.  Is there a hidden stash of
common data structures that might help me out here?

2.  All of my programs require heavy use of permutations and
combinations of sequences.  As far as I know, the C++ STL
implementation of next_permutation is the fastest algorithm for this.
But in Python, I generally use a simpler, non-destructive algorithm,
using recursion with lazy list comprehensions, which performs
reasonably well.  As always, rather than rewrite my own, I'd prefer to
use a standard library version of the algorithm.  Is there a hidden
stash of common algorithms that might help me out here?

3.  Speaking of lazy list comprehensions, SRFI 42 appears to only be
for eager list comprehension.  Is there a lazy version floating
around?  I use list comprehension syntax all the time, and would
sorely miss it if I couldn't use it (even though it's all convertible
to map/filter/etc.).

4.  Python's other primary data structure is a "dictionary" which is
essentially a hash table using immutable elements as the keys.  I use
this constantly, for memoization, and just generally storing large
quantities of information.  I see that MzScheme and SRFI 69 both offer
hash tables, so I don't expect this to be a problem as long as they
are reasonably efficient implementations.  Are there any gotchas about
the way hash tables are implemented that I need to be aware of?  For
example, does it work best if I convert my keys into immutable data
(so that an eq? test will suffice)?  If so, what is the simplest way
to convert a list into something immutable (Python has easy conversion
from lists to "tuples" which are immutable lists)?

5.  I use random numbers a lot.  Don't see any problem converting that.

6.  I do a fair amount of file input and output, some of which is
"pickling" the state of my computations and/or large data structures
to file for later resumption.  I know that Scheme has plenty of I/O
capabilities, but I'm not quite clear on how to do pickling.

7.  I generate a lot of tree structures and directed graphs.  Almost
certainly this stuff would actually come out a lot cleaner in Scheme.

So any advice on these issues would be most welcome.


Mark Engelberg

Posted on the users mailing list.