Monday 23 January 2012

Breaking stuff apart - Destructuring.

So... boooored. I might as well type up whatever I know about destructuring, which is... extremely, EXTREMELY useful, to say the least.

In fact, I know quite a bit about how to use it (not everything, though), but nothing about how it works under the hood. I only recently learned how lazy-seqs work (which, incidentally, is an interesting topic for another time).

So, destructuring.
If you recall, in my previous post I used something along the lines of
(defn reroot [tree [n1 & nr]] ...

Aaaand, here's destructuring. Instead of giving a second name for the second argument, I put [n1 & nr]. The second argument passed will be destructured into n1 and nr, where n1 holds the first element of that vector, and nr the other elements (that's what &, the rest argument is for). The funny thing is, this kind of destructuring can be arbitrarlily nested, which is powerful.
Really.

More examples:
(let [[a b c] [1 2 3]]
  (println a b c))
-> "1 2 3"

(let [[a b & c] [1 2 3]]
  (println a b c))
-> "1 2 [3]"

(let [[[a & b] & c] [[1 2 3 4] 5 6 7 8]]
  (println a b c))
-> "1 [2 3 4] [5 6 7 8]"

I'm currently writing a game, and I have a map that holds the entire game state. Pure functions act on that map, returning a new one with changes to the game world incorporated. There are many uses for destructuring there.

The world is made up of tiles. I use a map of vectors to maps for those tiles; the vector has two elements (x and y position), and the maps holds all data about the given tile. Now, when a map is ran through (seq), it returns a seq of two-element vectors - the first element is the key, the second one the value. Hence when drawing the field, I can do this:

(doseq [[[x y] tile] tiles]
  ...)

Yes, destructuring can be used in doseq and for. Even in let!
See, I destructured the input vector (which is, remember, a key-value pair) into [x y] and tile. Then, the first element is further destructured into x and y. That way I have access to all those important informations without having to manually extract them.

And this is destructuring for vectors only. Yes, there are other kinds.
But before I go into them, let me note one thing first. If, via destructuring, a name should be bound to some element, but there is none, those names are bound to nil:

(let [[a b c] [1 2]]
  (println a "/" b "/" c))
-> "1 / 2 / nil"

Alright. Destructuring MAPS. This is fun as well. See, in my game I rely on maps a lot. Units, for example, are maps holding all necessary information. In many functions, I don't need all of these informations, so some handy way to extract the ones I DO need would be... handy.
Behold.
(def unit
  { :power 1 :endurance 3 :name "Thing" :image nil :owner 1 :range 3 :position [2 2] })

(let [{name :name, owner :owner} unit]
  (println name "belongs to player" owner))
-> "Thing belongs to player 1"

And you can mix both types of destructuring.

(let [{name :name, [x y] :position} unit]
  (println name "is on field" x y))
-> "Thing is on field 2 2"

Again; if a key is not found in the map, nil is bound to the corresponding names.

So. Destructuring is awesome.
 
Words of warning, though. Overusing this makes code unreadable. Seriously. I usually try to avoid using this in defn parameter vectors, unless the function is trivial, but it really shines in for and doseq, and has it's uses in lets. I rely on it a lot to make those parts more concise.

Mazes and trees (sounds better than Clojure and Emacs, doesn't it?)

Some days ago I wrote a simple maze generator using depth-first search. It's really trivial, took much less space than my age-old Ruby implementation and - most importantly - made me play around with trees in Clojure.

Today, on a three-hour ride on the train I was bored. So my mind drifted off to my happy place (which, incidentally, is programming) and I started thinking about the aforementioned generator. I realized that all generated mazes could be represented as a tree (I... won't confess as to what data structure I used before.), so, upon further thought, I also concluded that path-finding between two points is trivial, assuming that one of the points is the root node... then I thought some more, and thought, "Hey! In the case of the maze it doesn't really matter WHICH node is the root node... so, I should be able to make a different node the root node without changing the structure of the maze at ALL."

Some mililitre of ink, some paper and quite some thoughts later...

It's definately possible. And, actually, not so hard.

1 -> 2
  -> 3
  -> 4 -> 5 -> 6
       -> 7 -> 8
            -> 9

Let's use this beautiful *cough* tree. Let's say we want to find the way from 4 to 3. The way is simple: 4 -> 1 -> 3. But it's not entirely clear from a data-structure point of view. So...

4 -> 5 -> 6
  -> 7 -> 8
       -> 9
  -> 1 -> 2
       -> 3

Upon closer inspection, what happened is very clear. All nodes UP from 4 were appended to the 4 instead. I don't feel like typing out another entire tree, but if there were more nodes above the 4, then all nodes above it would be in reversed order:

1 -> 2 -> 3 -> 4 -> 5
  becomes
3 -> 4 -> 5
  -> 2 -> 1
You see, 1 -> 2 became 2 -> 1.

So, that's about the entire theory - take all nodes up until the root, reverse the order,  and append that to the node you want to be the new root.

Let's implement it.

I assume trees built from vectors in the form of:
node => [[object] & nodes]
Which means the first item of each vector is basically anything (in our example these would be numbers), followed by any number of similarly-structured vectors.
[1 [2] [3 [4]]]
is equal to:
1 -> 2
  -> 3 -> 4
Because I was on a train at the time, and I couldn't recall any function to do it (nor use the clojure.repl tools very well) I wrote my own function to remove an indexed item from a vector, called "without". Basically...

(defn without [n v]
  (vec (concat (take n v) (drop (inc n) v))))

Nothing too exciting. Also, probably redundant.

At this point I was kind of stuck. I wrote something along the lines of this...

(defn reroot [tree [n1 & nr]]
  (if n1
    (conj (reroot (tree n1) nr) (without n1 tree))
    tree))

I used destructuring here (which I will go into in more detail in the next post), but here, it's enough to know that (reroot [tree] [1 2 3]) would have n1 = 1 and nr = [2 3].
Anyway, the first argument is the tree itself, obviously, whereas the second argument is the "path" to the new root node.
For example,
(reroot [1 [2] [3 [4]]] [2 1])
should result in
[4 [3 [1 [2]]]] 
since item #1 in item #2 of the original tree is 4.
Anyways, the code snipped above is wrong. I didn't really know why, I only knew I was doing something wrong. I was totally shotgunning it, putting a without there, removing one somewhere else, replacing it with a simple access-by-index... Until I thought - SCREW THIS, let's do it properly.

I wrote another helper function, I called it swap. It would swap (HAH!) the places of the root node and it's child node of index n:

(defn swap [tree n]
  (conj (tree n) (without n tree)))

Trivial enough.
I didn't explain yet why I use the without. Picture this tree:

1 -> 2 -> 3
  -> 4 -> 5

Calling swap 1 on it (index 1 is the 2 -> 3 branch) would result in this without the "without":

2 -> 3
  -> 1 -> 2 -> 3
       -> 4 -> 5

while it should be

2 -> 3
  -> 1 -> 4 -> 5

Now it's quite obvious; I use the "without" to achieve the effect of taking out the branch from the tree I'm appending to it.

Now return to our reroot...
(defn reroot [tree [n1 & nr]]
  (if n1
    (recur (step tree n1) nr)
    tree))
This works as intended.
But, this being Clojure, such a simple function in four lines? No way this is done. We can do it better.
And of course, the pattern is pretty obvious: some value that is modified repeatedly, according to some list passed along. Sounds awfully like reduce.
Hence, the final version:

(defn without [n v]
  (vec (concat (take n v) (drop (inc n) v))))

(defn swap [tree n]
  (conj (tree n) (without n tree)))

(defn reroot [tree path]
  (reduce swap tree path))

If this isn't elegant, I don't know what is*.
*If you ignore the part with that "without" for a moment.

Monday 16 January 2012

Clojure! Also, Emacs (I'm good with post titles.)

I recently (a few months ago?) started learning Clojure. It's a wonderful language. LISPs have fascinated me for a long time, I tried a flavor of Scheme in the past (Racket), but couldn't quite get into, despite my fascination for everything that family of languages stands for, with it's philosophy, it's appearance...

Nevermind. Clojure. I wanted to learn it. It promised a lot, parts of which I couldn't (and partially still can't) grasp the significance of, but as far as I can tell, it delivered.

I really could go all fanboy over it for significant, semi-infinite stretches of time (and my roommate just assumes it's going to be about Clojure when I tell him I have something interesting to say by now), so let's get back to earth.

So, installation. As it so often happens with this kind of awesome things, installation isn't quite that straightforward, in the Windows-sense of click, click, click some more, it runs. Actually, getting it to run under Windows was somewhat annoying.

I happen to run a Linux Mint VM, so I tried it there. I installed Emacs and tried to get SLIME/Swank to run (basically a neater REPL for LISPlikes), but numerous step-by-step tutorials have failed me, so I clean-installed Emacs and did everything by hand. Now, it's not the most "optimal", "comfortable" or anything like that setup, but the most important thing is, I'm wrestling with Emacs and Emacs Lisp myself (the latter being the reason I originally decided for Emacs over Vim, actually). It runs. There is this extremely awesome tool called Leiningen. It makes the entire thing much more comfortable than any graphical interface ever could. So does Emacs. But it takes some commitment.

I can only recommend the rough path, really. It's done me good so far.

I'll probably post some code snippets or stuff in the future. I dunno.