Computing a Cartesian Product with LINQ

And here we have yet another post inspired by a question on StackOverflow: how do you compute the Cartesian product of arbitrarily many sequences using LINQ? (*) UPDATE: Ian Griffiths has an interesting series of articles that approaches this question in considerably more depth than I do; check it out! First off, let’s make sure…

18

Every Program There Is, Part Nine

[This is the final part of a series on generating every string in a language. The previous part is here.] We seem to have a bit of a performance problem here. We could slap a profiler on it, and normally I’d recommend just that. But in this case, let’s solve this problem by thinking. Suppose…

3

Every Program There Is, Part Eight

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] OK, first things first. Let’s assume that we have a string that contains a grammar that has already been rewritten into our “nice” form, where there are exactly two terms in every…

1

Every Program There Is, Part Five

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] Last time: Clearly we have reduced a problem of size k to multiple problems of size less than k-1, and so this is amenable to a recursive solution. Right? Wrong. (The “clearly”…

4

Every Program There Is, Part Four

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] Remember, the point of this exercise was to come up with a device to help me test parts of my compiler. To test binary trees as we saw we can generate all…

9

Every Tree There Is

[This is part of a series on generating every string in a language. The previous part is here. The next part is here.] Last time we talked about how the number of binary trees with n nodes is C(n), where C(n) is the nth Catalan number. I asked if there were more or fewer trees…

19

Every Binary Tree There Is

[This is the first part of a series on generating every string in a language. The next part is here.] The other day I wrote a little algorithm that did some operation on binary trees. I wanted to test it. I whipped up a few little test cases and it seemed fine, but I wasn’t…

47

Immutability in C# Part Seven: More on Binary Trees

Lots of good comments on my previous post. To briefly follow up: One of the downsides of immutable tree implementations is that usually the tree must be built from the leaves up, which is not always convenient. We’ll look at implementations which hide this fact from the user in future posts. One smartypants pointed out…

21

Immutability in C# Part Six: A Simple Binary Tree

OK, we’ve gotten pretty good at this by now. A straightforward implementation of an immutable generic binary tree requires little comment on the basics. A binary tree is either empty, or a value, left tree and right tree: public interface IBinaryTree<V>{    bool IsEmpty { get; }    V Value { get; }    IBinaryTree<V> Left { get;…

13

Why does a recursive lambda cause a definite assignment error?

Hey fabulous readers, sorry for not much blogging lately. Between implementing LINQ and making plans to attend my first Burning Man, there’s been no time for anything. We’ve had lots of new ideas generated here for the type inferencing algorithm which I will discuss in detail when I get back. For now, here’s a question…

7