Добрый день, Сергей Михайлович! «то оба терма-скобок делаются „такими же“ — в смысле указывают на одно место и имеют равную длину.»
И таким образом ещё и может экономиться память: вторая ссылка на равный скобочный терм может оказаться ненужной и удалиться как мусор. Ещё можно показать, что эти две функции реверса списка эквивалентны: nrev [] = [] nrev x:xs = (nrev xs) ++ [x] arev xs = arevLoop xs [] arevLoop [] acc = acc arevLoop x:xs acc = arevLoop xs (x:acc) Первая имеет квадратичную сложность, вторая — линейную. Не уверен, можно ли одну привести к другой эквивалентными преобразованиями Бёрстола и Дарлингтона, но (а) можно их эквивалентность доказать на Идрисе (https://habr.com/ru/post/463957/), (б) Гамильтон каким-то образом выводил второе из первого при помощи своей туманной «дистилляции». С уважением, Александр Коновалов -----Original Message----- From: Sergei M. Abramov abram_AT_botik.ru [mailto:refal@botik.ru] Sent: Friday, April 10, 2020 12:31 PM To: Василий Стеллецкий swi_AT_cnshb.ru <refal@botik.ru> Subject: Re: Сортировка в Рефале-5 День добрый, всем! > Вряд ли такое возможно, Александр! > Интуиция подсказывает, что при "элементарных" преобразованиях порядок > сложности алгоритма не должен измениться... -- Колапсирующие джунгли порядок меняют, и понятно почему. Ну, и ручками, мемоизация (а именно ее колапс поднимает) позволяет изменить порядок. PS. К слову, в рефале плюс встроены колапсирующие джунгли над данными: если понадобилось сравнить два терма-скобок (а скобки у нас подвешенны) и они оказались равными, то оба терма-скобок делаются "такими же" -- в смысле указывают на одно место и имеют равную длину. То есть, термы становятся не просто "равный", а "тот же ссамый". С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308
