Home

Sorting some strings

Following my previous

(2) on a fun little language called J (http://jsoftware.com/), I thought I'd do a quick writeup for some source code I provided in the Khan Academy Alumni slack channel.

Over the next few paragraphs we're going to sort some strings by length, and end up with a function that is 5 characters in length: \:#&> (really!)

   (\:#&>) ;: 'sorting strings by length'
┌───────┬───────┬──────┬──┐
│sorting│strings│length│by│
└───────┴───────┴──────┴──┘

🔗 Boxes of strings

We can use the ;: Words verb to get a list of words in a string.

   'a'; 'tall'; 'cat'
┌─┬────┬───┐
│a│tall│cat│
└─┴────┴───┘
   ;: 'a tall cat'
┌─┬────┬───┐
│a│tall│cat│
└─┴────┴───┘

The fancy characters around each word represent the fact that they are "boxed."

We can > Open boxes.

   > ;: 'a tall cat'
a
tall
cat

We can get the number of items in a list (or a string - which is a list of characters) using the # Tally verb.

   # 1 3 5
3
   # 'hello'5

We can compose these two operations with & Bond conjunction, which takes two verbs and returns a single verb.

   # & > ;: 'hello world'
5 5
   #&> ;: 'a tall cat'
1 4 3

Now we are able to get the number of characters in each string.

🔗 Sorting and ranking

\: Sort Down is a powerful verb which sorts the left argument using the right argument for scoring (in descending order).

For example, we can rearrange "hello" by giving l and h a score of 1 and 2 respectively, and giving e and o a score of 11 and 10 (respectively). e will then appear at the front of the result as it received the highest score.

   'hello' \: 1 11 2 2 10
eollh

We can use this to sort our list of words, using the length of each word as its score.

   #&> ;: 'a tall cat'
1 4 3
   (;: 'a tall cat') \: 1 4 3
┌────┬───┬─┐
│tall│cat│a│
└────┴───┴─┘
   (;: 'a tall cat') \: #&> ;: 'a tall cat'
┌────┬───┬─┐
│tall│cat│a│
└────┴───┴─┘

🔗 Making things shorter

We've successfully used the ;:, \:, #, &, and > operators to piece together a working sort mechanism, but there's one flaw - we have to repeat ;: 'a tall cat' twice

To alleviate this, we can use one of J's strongest features, hooks.

In the following example, we'll take a list of numbers and add 7% to each of them. We may be inclined to write it like so:

   10 40 55 + 0.07&* 10 40 55
10.7 42.8 58.85

Which reads, take the list 10 40 55 and apply 0.07&* (remember bond?) to each item. Add the result to the list 10 40 55.

(Author's note: we also may be inclined to just multiply by 1.07 but that requires math).

Hooks allow us to simplify this by simply leaving off one of the arguments.

   (+ 0.07&*) 10 40 55
10.7 42.8 58.85

How does this work? J recognizes that we have two verbs within our parentheses (+ and 0.07&*) and combines them into a "hook." When we place a single argument at the end, J automatically applies it to both sides of the hook.

Put another way: (f g) x <=> x f g x for any two verbs f and g (don't forget your parentheses!)

So, the following expressions are equivalent:

   10 40 55 + 0.07&* 10 40 55
10.7 42.8 58.85
   (+ 0.07&*) 10 40 55
10.7 42.8 58.85

Let's circle back to our sorting mechanism before and see where we can apply this.

   (;: 'a tall cat') \: #&> ;: 'a tall cat'
┌────┬───┬─┐
│tall│cat│a│
└────┴───┴─┘

Spot it? Between our two instances of ;: 'a tall cat' we have two verbs: \: and #&>. Let's hook 'em.

   (\: #&>) ;: 'a tall cat'
┌────┬───┬─┐
│tall│cat│a│
└────┴───┴─┘

Lastly, we can eliminate some whitespace and build our custom verb.

   sort =. \:#&>
   sort ;: 'a tall cat'
┌────┬───┬─┐
│tall│cat│a│
└────┴───┴─┘

🔗 We did it!

I hope this was a decently short and pleasant introduction into some fun features of the J programming language:

I encourage you to download J and play around with it. Hooks and forks and other trains pop up in all sorts of places and may make you think differently about the code you write everyday.

Thanks for reading