A bit shorter on time today, so I’ve just got a quick library that I worked out to solve another problem (I’ll post it later this week when it’s actually working). Basically, when you need to store a heck of a lot of binary flags and don’t want to waste space, the best way to do it would be as one long list of bits. It’s really easy to do in a language like C, but how can you do it in Racket?
JP's Blog
Memoization in Racket
Memoization is awesome!
I’ve already written one post on the subject in Python, but this time we’ll do the same in Racket. It’s particularly timely as without it, today’s post on determining the number of prime partitions of a number would take longer to run than I care to wait.
Dictionary tries in Racket
For the next few posts, we’re going to need a way to represent a dictionary. You could go with just a flat list containing all of the words in the dictionary, but the runtime doesn’t seem optimal. Instead, we want a data structure that lets you easily get all possible words that start with a given prefix. We want a trie.
Evaluating prefix/infix/postfix expressions
In yesterday’s post, I talked about three different ways to write expressions: prefix, infix, and postfix expressions. I also promised to write up a web-based example that would show the guts of each algorithm in action. Well, here it is!
Use the three buttons at the top to switch between the different machines. Enter an expression in the box and click run to evaluate it. The only things that are supported at the moment are numbers (integers or floating point) and the operators +, -, *, and /, although the code is extensible enough that adding more shouldn’t be an issue.
Three ways to write expressions
(- (- (+ 4 (* 2 7)) (* (- 1 6) 5)) 1)
is the same as
4 + 2 * 7 - (1 - 6) * 5 - 1
is the same as
4 2 7 * + 1 6 - 5 * - 1 -
Madness right?