J:Самоссылка в неявной реализации пузырьковой сортировки

Question

Поскольку я новичок в J, я решил решить простую задачу, используя этот язык, в частности, реализовать алгоритм bubblesort.Я знаю, что это не идиоматично для решения такого рода проблем на функциональных языках, потому что это естественным образом решается с помощью транспозиции элементов массива в императивных языках, таких как C, вместо построения измененного списка в декларативных языках.Однако это код, который я написал:

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

Вот структура заявления:

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

Давайте применим это к массиву:

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

Вот что меня смущает, так это $: ссылка на утверждение, заключенное в крайние круглые скобки. Справка говорит , что:

$: обозначает самый длинный глагол, который его содержит.

Другая книга (~ 300 Кб) гласит:

    3+4 
7  
    5*20  
100  

Символы типа + и * для plus и времена в приведенных выше фразах они называются глаголами и представляют функции.У вас может быть более одного глагола в J-фразе, в этом случае она строится как предложение на простом английском языке с помощью чтение слева направо, то есть 4+6%2 означает 4 добавлено ко всему последующему, а именно 6 разделенный на 2.

Давайте перепишем мой фрагмент кода, опустив самый внешний ()s:

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

Повторные запросы те же.Я не мог бы объяснить себе, почему это работает, почему только ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) рассматривается как самый длинный глагол для $: но не все выражение целиком ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) ^: # и не только (<./@(2&{.)), $:@((>./@(2&{.)),2&}.), потому что если ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) является глаголом, он также должен образовывать другой глагол после соединения с #, я.e.можно рассматривать все предложение (первый фрагмент) как глагол.Вероятно, существует какое-то ограничение на длину глагола, ограниченное одним союзом.

Посмотрите на следующий код (отсюда):

    factorial =: (* factorial@<:) ^: (1&<)
    factorial 4
24

factorial внутреннее выражение относится ко всей функции в целом, i.e. (* factorial@<:) ^: (1&<).

Следуя этому примеру, я использовал имя функции вместо $::

    bubblesort =: (((<./@(2&{.)), bubblesort@((>./@(2&{.)),2&}.)) ^: (1<#)) ^: #
    bubblesort 5 3 8 7 2
2 3 5 7 8

Я ожидал bubblesort ссылаться на всю функцию целиком, но мне это не кажется верным, так как результат правильный.

Также я хотел бы увидеть другие реализации, если они у вас есть, даже слегка переработанные.

Спасибо.

Answer 1

Согласно эта ссылка (175 кб) соединение является:

Часть речи, которая принимает два аргумента и обычно приводит к глаголу.Например, *:^:3 является функцией, которая выполняет возведение в квадрат три раза (^: является соединение).

Как ^: подпадает под вышеупомянутую категорию, применение ее к аргументам приводит к более длинному глаголу:

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

Потому что $: обозначает самый длинный глагол, который его содержит, он относится к коду, только что написанному выше.

Аналогично, следующий ^: образует новый более длинный глагол из ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) и #:

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

на который, в свою очередь, ссылаются $: потому что он длиннее предыдущего.

Поскольку это нежелательное поведение, вероятно, единственным решением является разделение всего глагола таким образом, чтобы $: относится к ((<./@(2&{.)), $:@((>./@(2&{.)),2&}.)) ^: (1<#) хотя это не одноразовый лайнер:

    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

Эта статья имеет некоторые комментарии относительно $::

Объясняя, что $: (ссылка на себя) является ли и как оно используется, оказалось довольно неудачной отправной точкой для некоторых из тех, кто совершенно не знаком с языком, поскольку это продвинутая функция и нетипичный способ обычно все делается на J.Джон упомянул, что Роджер прокомментировал что он не включил бы это, если бы разрабатывал язык сейчас.

Еще раз подводя итог:

• ^: является соединение и создает новый глагол из его аргументов;
• $: обозначает самый длинный глагол это содержит в себе все.

Спасибо, что прилетели к эстанфорд для набора данных 3 1 2 9 2 9 86 5 9 6 9 6 45 в своем ответе.

Answer 2

Я занимаюсь этим делом.В то же время, вы внедряете bubblesort, потому что вам нужна bubblesort конкретно, или потому, что вам просто нужна сортировка (т.Е.не могли бы вы выйти сухим из воды, используя /:~ вместо этого)?

Редактировать:Вы пробовали запускать свою пузырьковую сортировку в наборе данных, например 3 1 2 9 2 9 86 5 9 6 9 6 45?Система зависала, когда я попробовал это на своей машине, но это работает, если вы замените окончание # на _.

Answer 3

Вот еще один подход к реализации пузырьковой сортировки в J: http://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort#J