I’ve just discovered the following interesting and related facts:
1) Chickenfoot’s pattern matching is very error tolerant. If it looks for “Older posts” and can’t find it, it will cheerfully settle for “Newer posts”.
2) StumbleUpon histories only go back a few months.
3) When writing code, you should be really careful to avoid infinite loops.
Sigh.
bogo-sort: /boh`goh·sort´/, n.
(var.: stupid-sort) The archetypical perversely awful algorithm (as opposed to bubble sort, which is merely the generic bad algorithm). Bogo-sort is equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order. It serves as a sort of canonical example of awfulness. Looking at a program and seeing a dumb algorithm, one might say “Oh, I see, this program uses bogo-sort.” Esp. appropriate for algorithms with factorial or super-exponential running time in the average case and probabilistically infinite worst-case running time. Compare bogus, brute force.
A spectacular variant of bogo-sort has been proposed which has the interesting property that, if the Many Worlds interpretation of quantum mechanics is true, it can sort an arbitrarily large array in linear time. (In the Many-Worlds model, the result of any quantum action is to split the universe-before into a sheaf of universes-after, one for each possible way the state vector can collapse; in any one of the universes-after the result appears random.) The steps are: 1. Permute the array randomly using a quantum process, 2. If the array is not sorted, destroy the universe (checking that the list is sorted requires O(n) time). Implementation of step 2 is left as an exercise for the reader.
One function in the Haskell standard library is ‘fix’, the least fixed point operator (a sort of generalisation of the Y combinator). As per the topic, the entire source code for it is:
fix :: (t -> t) -> t
fix f = let x = f x in x
This is really awesome, but it took me a while to figure out how it worked.
Let’s take an example:
g x = 1 : x
ones = fix g
This gives us an infinite list of ones. However, it’s important to note that at this point nothing is evaluated.
Suppose I wanted to evaluate head ones. How would the evaluation proceed? It would go as follows:
head(ones) = head(1 : ones) = 1
No more of the argument is evaluated than needed. That’s what laziness means.
Now let’s see how we use it as Y combinator.
genfact f 0 = 0
genfact f n = n * (f(n-1))
(I’m aware my bracketing is non-ideal. I haven’t quite got the hang of reading and writing Haskell in a normal style yet though)
fix genfact 3 = genfact (fix genfact) 3
= 3 * ( (fix genfact) 2 )
= 3 * ( genfact (fix genfact) 2)
= 3 * 2 * ( (fix genfact) 1)
= 3 * 2 * 1 * (fix genfact 0)
= 3 * 2 * 1 * (genfact (fix genfact) 0)
= 3 * 2 * 1 * 1
= 6
Neat.
Or, in other words, why you have to check for a ‘referer’.
I encountered a neat little feature in javascript recently.
Javascript has things that look like global variables. They’re not. What they *actually* are is fields of the global object. The following syntax lets you write a bunch of code that uses a different global object:
with(foo)
{
// do Stuff
}
Has foo as the global object inside the braces.
Well, almost. There’s a caveat.
Try the following in Rhino or Spidermonkey:
foo = { bar : 2 };
with (foo)
{
baz = 3;
}
print(foo.baz);
It will print “undefined”.
But if you do
print(baz)
It will print 3.
Huh? What’s going on?
This is how javascript scope works. The assignment “foo = bar” will not find the identifier ‘foo’ bound, so will fall outwards into enclosing scopes until it finds a scope which does bind it, stopping at the top level scope (and corresponding global object) if it doesn’t find any.
It’s kindof annoying, but it does make sense. Further it’s more or less how it has to work given the combination of Javascript’s soft objects and lexical scoping.
With this caveat borne in mind, the ‘with’ method is quite cool. I shall try and find an excuse to use it in future. :-) (I encountered it via Chickenfoot, where it seems to be useful for loading other pages in the background and applying chickenfoot methods to them).
Update: Apparently this is deprecated and considered bad practice, as it’s difficult to optimise and leads to some non-intuitive issues with scoping. Oh well.