Intro to Trees
There is only one data structure in Hoon: the binary tree.
Everything is a binary tree in Hoon.
Hoon code itself is a binary tree! ...but don't worry about that yet.
Let's have a quick refresher on binary trees, a general purpose data
structure that is used all over, not just in Hoon.
A binary tree consists of nodes, starting with the root node. In the
general case, each node (a) contains a value, (b) has 0, 1, or 2
children. Or, rather, every node has pointers to 2 children, but
either of these pointers can be NULL / empty / whatever. There are no
cycles (i.e. no loops).
You have certainly dealt with trees before. HTML, for example, is a
tree (although not a binary tree). E.g.
this is the first div
is a root node ( html ) with four children (h1, div.a, div.b, div.c).
The second child (div.a) has a lot going on: an id ('a'), content
("this"), and a child ("span").
Hoon has a MUCH simpler structure.
First, it's a binary tree: every node can have 0, 1, or 2 children.
Second, there are no attributes (like HTML "names" or "ids").
Third, a node either has content, or has children, but never both.
Also, we call nodes "cells", and we call trees "hoons". Yes, the name
of the core data structure is the same as the name of the language,
except the word for the data structure has a lowe case 'h', while the
language name has an upper case 'H'. I do not defend this; I merely
report on it.
Let's look at a Hoon style binary simple tree:
This is a tree with one cell (the root) which holds the value 3, no left child, and no
Here's a Hoon tree with three cells:
Here's a Hoon tree with seven cells:
/ \ / \
3 12 1 5
These ASCII art diagrams are tricky, and there's a much more compact
notation, using square brackets. The above tree can be expressed
[[3 12] [1 5]]
Trees need not be balanced; this is a legitimate tree:
This tree is expressed
[3 [1 5]]
A very common use of trees in Hoon is a very very unbalanced
right-heavy tree, like this:
All linear structures are implimented in trees this way. Where you
would use an array in C or Ruby, you'll use a tree in this manner in
Hoon. You should simultaneously think of such a usage as "a list",
but also remember the underlying implementation.
This is expressed on one line as
[ 3 [1 [5 [22 99]]]]
Because this is a very common usage model, though, there is an
alternate expression syntax:
[3 1 5 22 99]
Your brain is going to look at this and think "that's a tree with a
single root cell, and it has five children cells". Yes, that's what the
syntax seems to imply.
No, that's not what it means.
I know that this is kind of painful, but you have to accept that the
above syntax means the diagram above, NOT a root with five children.
When you realize that that unbalanced right-heavy tree is USED in the
same way that an array is, the syntax becomes a bit less painful.
The interpretter (dojo) accepts both syntaxes, but only emits the
So, let's recap:
* everything in Hoon is a binary tree ... EVERYTHING !
* we also call binary trees "hoons", with a lower case 'h'.
* binary trees are made up of cells
* a cell either (a) holds a value and has zero children, or (b) does
NOT hold a value and has 1 or 2 children.
* cells do not have HTML- or XML- style attributes associated with them
(this is kind of the truth and kind of a white lie; I'll explain
Your homework assignment:
* get urbit installed on your PC following the instructions here
* boot into a comet. Note that you must do this in a basic terminal;
it will NOT work inside an emacs shell.
* read the official explanation of nouns, cells, and atoms here
* in your urbit, use dojo (the interpretter) and enter some hoons:
[[1 2] [3 4]]
[10 20 30 40 50]
Note that the dojo interpretter is very opinionated, and will enforce
one space between values. I do not defend this, I merely report it.