views:

83

answers:

2

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<#)) ^: #

Here's the structure of the statement:

┌────────────────────────────────────────────────────────────────────────────┬──┬─┐
│┌───────────────────────────────────────────────────────────────┬──┬───────┐│^:│#│
││┌───────────────────┬─┬───────────────────────────────────────┐│^:│┌─┬─┬─┐││  │ │
│││┌──────┬─┬────────┐│,│┌──┬─┬────────────────────────────────┐││  ││1│<│#│││  │ │
││││┌──┬─┐│@│┌─┬─┬──┐││ ││$:│@│┌───────────────────┬─┬────────┐│││  │└─┴─┴─┘││  │ │
│││││<.│/││ ││2│&│{.│││ ││  │ ││┌──────┬─┬────────┐│,│┌─┬─┬──┐││││  │       ││  │ │
││││└──┴─┘│ │└─┴─┴──┘││ ││  │ │││┌──┬─┐│@│┌─┬─┬──┐││ ││2│&│}.│││││  │       ││  │ │
│││└──────┴─┴────────┘│ ││  │ ││││>.│/││ ││2│&│{.│││ │└─┴─┴──┘││││  │       ││  │ │
│││                   │ ││  │ │││└──┴─┘│ │└─┴─┴──┘││ │        ││││  │       ││  │ │
│││                   │ ││  │ ││└──────┴─┴────────┘│ │        ││││  │       ││  │ │
│││                   │ ││  │ │└───────────────────┴─┴────────┘│││  │       ││  │ │
│││                   │ │└──┴─┴────────────────────────────────┘││  │       ││  │ │
││└───────────────────┴─┴───────────────────────────────────────┘│  │       ││  │ │
│└───────────────────────────────────────────────────────────────┴──┴───────┘│  │ │
└────────────────────────────────────────────────────────────────────────────┴──┴─┘

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.

+1  A: 

I'm looking into it. In the meantime, are you implementing bubblesort because you need bubblesort specifically, or because you just plain need a sort (i.e. could you get away with using /:~ instead)?

EDIT: Have you tried running your bubble sort on a dataset like 3 1 2 9 2 9 86 5 9 6 9 6 45? The system hung when I tried it on my machine, but it works if you replace the ending # with a _.

estanford
I've been given a homework task: implement a client-server app, where client sends an unsorted list, the server receives that list, performs sorting and sends the resulting list back to the client. Actually, it doesn't make sense how sorting is implemented, but this manually implemented example would highly impress my teachers, because it turns out they use only imperative languages, and I'm 95% sure they haven't heard of J and other tacit languages! ;)
Yasir Arsanukaev
So the sorting method isn't specified? That's good news - the J sort operators /: and \: have a pretty sophisticated back end, and choose between the insertion sort, quicksort, and linear sort algorithms depending on the interpreter's optimal performance estimate for the given input data. Using the (/:~) verb train will give you professional-quality sort speeds with minimal effort on your part, which would hopefully impress your teachers with the language's power.
estanford
Sure, I'm aware of sorting functions included in J, but it's fun to implement things manually on early stages of studying. I'd also like to know if there are places J programmers hang out (IRC, forums etc) – hundreds of ones for C, Haskell, Python programmers.
Yasir Arsanukaev
The Jsoftware.com website hosts a J mailing list that might be worth looking into (archive at http://old.nabble.com/Re%3A--Jchat--Dynamic-currency-conversion-td28482538s24193.html) but it's not a forum per se. There's also a Google group and a facebook page, but I don't know of any other communities.
estanford
Back to your original question, could it be that removing the parens didn't matter because (function ^:) is a gerund? The $: operator might be deciding that the longest verb it's in comes to an end at the gerund ^:, in which case removing the parentheses around that verb statement wouldn't make a difference.
estanford
Yasir Arsanukaev
+1  A: 

According to this reference (175 KiB) conjunction is:

A part of speech that takes two arguments and typically results in a verb. For example, *:^:3 is a function that iterates squaring three times (^: is a conjunction).

As ^: falls into above-mentioned category, applying it to the arguments results in the longer verb:

((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)

Because $: denotes the longest verb that contains it, it refers to the code just written above.

Similarly, the next ^: makes a new longer verb from ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) and #:

(((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: #

which in turn is referred to by $: because it's longer than the previous one.

Since it's the undesirable behaviour, probably the only solution is to split the whole verb so that $: refers to the ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) though it's not a oneliner:

    bubbleiter =: ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#)
    bubblesort =: bubbleiter ^: #
    bubblesort 3 1 2 9 2 9 86 5 9 6 9 6 45
1 2 2 3 5 6 6 9 9 9 9 45 86

This article has some comments as to $::

Explaining what $: (self-reference) is and how it's used turned out to be a rather unfortunate starting point for some of those completely new to the language as this is an advanced feature and is atypical of the way things are usually done in J. John mentioned that Roger has commented that he wouldn't include this if he were designing the language now.

Once more, to sum up:

  • ^: is a conjunction and makes a new verb from its arguments;
  • $: denotes the longest verb that contains it.

Thanks fly out to estanford for dataset 3 1 2 9 2 9 86 5 9 6 9 6 45 in his answer.

Yasir Arsanukaev