🚀 go-pugleaf

W dniu czwartek, 22 sierpnia 2019 10:57:40 UTC+2 użytkownik Maciej Sobczak napisał:
> Nudy jakieś, wszyscy na urlopach?
> W każdym razie, skoro ostatnio były tu fajne dyskusje o różnych językach programowania, to pozwolę sobie dla hecy pokazać sortowanie bąbelkowe w Wolframie.
> 
> Otóż jak wiadomo, pojedynczy krok sortowania polega na tym, że jeśli gdzieś jest para elementów w "niewłaściwej" kolejności, to trzeba je zamienić miejscami. A potem powtarzać to aż do skutku.
> 
> No to mamy, pojedynczy krok:
> 
> oneBubbleStep[lst_] := 
>  lst /. {pre___, a_, b_, post___} /; a > b -> {pre, b, a, post}
> 
> oneBubbleStep to funkcja, która ma jeden parametr, nazwany lst. Ta funkcja szuka wzorca:
> 
> {pre___, a_, b_, post___}
> 
> wzorzec ma być listą, składającą się z:
> 1. jakiegoś pre, zero lub więcej elementów
> 2. jakiegoś a
> 3. jakiegoś b
> 4. jakiegoś post, zero lub więcej elementów
> 
> i jeśli przypadkiem a > b, to znaleziony wzorzec ma być zamieniony na taki:
> 
> {pre, b, a, post}
> 
> czyli elementy a i b mają się zamienić miejscami. Jeśli wzorzec nie pasuje, to żadna zmiana nie jest wykonana. To zadziała zawsze, nawet na brzegach, np.:
> 
> oneBubbleStep[{10, 20, 40, 30, 50}]
> 
> {10, 20, 30, 40, 50}
> 
> I teraz biorę jakieś dane testowe:
> 
> testData = RandomSample[Range[10], 10]
> 
> {2, 10, 1, 3, 8, 9, 6, 4, 5, 7}
> 
> i aplikuję funkcję oneBubbleStep tak długo, aż wynik przestanie się zmieniać, pokazując po drodze wszystkie pośrednie wyniki (sformatowałem ręcznie):
> 
> FixedPointList[oneBubbleStep, testData]
> 
> {
>  {2, 10, 1, 3, 8, 9, 6, 4, 5, 7},
>  {2, 1, 10, 3, 8, 9, 6, 4, 5, 7},
>  {1, 2, 10, 3, 8, 9, 6, 4, 5, 7},
>  {1, 2, 3, 10, 8, 9, 6, 4, 5, 7},
>  {1, 2, 3, 8, 10, 9, 6, 4, 5, 7},
>  {1, 2, 3, 8, 9, 10, 6, 4, 5, 7},
>  {1, 2, 3, 8, 9, 6, 10, 4, 5, 7},
>  {1, 2, 3, 8, 6, 9, 10, 4, 5, 7},
>  {1, 2, 3, 6, 8, 9, 10, 4, 5, 7},
>  {1, 2, 3, 6, 8, 9, 4, 10, 5, 7},
>  {1, 2, 3, 6, 8, 4, 9, 10, 5, 7},
>  {1, 2, 3, 6, 4, 8, 9, 10, 5, 7},
>  {1, 2, 3, 4, 6, 8, 9, 10, 5, 7},
>  {1, 2, 3, 4, 6, 8, 9, 5, 10, 7},
>  {1, 2, 3, 4, 6, 8, 5, 9, 10, 7},
>  {1, 2, 3, 4, 6, 5, 8, 9, 10, 7},
>  {1, 2, 3, 4, 5, 6, 8, 9, 10, 7},
>  {1, 2, 3, 4, 5, 6, 8, 9, 7, 10},
>  {1, 2, 3, 4, 5, 6, 8, 7, 9, 10},
>  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
>  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
> }
> 
> Ten "program" ma swoją interpunkcję, która na pewno się tu komuś nie spodoba, ale ma ciekawą zaletę: odzwierciedla opis słowny. Fajne?

Rzeczywiście ładne.
Spośród rozwiązań na Rosetta Code to w Wolframie jest niewątpliwie najładniejsze:

bubbleSort[{w___, x_, y_, z___}] /; x > y := bubbleSort[{w, y, x, z}]
bubbleSort[sortedList_] := sortedList

Szkoda tylko, że taka brzydka interpunkcja ;]

> Spośród rozwiązań na Rosetta Code to w Wolframie jest niewątpliwie najładniejsze:
> 
> bubbleSort[{w___, x_, y_, z___}] /; x > y := bubbleSort[{w, y, x, z}]
> bubbleSort[sortedList_] := sortedList

Tak, w tym wypadku wzorzec (i to razem z warunkiem) jest w "sygnaturze" funkcji. To pokazuje, że w Wolframie wywołanie funkcji nie działa tak samo jak w innych językach, tylko jest podmianą pasującego wzorca. Z punktu widzenia innych języków to powyżej to "przeciążanie" funkcji, ale widać, że wtedy przeciążanie na podstawie liczby albo typów argumentów to zaledwie kropelka w morzu tego, co da się takim mechanizmem zrobić.
Przyznam jednak, że o ile ten mechanizm ma wysoką teoretyczną estetykę (pomijając rekurencję w tym przykładzie, która to rekurencja nie ma żadnej wartości dodanej i jest ogólnie fuj), to mam opory przed jego szerszym użyciem. Może ograniczają mnie stare przyzwyczajenia, ale pewniej się czuję z wzorcami ukrytymi wewnątrz funkcji, tak jak w moim pierwszym przykładzie. To, że te dwa podejścia są wymienne widać też po tym, że nawet ilość kodu jest taka sama (ale rekurencja jest fuj).

Natomiast funkcja FixedPointLoop ma ciekawą cechę, że daje pośrednie wyniki (FixedPoint daje tylko ostateczny) - pięknie się to nadaje do wizualizacji przebiegu obliczeń. Wystarczy na wyniku zaaplikować funkcję np. ArrayPlot i mamy prezentację bąbelków, które w kolejnych wierszach płyną na swoje miejsca.

https://reference.wolfram.com/language/ref/ArrayPlot.html

I w kilku linijkach mamy gotową lekcję informatyki.

> Szkoda tylko, że taka brzydka interpunkcja ;]

Interpunkcja to skróty dla tych, co lubią skróty. Dla tych co nie lubią (ta sama funkcja):

oneBubbleStep[lst_]:=ReplaceAll[lst, 
 Rule[Condition[
   List[Pattern[pre, BlankNullSequence[]], Pattern[a, Blank[]], 
    Pattern[b, Blank[]], Pattern[post, BlankNullSequence[]]], 
   Greater[a, b]], List[pre, b, a, post]]]

Tak to widzi Wolfram w środku, zawsze. Człowiek ma wybór.

-- 
Maciej Sobczak * http://www.inspirel.com

W dniu piątek, 23 sierpnia 2019 08:18:35 UTC+2 użytkownik Maciej Sobczak napisał:
> > Spośród rozwiązań na Rosetta Code to w Wolframie jest niewątpliwie najładniejsze:
> > 
> > bubbleSort[{w___, x_, y_, z___}] /; x > y := bubbleSort[{w, y, x, z}]
> > bubbleSort[sortedList_] := sortedList
> 
> Tak, w tym wypadku wzorzec (i to razem z warunkiem) jest w "sygnaturze" funkcji. To pokazuje, że w Wolframie wywołanie funkcji nie działa tak samo jak w innych językach, tylko jest podmianą pasującego wzorca. Z punktu widzenia innych języków to powyżej to "przeciążanie" funkcji, ale widać, że wtedy przeciążanie na podstawie liczby albo typów argumentów to zaledwie kropelka w morzu tego, co da się takim mechanizmem zrobić.
> Przyznam jednak, że o ile ten mechanizm ma wysoką teoretyczną estetykę (pomijając rekurencję w tym przykładzie, która to rekurencja nie ma żadnej wartości dodanej i jest ogólnie fuj), to mam opory przed jego szerszym użyciem. Może ograniczają mnie stare przyzwyczajenia, ale pewniej się czuję z wzorcami ukrytymi wewnątrz funkcji, tak jak w moim pierwszym przykładzie. To, że te dwa podejścia są wymienne widać też po tym, że nawet ilość kodu jest taka sama (ale rekurencja jest fuj).

A dlaczego rekurencja jest fuj?
(I dlaczego Stephen Wolfram zdecydował się ją wesprzeć w swoim języku?)

> A dlaczego rekurencja jest fuj?

Bo sortowanie bąbelkowe jest procesem fizycznym, który ani się na rekurencji nie opiera ani też nie odnosi się do niej w swoim opisie. Właśnie brak odniesienia do rekurencji w opisie tego procesu sprawia, że rekurencja jest tam obcą konstrukcją. Można byłoby się z niej wytłumaczyć, gdyby była artefaktem implementacyjnym, wymaganym przez użytą technologię (coś w stylu - dlaczego w silniku benzynowym jest świeca zapłonowa). Ale nie jest.

Ot, jakiś fan programowania funkcyjnego się popisał.

> (I dlaczego Stephen Wolfram zdecydował się ją wesprzeć w swoim języku?)

A dlaczego uważasz, że się zdecydował albo że ją wsparł? W takiej formie jak powyżej, możliwość użycia rekurencji jest raczej przypadkowym efektem ubocznym innych reguł. O innych językach też tak można powiedzieć - funkcja może zawołać funkcję; właściwie może zawołać dowolną, bo niby czemu nie; o kurczę, sama siebie też może zawołać, a to dopiero ciekawostka!

Należałoby raczej powiedzieć, że jej nie zabronił. Bo i nie było potrzeby zabraniać. Ale żeby robić z tego fetysz?
Zwłaszcza, że wersja bez rekurencji nie jest ani trochę dłuższa. A przy użyciu lambdy można było całość zapisać jednym wyrażeniem:

FixedPoint[#/.{pre___,a_,b_,post___}/;a>b->{pre,b,a,post}&,testData]

I tego już rekurencja nie potrafi. A nadal jest zgodnie z opisem.

-- 
Maciej Sobczak * http://www.inspirel.com