Browse by Tags

Tagged Content List
  • Blog Post: 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...
  • Blog Post: 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 we’re trying...
  • Blog Post: 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...
  • Blog Post: 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” was...
  • Blog Post: 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 trees of size one, then all...
  • Blog Post: 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 – not restricted to binary...
  • Blog Post: 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 quite satisfied. I was pretty...
  • Blog Post: 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. ...
  • Blog Post: 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;...
  • Blog Post: 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...
  • Blog Post: Recursion, Part Six: Making CPS Work

    JScript doesn't support CPS natively but we can write another dispatch engine that makes it work. There's only ever one active continuation, so lets have a new rule: JScript CPS functions are allowed to return, but the last thing that they do must be to tell our dispatch engine what the continuation...
  • Blog Post: Recursion, Part Five: More on CPS

    Suppose we wanted to write this by-now-familiar little function in continuation passing style: function treeDepth(curtree) { if (curtree == null) return 0; else { var leftDepth = treeDepth(curtree.left); var rightDepth = treeDepth(curtree.right); return 1 + Math.max(leftDepth, rightDepth); } } ...
  • Blog Post: Recursion, Part Four: Continuation Passing Style

    We're getting hung up on the stack management aspects of recursive programming. Why do we need a stack at all? What purpose does it serve? If you're like most developers, you probably learned about subroutines and functions at an early age. The idea is pretty straightforward. You stop what you're...
  • Blog Post: Recursion, Part Three: Building a Dispatch Engine

    There's a particular technique that I like to use to solve problems -- it doesn't always work, but when it does, it can produce programs of surprising elegance and power. The technique is this: if you have a specific problem to solve, solve a more general problem, and then your problem is just a special...
  • Blog Post: Recursion, Part Two: Unrolling a Recursive Function With an Explicit Stack

    That recursive solution is pretty cool, to be sure. But there is one big problem with it. Consider this Jscript program that puts a few more nodes into our tree from last time: function tree(value, left, right) { this.value = value; this.left = left; this.right = right; } for (var i = 1 ; i < 1500...
  • Blog Post: Recursion, Part One: Recursive Data Structures and Functions

    The first thing to wrap your head around is recursively defined data structures. Let's start with something simple. Think about the abstract idea of “list”. Most people think of a “list” as an ordered collection of “items”, one after the other, with a beginning and an end. That’s a very non-recursive...
  • Blog Post: Recursion, Part Zero

    I’ve mentioned recursive programming techniques several times over the years in this blog ( Topological Sort , How Not To Teach Recursion , Fibonacci Challenge , Recursion and Dynamic Programming , Sometimes Breadth Is Better Than Depth , and probably a few others). A lot of developers, particularly...
  • Blog Post: re: Bad Recursion Revisited

    I have heard the tendancy for programmers to love these tiny, jewel-like, over-clever expressions called "APL Syndrome", as APL particularly encourages that style of programming. However, googling that for the origin of the phrase results in an avalanche of pages about antiphospholipid syndrome...
  • Blog Post: Bad Recursion Revisited

    We have internal email lists for questions about programming languages. Here's one that came across recently that I thought illustrated a good point about language design. An interview candidate gave the following awful implementation of the factorial function. (Recall that factorial is notated "n...
  • Blog Post: Breadth is sometimes better than depth

    A while back the Scripting Guys blogged about using recursion to list all the files in a directory and all its subdirectories. Something that you'll notice about this very standard solution to this problem is that it is "depth first". That is, it lists the files like this: c:\xyz.txt c:\foo\bbb.txt c...
  • Blog Post: Recursion and Dynamic Programming

    Back in May we were discussing the merits and drawbacks of recursive programming techniques -- that is, writing functions which break down problems into sub-problems, and then call themselves. The drawback of such an approach is that in some cases, you end up doing way more work than necessary...
  • Blog Post: Results Of The Fibonacci Challenge Are In

    Another bunch of good replies to my challenge of yesterday. And again, a bunch of answers that I didn't expect, and some of the points that I was thinking of weren't mentioned. People seem to like this more conversational format; I'll probably use it more in the future. Three readers had conjectures...
  • Blog Post: How Not To Teach Recursion

    A Joel On Software reader asked the other day for examples of recursive functions other than old chestnuts like Fibonacci or factorial. Excellent question. I suggested topological sort , of course, but there are plenty of other examples that are way better than the Fibonacci numbers. Why do I think Fibonacci...
  • Blog Post: Revenge of The Cycle Detector

    Mike Schinkel takes even longer to get to the point than I do, and that's saying something! Mike tells a long story about another application of partial order sorts , and asks how to modify the partial order sort algorithm so that it has a new property. Namely, in addition to returning a list ordered...
  • Blog Post: Attack of the Undead Cycle Detector

    My old friend Rob made some comments on yesterday's post which deserve to be called out: Consider a software application that is extensible with plug-ins. If some of the plug-ins are dependent on others, then a partial sort is required to determine the order in which they are loaded so that...
Page 1 of 2 (26 items) 12