J: Self-reference in bubble sort tacit implementation
- by Yasir Arsanukaev
Hello people!
Since I'm beginner in J I've decided to solve a simple task using this language, in particular implementing the bubblesort algorithm. I know it's not idiomatically to solve such kind of problem in functional languages, because it's naturally solved using array element transposition in imperative languages like C, rather than constructing modified list in declarative languages. However this is the code I've written:
(((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: #
Let's apply it to an array:
(((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: # 5 3 8 7 2
2 3 5 7 8
The thing that confuses me is $: referring to the statement within the outermost parentheses. Help says that:
$: denotes the longest verb that
contains it.
The other book (~ 300 KiB) says:
3+4
7
5*20
100
Symbols like + and * for plus and
times in the above phrases are called
verbs and represent functions. You may
have more than one verb in a J phrase,
in which case it is constructed like
a sentence in simple English by reading
from left to right, that is
4+6%2 means 4 added to whatever follows, namely 6 divided by 2.
Let's rewrite my code snippet omitting outermost ()s:
((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) ^: # 5 3 8 7 2
2 3 5 7 8
Reuslts are the same. I couldn't explain myself why this works, why only ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) is treated as the longest verb for $: but not the whole expression ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) ^: # and not just (<./@(2&{.)), $:@((>./@(2&{.)),2&}.), because if ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) is a verb, it should also form another verb after conjunction with #, i. e. one might treat the whole sentence (first snippet) as a verb. Probably there's some limit for the verb length limited by one conjunction.
Look at the following code (from here):
factorial =: (* factorial@<:) ^: (1&<)
factorial 4
24
factorial within expression refers to the whole function, i. e. (* factorial@<:) ^: (1&<).
Following this example I've used a function name instead of $::
bubblesort =: (((<./@(2&{.)), bubblesort@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: #
bubblesort 5 3 8 7 2
2 3 5 7 8
I expected bubblesort to refer to the whole function, but it doesn't seem true for me since the result is correct.
Also I'd like to see other implementations if you have ones, even slightly refactored.
Thanks.
