В ФЯ существует удобная конструкция для операций с головой списка, в ерланг например [H | T]. Почему также нельзя выделить последний элемент и то, что находиться до него? Как-то так например: [H |T1,T2].

Здравствуйте, LaPerouse, Вы писали:

LP>В ФЯ существует удобная конструкция для операций с головой списка, в ерланг например [H | T]. Почему также нельзя выделить последний элемент и то, что находиться до него? Как-то так например: [H |T1,T2].
По тому что оторвать списку голову стоит O(1), а оторвать хвост O(N).
А если вспомнить про ленивые языки с бесконечными списками...

Здравствуйте, LaPerouse, Вы писали:

LP>В ФЯ существует удобная конструкция для операций с головой списка, в ерланг например [H | T]. Почему также нельзя выделить последний элемент и то, что находиться до него? Как-то так например: [H |T1,T2].

Потому что это совсем другая модель данных. Обычно — односвязный список, по которому можно двигаться только в одну сторону. А тут двусвязный, с указателями на голову и хвост. В таком виде невозможно представить, например, поток данных — у нас ещё нет хвоста, он не пришёл. Или еще не вычислен. С такой формой хуже будет работать ленивость (имхо). Сложнее сделать, например, два списка, у которых хвост общий, а головы разные. Потому что по такому списку можно идти от хвоста и не ясно, куда идти, встретив развилку.

Можно было бы вообще массив с произвольным доступом устроить — но это ещё больше ограничений.

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, LaPerouse, Вы писали:

LP>>В ФЯ существует удобная конструкция для операций с головой списка, в ерланг например [H | T]. Почему также нельзя выделить последний элемент и то, что находиться до него? Как-то так например: [H |T1,T2].
WH>По тому что оторвать списку голову стоит O(1), а оторвать хвост O(N).
WH>А если вспомнить про ленивые языки с бесконечными списками...

Тем не менее функцию last засунули в стандартную библиотеку. если сделать список двунаправленным, то будет тот же O(1).

Здравствуйте, SergH, Вы писали:

SH>Здравствуйте, LaPerouse, Вы писали:

LP>>В ФЯ существует удобная конструкция для операций с головой списка, в ерланг например [H | T]. Почему также нельзя выделить последний элемент и то, что находиться до него? Как-то так например: [H |T1,T2].

SH>Потому что это совсем другая модель данных. Обычно — односвязный список, по которому можно двигаться только в одну сторону. А тут двусвязный, с указателями на голову и хвост. В таком виде невозможно представить, например, поток данных — у нас ещё нет хвоста, он не пришёл. Или еще не вычислен. С такой формой хуже будет работать ленивость (имхо). Сложнее сделать, например, два списка, у которых хвост общий, а головы разные. Потому что по такому списку можно идти от хвоста и не ясно, куда идти, встретив развилку.

SH>Можно было бы вообще массив с произвольным доступом устроить — но это ещё больше ограничений.

Ну тогда двусвязный список можно было бы сделать отдельным типом данных. есть же массивы.

Здравствуйте, LaPerouse, Вы писали:

LP>Ну тогда двусвязный список можно было бы сделать отдельным типом данных. есть же массивы.

Алгоритмы, рассчитанные на этот тип данных будут менее общими.

А кому надо — сделает. Несложно же.

Здравствуйте, SergH, Вы писали:

SH>Здравствуйте, LaPerouse, Вы писали:

LP>>Ну тогда двусвязный список можно было бы сделать отдельным типом данных. есть же массивы.

SH>Алгоритмы, рассчитанные на этот тип данных будут менее общими.

SH>А кому надо — сделает. Несложно же.

Синтаксис не сделать. Речь шла именно о синтаксисе.

Здравствуйте, LaPerouse, Вы писали:

LP>Тем не менее функцию last засунули в стандартную библиотеку.
Только есть мнение что она на пару с функцией head зло. Ибо что делать с пустым списком?

LP>если сделать список двунаправленным, то будет тот же O(1).
Неизменяемый список двусвязным? Есть конечно всякие там rope'ы но это несколько иная структура данных... гораздо болие кучерявая чем список.
А с бесконечным списком что делать?

Здравствуйте, LaPerouse, Вы писали:

LP>В ФЯ существует удобная конструкция для операций с головой списка, в ерланг например [H | T]. Почему также нельзя выделить последний элемент и то, что находиться до него? Как-то так например: [H |T1,T2].

Если речь о синтаксисе, а не о структуре данных, то возможный ответ — extractors из Scala или что-то подобное.

Здравствуйте, LaPerouse, Вы писали:

LP>В ФЯ существует удобная конструкция для операций с головой списка, в ерланг например [H | T]. Почему также нельзя выделить последний элемент и то, что находиться до него? Как-то так например: [H |T1,T2].

Подобное было в Рефале, например. Правда, Рефал не столько ФЯ, сколько марковский язык. Но точно декларативный...

$ENTRY Go { = <Prout <Palindrome 'hadgalagdah'>> }

Palindrome {
                 = True;
     s.1         = True;
     s.1 e.2 s.1 = <Palindrome e.2>;
     e.1         = False;  
}

Здравствуйте, geniepro, Вы писали:

G>Подобное было в Рефале, например. Правда, Рефал не столько ФЯ, сколько марковский язык. Но точно декларативный...

Ну в Рефале вообще легкий доступ к любым сложных структурам.

Здравствуйте, LaPerouse, Вы писали:

LP>В ФЯ существует удобная конструкция для операций с головой списка, в ерланг например [H | T]. Почему также нельзя выделить последний элемент и то, что находиться до него? Как-то так например: [H |T1,T2].

Если сильно хочется, то реверсируй список и обращайся к первому элементу. Правда, будет не быстрее и не решает некоторые другие проблемы.

Здравствуйте, Turtle.BAZON.Group, Вы писали:

TBG>Здравствуйте, LaPerouse, Вы писали:

LP>>В ФЯ существует удобная конструкция для операций с головой списка, в ерланг например [H | T]. Почему также нельзя выделить последний элемент и то, что находиться до него? Как-то так например: [H |T1,T2].

TBG>Если сильно хочется, то реверсируй список и обращайся к первому элементу. Правда, будет не быстрее и не решает некоторые другие проблемы.

Так и сделал. Если обработка симметричная, то это самое то, т к reusing. Пусть и двойной реверс дорогой.

Здравствуйте, LaPerouse, Вы писали:

LP>Здравствуйте, SergH, Вы писали:

SH>>Здравствуйте, LaPerouse, Вы писали:

LP>>>Ну тогда двусвязный список можно было бы сделать отдельным типом данных. есть же массивы.

SH>>Алгоритмы, рассчитанные на этот тип данных будут менее общими.

SH>>А кому надо — сделает. Несложно же.

LP>Синтаксис не сделать. Речь шла именно о синтаксисе.

В языке FP есть симметричные списки. см. "Функциональное программирование" Филда и Хариссона. М Мир, 1993. Но там мало. Если найдёшь больше — отпишись.

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, LaPerouse, Вы писали:

LP>>Тем не менее функцию last засунули в стандартную библиотеку.
WH>Только есть мнение что она на пару с функцией head зло. Ибо что делать с пустым списком?

Пустой отсеивается в pm.

LP>>если сделать список двунаправленным, то будет тот же O(1).
WH>Неизменяемый список двусвязным? Есть конечно всякие там rope'ы но это несколько иная структура данных... гораздо болие кучерявая чем список.
WH>А с бесконечным списком что делать?

Бесконечные — отдельный тип данных?
Какая проблема сделать неизменяемый список двусвязным? Дороже создание нового списка. Если скажем новый список отличается от старого только одним элементом и оптимизатор это просечет, то компилятору придется модифицировать две ячейки вместо одной. Не так фатально.

Здравствуйте, LaPerouse, Вы писали:

LP>>>Тем не менее функцию last засунули в стандартную библиотеку.
WH>>Только есть мнение что она на пару с функцией head зло. Ибо что делать с пустым списком?
LP>Пустой отсеивается в pm.
Мы проде про функции head и tail говорим? А они должны что-то возвращать. А при пустом списке возвращать им решительно нечего. Ну разве что заставить их возвращать maybe. Но тогда за что боролись? Не понятно.

LP>Бесконечные — отдельный тип данных?
Не обязательно.

LP>Какая проблема сделать неизменяемый список двусвязным?
Нууу... как бы это сказать... двусвязный список можно реализавать только при наличии разрушающего присваивания.
Но если очень хочется не изменяемую структуру данных с похожими свойствами смотри на rope.

LP>Дороже создание нового списка. Если скажем новый список отличается от старого только одним элементом и оптимизатор это просечет, то компилятору придется модифицировать две ячейки вместо одной. Не так фатально.
А за одно выполним бесконечный цик за 7 секунд.

Здравствуйте, LaPerouse, Вы писали:

LP>Какая проблема сделать неизменяемый список двусвязным?
А почему не использовать более подходящую структуру данных, например, Data.Sequence, если речь о Haskell?

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, LaPerouse, Вы писали:

LP>>>>Тем не менее функцию last засунули в стандартную библиотеку.
WH>>>Только есть мнение что она на пару с функцией head зло. Ибо что делать с пустым списком?
LP>>Пустой отсеивается в pm.
WH> Мы проде про функции head и tail говорим? А они должны что-то возвращать. А при пустом списке возвращать им решительно нечего. Ну разве что заставить их возвращать maybe. Но тогда за что боролись? Не понятно.

Кстати говоря, почему нечего? Пусть возвращают пустой список. Зачем в haskell кидается exception — непонятно.

LP>>Бесконечные — отдельный тип данных?
WH>Не обязательно.

Я имел ввиду надо сделать их отдельным типом данных.

LP>>Какая проблема сделать неизменяемый список двусвязным?
WH>Нууу... как бы это сказать... двусвязный список можно реализавать только при наличии разрушающего присваивания.
WH>Но если очень хочется не изменяемую структуру данных с похожими свойствами смотри на rope.

Не будет. При добавлении элемента будем создавать полностью новый список (в отличие от однонаправленного списка, когда достаточно было салиасить новый элемент на голову старого списка). При этом тяжело придется рантайму — будет куча переалокаций, но к процессу программирования это отношение не имеет. Все по прежнему immutable. Но тут на самом деле можно и не выделять память под новый список, там есть возможности для оптимизации.

Здравствуйте, palm mute, Вы писали:

PM>Здравствуйте, LaPerouse, Вы писали:

LP>>Какая проблема сделать неизменяемый список двусвязным?
PM>А почему не использовать более подходящую структуру данных, например, Data.Sequence, если речь о Haskell?

Речь шла больше о ерланге. Про Data.Sequence из haskell не слышал.

Здравствуйте, LaPerouse, Вы писали:

LP>Кстати говоря, почему нечего? Пусть возвращают пустой список. Зачем в haskell кидается exception — непонятно.
А зачем они тогда вобще нужны если они будут список возвращать?

LP>Я имел ввиду надо сделать их отдельным типом данных.
Не надо.

LP>Не будет.
Чего не будет?

LP>При добавлении элемента будем создавать полностью новый список (в отличие от однонаправленного списка, когда достаточно было салиасить новый элемент на голову старого списка).
Тогда почему не массив? Они сильно эффективние двусвязных списков при таком раскладе.

LP>При этом тяжело придется рантайму — будет куча переалокаций, но к процессу программирования это отношение не имеет. Все по прежнему immutable. Но тут на самом деле можно и не выделять память под новый список, там есть возможности для оптимизации.
Еще раз: Кури rope