cupraer24 фев в 05:29

Переверни его. Переверни наоборот

Простой

7 мин

7.5K

Elixir/Phoenix * Python * JavaScript * ГовнокодRuby *

Из песочницы

Комментарии 44

mayorovp 24 фев в 06:04

Какое-то изложение непоследовательное. Почему подход с аккумулятором и хвостовой рекурсией, вроде как идеальный для Erlang, даже не был упомянут как вариант в Хаскеле?

cupraer 24 фев в 06:09

Ну вы уж простите великодушно, как смог.

Первый вариант в хаскеле — это хвостовая рекурсия.

mayorovp 24 фев в 07:37

Канонический вариант:

reverse :: [a] -> [a]
reverse x = reverse' x []
  where
    reverse' [] acc = acc
    reverse' (x:xs) acc = reverse' xs (x:acc)

vkni 24 фев в 14:10

Вы же читали известное эссе про эволюцию программиста на Хаскеле? :-) Автор подходит с точки зрения point-less программиста, что более, чем естественно! :-)

https://people.willamette.edu/~fruehr/haskell/evolution.html

mayorovp 24 фев в 15:21

Читал я его, читал. Однако там полно стадий, из которых автор почему-то выбрал разные для разных языков.

vkni 24 фев в 15:56

"Художник так видит" - ну, блин, сама по-себе идеология программиста-полиглота, горячо поддерживаемая Алексеем, прямо запрещает "писать на любом языке, как на ФОРТРАНЕ" (а я видел, как по-английски пишут "на ФОРТРАНЕ"). То есть, для разных не родственных языков ОБЯЗАТЕЛЬНО должны быть разные стили.

Короче, придираетесь.

mayorovp 24 фев в 16:23

Но ведь Erlang и Haskell - родственные же...

Seasle 24 фев в 06:10

JavaScript – ожидаю toReversed... в 2026 то году. Но его почему-то нет.

MadridianFox 24 фев в 06:11

Эмм.. Мне одному показалось, что сейчас мне покажут как элегантно перелинковать ноды связанного списка, с разбором нюансов, а в итоге мне показали результат промпта "покажи как развернуть массив на разных языках"?

Kotofay 24 фев в 07:23

struct Node {
    Node * next;
    int data;
};

void foo( Node ** node ) {
    if( !node || !*node || !( *node )->next )
        return;

    auto & cur = *node;
    auto next = cur->next;

    cur->next = nullptr;

    while( next ) { 
        auto tmp = next->next;
        next->next = cur;
        cur = next;
        next = tmp;
    }
}

Собеседовал как то претендентов на синьора С++.
Что это и как работает ответило 2 из 10.
Так что да, пользуйтесь стандартными алгоритмами.

kmatveev 24 фев в 08:07

Я ни разу не сеньор C++, такой вопрос: зачем в foo передаётся указатель на указатель? Просто указателя вроде как должно быть достаточно.

mayorovp 24 фев в 08:24

Потому что после разворота указатель на голову списка должен изменить свой значение.

vkni 24 фев в 16:58

Это, кмк, реально древний код из непонятных времён, скорее всего переписанный с чего-то вроде Pascal или FORTRAN с указателями - то есть, с языков, где есть различие между функциями и процедурами. В С я бы использовал возвращаемое значение типа node *. Соответственно, сигнатура выглядела бы

node * foo( const node *)

В случае ошибки возвращается NULL, в случае успеха - указатель на новую голову.

Kotofay 24 фев в 18:30

И в каком состоянии останется список после ошибки?
Голову то вы уже потеряли, список разорван, память утекла.
И кстати, какие ошибки могут быть?
Список уже существует, никакая память не выделяется и не освобождается.
Это учебный код для выявления !С/С++ программистов и
!программистов прикидывающихся синьорами С++.

vkni 24 фев в 18:45

И в каком состоянии останется список после ошибки?

В отличном. Там состояния ошибки — это только

!node || !*node

Как вы, собственно, и пишете.

serp2002 24 фев в 06:47

>>В энтерпрайзах списки не разворачивают.

ну блин, я только ради этого статью и читал! )

qrdl 24 фев в 06:59

Жаль, что мы так и не увидели ни одного связанного списка. Развернуть слайс/массив/вектор - это совсем другая задача.

cupraer 24 фев в 07:41

В языках, в которых они есть из коробки, вы их увидели.

qrdl 24 фев в 07:54

Вектор в Rust:

A contiguous growable array type, written as Vec<T>

Слайс в Go:

They build on arrays to provide great power and convenience

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

kmatveev 24 фев в 10:25

подозреваю, с остальными языками такая же ситуация

В Haskell, Erlang и Elixir не так, там язык предоставляет тип данных "ячейка с двумя ссылками", первая ссылка указывает на элемент, вторая - на следующую ячейку, так что там настоящие односвязные списки. Исторически это идёт от Lisp-ов, называется cons-ячейки и продолжает жить во многих современных диалектах, например Scheme (кстати, где он?), но там оно мутабельное, а в Haskell/Erland/Elixir - нет.

cupraer 24 фев в 11:22

Да, пардон, про Scheme я впопыхах непростительно забыл.

vkni 24 фев в 15:53

Вообще, можно совместить со статьёй про парадигмы и их влияние.

qrdl 24 фев в 12:25

Ок, значит все же какие-то списки в статье есть. Но по тем языкам, которые я знаю, написано неправильно. И в Python'е слайсы тоже на базе массивов, насколько я помню.

Taraflex 24 фев в 07:06

Как надо:

const reverse = (list) => [...list].reverse();

Кхем. Вот так как раз-таки никогда нельзя, ибо переполнение стека. И даже, если забыть что по условию у нас вроде как список должен быть на выходе, а не массив, то должно быть хотя бы в стиле.

const reverse = (list) => Array.from(/*вот тут проглотит любой объект-итератор*/ list).reverse();

Остальные примеры не особо лучше.

mayorovp 24 фев в 07:39

А где тут переполнение стека может случиться?

cupraer 24 фев в 07:40

Нигде, конечно.

Taraflex 24 фев в 08:11

Каюсь. В данном случае переполнения нет. Приучил себя не использовать ... на итераторах неизвестной длинны. Ибо в конструкции

Math.max(...Array(1000000))

уже получим RangeError: Maximum call stack size exceeded

cupraer 24 фев в 11:25

Это совершенно нерелевантная проблема, связанная с внутренним разворотом интервала в массив.

mayorovp 24 фев в 13:12

Нет, эта проблема связана с попыткой передать 1000000 аргументов через стек. Но да, она нерелевантна.

tmhba 24 фев в 07:10

Это ведь про массивы, а не про связные списки.

gravicappa 24 фев в 07:13

const reverse = (list) => list.reduce((acc, current) => [current, ...acc], []);

Тут, если что, тоже O(n²).

Alexandroppolus 24 фев в 07:55

Раз уж в статье про разворот списка совершенно неожиданно (судя по всему, не только для меня) разворачивают массив, то вот знаменитый js-кодогольф на тему сабжа:

const reverse = a => a.map(a.pop,[...a])

Иммутабельно, за O(n)

domix32 24 фев в 12:40

Мне кажется более интересная задача про отражение дерева вокруг корня. Вот где всякое мясо начинает всплывать наружу.

Alexandroppolus 24 фев в 13:25

Это задача, на которую однажды намотали автора homebrew?

vkni 24 фев в 17:05

Отразили! :-)

domix32 15 часов назад

Ещё бы понимать о какой истории речь. Не могу ни подтвердить ни опровергнуть

Alexandroppolus 14 часов назад

История, нашумевшая в своё время - https://habr.com/ru/articles/345756/

vkni 24 фев в 13:47

Вот интересный момент, почему вы рядом с Эрлангом не поставили код на Прологе?

Очень многое по-поводу «инопланетного» синтаксиса Эрланга стало бы сразу очевидно...

С возвращением!

oeditus 24 фев в 14:01

На прологе же буквально ничем не отличается от на эрланге:

reverse(List, Reversed) :-
    reverse(List, [], Reversed).

reverse([], Buffer, Buffer).
reverse([Head|Tail], Buffer, Reversed) :-
    reverse(Tail, [Head|Buffer], Reversed). 

?- reverse([1, 2, 3], Result).

https://swish.swi-prolog.org/p/list-reverse-am.swinb

mayorovp 24 фев в 15:26

Настоящий код на Прологе должен работать в обе стороны, а тут reverse(Result, [1, 2, 3]) вылетает с переполнением стека на попытке выдать второй результат.

oeditus 24 фев в 16:08

Покажите настоящий код, пожалуйста.

mayorovp 24 фев в 16:28

Ну, квадратичный код работает с любой стороны:

reverse([], []).
reverse([Head|Tail], Reversed) :- 
    reverse(Tail, ReversedTail),
    append(ReversedTail, [Head], Reversed).

А если оптимизировать - то без free/bound (var/unvar) и ! не обойтись.

oeditus 24 фев в 16:31

Спасибо!

cupraer 24 фев в 14:03

Спасибо! Накопил материал зато, пока меня не было.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий