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

Помогите реализовать функцию,удаляющую из списка каждый второй элемент.

0

0

Сообщение от pycture это самое короткое и правильное решение в функциональном стиле

Не самое…

Добавлено через 34 секунды

Сообщение от _Ivana Я прочел только, что ML это типизированный Лисп с раскукоженным синтаксисом

Фигню прочёл.

2

Сообщение от Ev_Hyper Visual F# Power Tools

Решает пару проблем, но подсветка иногда глючит.

Сообщение от Ev_Hyper все - же это не самый хороший пример

Первое, что пришло на ум из простого.

Сообщение от Ev_Hyper Почему?

OCaml считается родителем F#, т.е. истину стоит искать там. Правильно описать не смогу, я не гуру ФП, но здесь описано пару основных моментов: http://stackoverflow.com/a/27652530

Сообщение от Ev_Hyper А можно увидеть на них ссылки?

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

0

Сообщение от I2um1 Вот это я не просто так написал, а довольно интересный факт, но описывать его не буду.

Потому что в Ocaml нет list comprehensions?

2

Сообщение от korvin_ Потому что в Ocaml нет list comprehensions?

Угу.

0

Сообщение от I2um1 Решает пару проблем, но подсветка иногда глючит.

Угу, зато быстрое форматирование очень удобно.

Сообщение от I2um1 Не, я стесняюсь и не гонюсь за популярностью. Тем более это чревато негативными последствиями для меня.

а можно тогда хотя-бы в личку? Дальше меня информация не уйдет.

Сообщение от I2um1 OCaml считается родителем F#, т.е. истину стоит искать там. Правильно описать не смогу, я не гуру ФП, но здесь описано пару основных моментов:

Т.е. что вроде Эрланговского генератора

http://erlang.org/doc/programm... sions.html

имхо, трудно для восприятия непосвященных.

0

Сообщение от I2um1 OCaml считается родителем F#

Это не значит, что потомок — точная копия родителя без изменений и дополнений, поэтому

Сообщение от I2um1 истину стоит искать…

… в документации по F#.

Добавлено через 1 минуту

Сообщение от I2um1 Угу.

Что «угу»? Отсутствие в Ocaml list comprehensions означает, что они не нужны? Ты что сказать-то хочешь?

1

Сообщение от korvin_ что они не нужны?

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

Добавлено через 59 секунд

Сообщение от korvin_ в документации по F#.

Я документацию ищу не там, обычно ее там просто нет, если мы конечно говорим про msdn.

0

Сообщение от I2um1 JetBrains... Если сильно утрировать, они оценивают пригодность языка по его возможностям, мощности тулкитов и размеру комьюнити. Где-то даже был интересный подробный анализ F#, точнее почему он плох, если пытаться писать в чистом функциональном стиле. Даже Visual Studio очень плохо поддерживает F#, опустим что это кроссплатформенный язык. К примеру допустимо создавать папки в проекте, но через VS это не сделать. Или как использовать частичные классы в XAML (не важно, WPF, Xamarin, что-то еще); советуют использовать MVC вместо MVVM, потому что можно настроить удобный биндинг.

JetBrains после этого конечно можно было дальше не читать, но я все же поясню.

не надо требовать от языка то для чего он не предназначен. f# всегда четко позиционировался как язык для обработки данных и поддержка в VS на уровне позиционирования языка вполне достаточная. а гуевые свистелки-перделки для мышевозов всегда рекомендовали делать на с#. далее. вот в c# нет ADT, от слова совсем, - торжественно объявим его неязыком? а тайппровайдерах в c# даже не мечтают. так что проблема то не в языках а в оценщиках типа JetBrains

Сообщение от korvin_ Не самое…

это для хаскеля не самое. для F# чтото пристойней предложить сложно. и да на хаскеле пишется еще короче

Сообщение от I2um1 OCaml считается родителем F#, т.е. истину стоит искать там

так только считается. все сложнее.

на самом деле оверблюд достаточно уникален. если чтото там нет изначально, это не значит, что это не появится в батарейках. там лисп можно встроить не то что какой то List Comprehension https://github.com/cakeplus/pa_comprehension/

Добавлено через 3 часа 10 минут
ps хе... ссылку на camlp4 то я и не приметил/

Добавлено через 1 минуту
ладно. один черт фешарпный List Comprehension на из окамла растет

0

Тривиальное решение.
А то индексации какие то. В реале, если понадобится выкинуть каждую вторую карту из колоды, никто не будет же нумеровать колоду и остаток от деления находить. Может % 2 и соптимизируется, но, всё равно, не наглядно. IMHO.

0

Сообщение от KolodeznyDiver Тривиальное решение

т.е. студенческое, что в общем то и требовалось, оно такое.

В реале,...

оно издохнет на переполнении стека (здесь вам не хаскель). поэтому в реале будет только фор.

1

Сообщение от pycture т.е. студенческое, что в общем то и требовалось

Да. Спасибо за напоминание что в F# меньше проверок требуется.

Сообщение от pycture оно издохнет на переполнении стека

Я в курсе. Условия соблюдены. Чтобы меньше дохло хвостовую рекурсию. Её в самом начале темы привели. Суть, в общем, в том что для такой задачки рекурсия самое то.

0

Лесник в эту тему уже заглядывал, сейчас очередь Капитана Очевидности
Сабжевая задача про то, как из списка выделить подсписок по определенному критерию. То есть, говоря в общем, абстракция filter или (чуть отдаленнее) map. Для определенности останемся в рамках иммутабельности и оставим за кадром возможности некоторых функциональных языков деструктивно изменять список при пробежке по нему (set-car | set-cdr или как оно там называется). Из очевидных решений реализации этих функций в рамках библиотеки (а не в ядре самого языка) видится 3 варианта:

1) вышеприведенный рекурсивный без аккумулятора. Сохраняет порядок элементов в списке, в принципе работает на бесконечных списках-потоках (с кучей оговорок на стек, ленивую/строгую семантику, реализацию самих ленивых структур и т.п.), в наивной реализации при строгой семантике жрет стек потому что не хвостовой вызов.

2) вариант с накоплением результата в аккумуляторе. Реверсирует порядок элементов (для половины задач использования списков это вполне допустимо), не работает на бесконечных списках, не жрет стек при наличии ТСО в ядре языка.

3) вариант 2 с последующим реверсом результата - со всеми особенностями варианта 2 плюс вторая пробежка по списку.

Я год назад накостылил свой строгий функциональный язык, реализацию интерпретатора. И в стандартную библиотеку мне конечно потребовались и map и filter. Сначала я их реализовал по варианту 1. Но поскольку реализация интерпретатора была на Java, то я ловил стековерфлоу уже на списках порядка нескольких сотен элементов (в Java очень маленький стек выделяемый по умолчанию на поток, его можно увеличить ключами запуска приложения, но все равно кардинально не решает проблему). Потом я реализовал в ядре интерпретатора ТСО и переписал эти библиотечные функции по варианту 3. Стало работать чуть медленнее (за счет финального реверса результата), но стек не переполнялся на любых размерах списков. (Потоковые аналоги этих функций для бесконечных ленивых списков конечно остались в варианте 1). Потом я написал второй эвалюатор интерпретатора (рядом с первым, можно в ГУЕ выставлять флажок каким эвалюатором считать), который был нерекурсивный и использовал собственный навелосипеденный стек (с точки зрения Java размещающийся в куче). Стало раза в полтора медленнее, но никаких стековерфлоу ни на каких задачах от слова ваще! Я бы переписал обратно библиотечные мапы и фильтры на реализации без аккумуляторов, если бы ради фана не оставил возможность юзеру выбирать эвалюатор. Хотя может допустимым решением было бы влепить в библиотеку все 3 версии каждой (!) списковой функции. Но я то (на правах создателя этого безобразия и концепции) знаю чем они отличаются и когда какую надо применять, а объяснить это начинающим имхо было бы нетривиально

Я, собственно, к чему это все. Реализуя подобные функции, по-хорошему стоит знать, в какой семантике абстрактной (или конкретной) виртуальной машины они будут жить и работать А то может и циклами надо писать, как говорит уважаемый pycture, или же покатит и лобовой безаккумуляторный вариант 1, если под капотом хаскель или мой итеративный эвалюатор.

ЗЫ однажды на хабре кто-то написал статью про понятие котоморфизма применительно к практике. Но кота (морфирующего) писал на F#, на примере общей функции свертки дерева по любой сверточной функции. Так автор специально вместо наивного рекурсивного решения свертки применил технику то ли трамплинов, то ли еще чего-то (сейчас уже и не помню, но можно найти статью и посмотреть) - для того, чтобы перенести вычисления со стека в кучу и избежать стековерфлоу. А вы говорите язык для обработки данных и суровой правды реальной жизни вместо фантазийноролевых игр Но это я шучу, я вроде не настолько идиот как выгляжу, чтобы разжигать холивар с разумными людьми по такому поводу

1

Хвостовой без реверса результатаВозможно, его тоже можно короче записать. И не знаю что быстрее получится. Быстрее мутабельные варианты.

Добавлено через 9 минут
Aха, вот как.

0

KolodeznyDiver,
@ <- очень дорогостоящая операция

1

Сообщение от _Ivana Так автор специально вместо наивного рекурсивного решения свертки применил технику то ли трамплинов, то ли еще чего-то (сейчас уже и не помню, но можно найти статью и посмотреть) - для того, чтобы перенести вычисления со стека в кучу и избежать стековерфлоу

CPS. в хаскеле тоже присуствует
https://en.wikibooks.org/wiki/... sing_Style (+монады) хотя там и не так заметно. выглядеть будет грубо так работает медленее чем аккумулятор

1

pycture, axa, а потомИ как это помогает избежать стековер? Техника известна. В фентезийном мире так учат делать правую свёртку из левой (для тренировки магспособностей).

0

Сообщение от KolodeznyDiver И как это помогает избежать стековер?

результат копится не на стеке, а на хипе. хип значительно толще

0

Ага, типа нагребатор цепочки отложенных вычислений в куче из-за строгой семантики... https://habrahabr.ru/post/57503/

0

Сообщение от pycture результат копится не на стеке, а на хипе. хип значительно толще

не, я правда, не понимаю. Помню что в шарпе ссылки в куче, не ссылки в стеке. Но тут то строится цепочка вызовов функций, аргументы их в стеке. Что в куче? Или для частично применённых функций применённые аргументы в куче, типа объекты такие создаются для каждого частичного применения?

Добавлено через 1 час 1 минуту

0