Arrays in scheme / Memoization

3
votes

How can I use arrays in Scheme?

In particular, I'm attempting to implement a recursive fibonacci procedure using memoization. Do arrays even exist in Scheme?

If not, how can I implement memoization?

2
schemeracketdynamic-programmingmemoization
For such questions it is often very useful to specify which implementation you're using. Memoization is common enough in Scheme that most implementations would come with some library. - Eli Barzilay
I had the implementation as a tag, but it seems sgm edited it out (probably rightly so as I think I was creating the tag by using it). I'm using Pretty Big Scheme (DrScheme). - Cam
Actually, I just chose PBS from DrScheme's Choose Language menu - I have no idea which one I should use. Apprently PLT and r5rs are popular? - Cam
In this case you should have used plt-scheme as the tag. - Eli Barzilay

2 Answers

5
votes

There are arrays in Scheme, but they are called vectors. Be aware that they don't resize like they do in other languages like Perl and Javascript, or the like-named C++ thing; you have to make a bigger one and copy the contents of the obsolete one over.

If you want to know more about memoization and dynamic programming in particular, you can read chapter 12 of the free book Concrete Abstractions.

1
votes

This is not a direct answer, so feel free to downvote etc: if you're using PLT and you need memoization then you should look at Dave Herman's memoize package. Also, you could grab the memoize function from the swindle library.