J: Self-reference in bubble sort tacit implementation

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 

Дело в том, что сбивает с толку меня это $:, ссылаясь на утверждение в крайних скобках. Help говорит, что:

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

The other book (~ 300 KiB) говорит:

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 

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

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

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

Согласно this reference (175 KiB) конъюнкции является:

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

В ^: попадает в выше указанной категории, применяя его к результатам аргументов в более глаголом:

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

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

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

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

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

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

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

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

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

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

Answer 2

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

EDIT: Вы пробовали использовать свой вид пузыря на наборе данных, например 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