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

@Anastasia_ · Регистрация: 23.11.2014

Студворк — интернет-сервис помощи студентам

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

@_Ivana · 22.12.2016, 23:31

Не по теме:

Фигасе я мимо прошел... А тут внезапный взрыв жизни в разделе :)

Сообщение от Ev_Hyper

С OCaml - ом не довелось познакомиться.

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

@korvin_ · 22.12.2016, 23:34

Сообщение от pycture

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

Не самое…

Haskell
1
2
3
delsnd []       = []
delsnd [x]      = [x]
delsnd (x:y:zs) = x : delsnd zs

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

Сообщение от _Ivana

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

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

@I2um1 · 22.12.2016, 23:36

Сообщение от Ev_Hyper

Visual F# Power Tools

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

Сообщение от Ev_Hyper

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

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

Сообщение от Ev_Hyper

Почему?

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

Сообщение от Ev_Hyper

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

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

@korvin_ · 22.12.2016, 23:41

Сообщение от I2um1

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

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

@I2um1 · 22.12.2016, 23:42

Сообщение от korvin_

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

Угу.

@Ev_Hyper · 22.12.2016, 23:43

Сообщение от I2um1

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

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

Сообщение от I2um1

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

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

Сообщение от I2um1

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

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

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

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

@korvin_ · 22.12.2016, 23:45

Сообщение от I2um1

OCaml считается родителем F#

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

Сообщение от I2um1

истину стоит искать…

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

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

Сообщение от I2um1

Угу.

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

@I2um1 · 22.12.2016, 23:58

Сообщение от korvin_

что они не нужны?

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

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

Сообщение от korvin_

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

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

@pycture · 23.12.2016, 11:00

Сообщение от I2um1

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

JetBrains

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

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

Сообщение от korvin_

Не самое…

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

Haskell
1
2
    delsnd (x:y:zs) = x : delsnd zs
    delsnd x        = x

Сообщение от I2um1

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

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

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

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

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

@Curry · 23.12.2016, 22:11

Тривиальное решение.

F#
1
2
3
4
5
let rec delscd lst =
          match lst with
          | [] -> []
          | [x] -> [x]
          | x::_::xs -> x:: delscd xs

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

@pycture · 23.12.2016, 22:20

Сообщение от KolodeznyDiver

Тривиальное решение

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

F#
1
2
3
let rec delscd = function
    | x :: _ :: xs -> x :: delscd xs
    | xs -> xs

В реале,...

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

@Curry · 23.12.2016, 22:28

Сообщение от pycture

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

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

Сообщение от pycture

оно издохнет на переполнении стека

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

@_Ivana · 24.12.2016, 04:28

Лесник в эту тему уже заглядывал, сейчас очередь Капитана Очевидности

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

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

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

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

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

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

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

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

Но это я шучу, я вроде не настолько идиот ~~как выгляжу~~, чтобы разжигать холивар с разумными людьми по такому поводу

@Curry · 24.12.2016, 09:33

Хвостовой без реверса результата

F#
1
2
3
4
5
6
let delscd = 
    let rec go res lst= 
          match res,lst with
          | r,x::_::xs -> go (r @ [x]) xs
          | r,x -> r @ x
    go []

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

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

F#
1
2
3
4
5
let delscd = 
    let rec go r = function 
          | x::_::xs -> go (r @ [x]) xs
          | x -> r @ x
    go []

@Ev_Hyper · 24.12.2016, 12:38

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

@pycture · 24.12.2016, 16:58

Сообщение от _Ivana

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

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

F#
1
2
3
4
5
let rec d2 xs cont =  
    match xs with
    | a :: _ :: t -> 
        d2 t (fun y -> cont (a :: y))
    | t             -> cont t

работает медленее чем аккумулятор

@Curry · 24.12.2016, 19:50

pycture, axa, а потом

F#
1
let delscd lst = d2 lst id

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

F#
1
let foldr f b ta = List.fold (fun a e -> f e >> a) id ta b

@pycture · 24.12.2016, 20:00

Сообщение от KolodeznyDiver

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

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

@_Ivana · 24.12.2016, 20:20

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

@Curry · 24.12.2016, 21:54

Сообщение от pycture

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

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

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

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.

@Anastasia_ 0 / 0 / 0 Регистрация: 23.11.2014 Сообщений: 10

	Описать функцию, удаляющую из списка каждый второй элемент 13.12.2016, 20:12. Показов 6774. Ответов 43 Метки нет (Все метки) Помогите реализовать функцию,удаляющую из списка каждый второй элемент. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	24.12.2016, 04:28
	Лесник в эту тему уже заглядывал, сейчас очередь Капитана Очевидности Сабжевая задача про то, как из списка выделить подсписок по определенному критерию. То есть, говоря в общем, абстракция 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

@Ev_Hyper Заблокирован
	24.12.2016, 12:38
	KolodeznyDiver, `@` <- очень дорогостоящая операция 1

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	24.12.2016, 20:20
	Ага, типа нагребатор цепочки отложенных вычислений в куче из-за строгой семантики... https://habrahabr.ru/post/57503/ 0