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

Question

Поскольку я новичок в J, я решил решить простую задачу с использованием этого языка, в частности, реализовать алгоритм пузырьковой сортировки. Я знаю, что идиоматически не решить такую ​​проблему в функциональных языках, потому что она естественным образом решается с помощью транспонирования элементов массива в императивных языках, таких как 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  

Символы, такие как + и * для плюса и времени в приведенных выше фразах, называются глаголами и представляют функции. У вас может быть более одного глагола в фразе 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<#) это глагол, он также должен образовывать другой глагол после соединения с #то есть можно рассматривать все предложение (первый фрагмент) как глагол. Вероятно, есть некоторый предел для длины глагола, ограниченный одним соединением.

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

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

factorial внутри выражения относится ко всей функции, т.е. (* 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

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

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

Еще раз, чтобы подвести итог:

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

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

Answer 2

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

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

Answer 3

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