Форум программистов, компьютерный форум, киберфорум
F# .NET
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.96/56: Рейтинг темы: голосов - 56, средняя оценка - 4.96
0 / 0 / 0
Регистрация: 02.02.2021
Сообщений: 9

Присоединение пустого листа

02.02.2021, 18:36. Показов 12032. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте!
На учебе дали задание написать функцию union. Дано два листа, на выходе надо вернуть объединенный лист без повторений.
Встроенные функции использовать нельзя.

Написала следующее:

F#
1
2
3
4
 let rec union alist blist =
    match alist@blist with
        | []->[]
        | h::rest -> if memberof h rest then union rest [] else h::(union rest [])
На что получила комментарий что такое работает, но что вот это
F#
1
union rest []
плохо. Объясните, пожалуйста, почему? (memberof возвращает true если элемент есть в листе, и false если нет)

Добавлено через 41 минуту
Пока нашла только что @ копирует левый лист. (Если я правильно понимаю ответы тут https://stackoverflow.com/ques... ng-objects).
Значит ли это, что более оптимальным решением может быть union [] rest ?
То есть копирование пустого листа должно же быть быстрее...
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
02.02.2021, 18:36
Ответы с готовыми решениями:

Копир даже при копировании пустого листа делает черную полоску
У меня есть копир Xerox WorkCentre 5016. Он при копировании листа делает на копии черную полоску с какими-то "засечками", даже...

Сохранение текущего листа с сохранением имени листа и присвоением новой книге имени текущего листа
Sub Save_as() With Application.FileDialog(msoFileDialogSaveAs) .InitialFileName = ThisWorkbook.Path & "\" & "new book name"...

создание нового листа (заданного формата) с переносом данных с другого листа
Добрый день, формунчане! Большая просьба с созданием макроса. Необходимо разработать документ, который бы позволял создавать...

11
Модератор
Эксперт функциональных языков программирования
3132 / 2279 / 469
Регистрация: 26.03.2015
Сообщений: 8,870
03.02.2021, 11:10
Цитата Сообщение от Almaninyo Посмотреть сообщение
alist@blist
Использование внутренней функции?


Цитата Сообщение от Almaninyo Посмотреть сообщение
Пока нашла только что @ копирует левый лист.
Да. Так как мы можем добавлять только в начало списка, приходится все элементы первого списка добавлять во второй.

Цитата Сообщение от Almaninyo Посмотреть сообщение
Значит ли это, что более оптимальным решением может быть union [] rest ?
Да. Но я бы переписал без использования List.append.

Добавлено через 13 минут
Что-то типа такого.
F#
1
2
3
4
5
6
let union alist blist =
    let rec add a b =
        match a with
        | [] -> b
        | h::rest -> if List.contains h b then add rest b else h::(add rest b)
    add alist (add blist [])
Но можно переписать с использованием аккумулятора, чтобы сделать рекурсию хвостовой.
"add blist []" копирует blist без повторений

Добавлено через 4 минуты
Обнаружил у себя ошибку: наличие h проверяется в b и не проверяется в rest
Исправил:
F#
1
2
3
4
5
6
7
8
9
10
let union alist blist =
    let add1 x a = 
        if List.contains x a then a else x::a
 
    let rec add a b =
        match a with
        | [] -> b
        | h::rest -> add1 h (add rest b)
        
    add alist (add blist [])
0
Модератор
Эксперт функциональных языков программирования
3132 / 2279 / 469
Регистрация: 26.03.2015
Сообщений: 8,870
03.02.2021, 11:48
Лучший ответ Сообщение было отмечено Almaninyo как решение

Решение

Ещё вопрос - какое вхождение из нескольких оставлять? Если оставлять первое вхождение, то код будет таким:
F#
1
2
3
4
5
6
7
let union alist blist =
    let rec add a b =
        match a with
        | [] -> b
        | h::tail -> if List.contains h b then add tail b else add tail (h::b)
        
    [] |> add alist |> add blist |> List.rev
Заодно избавились от нехвостовой рекурсии.
List.contains у Вас уже есть (memberof), а List.rev написать несложно (разворачивает список).
1
0 / 0 / 0
Регистрация: 02.02.2021
Сообщений: 9
03.02.2021, 19:55  [ТС]
Спасибо за ответы, какое вхождение оставлять - не важно, и переворачивать список, я думаю, тоже не надо - по условиям на выходе должно быть просто множество.
То есть я так понимаю в принципе присоединение списков - дорогая операция?
И еще вопрос тогда, а чем плоха хвостовая рекурсия? На первых лекциях по F# у меня наоборот сложилось впечатление (очевидно, ошибочное ), что рекурсия - это наше всё, как Пушкин ...
0
41 / 28 / 13
Регистрация: 31.10.2019
Сообщений: 126
03.02.2021, 19:58
а нельзя просто объединить два списка оператором @ ?
0
0 / 0 / 0
Регистрация: 02.02.2021
Сообщений: 9
03.02.2021, 22:37  [ТС]
нужно чтобы в объединенном списке не было дубликатов. При этом оба списка на входе могут их содержать
0
41 / 28 / 13
Регистрация: 31.10.2019
Сообщений: 126
03.02.2021, 23:20
чтобы удалить дубликаты, список достаточно преобразовать во множество. а затем, множество - снова преобразовать в список

F#
1
list1 @ list2 |> Seq.distinct |> Seq.toList
Добавлено через 11 минут
F#
1
let notDublicated = [1;2;3;4] @ [3;4;5;6] |> Seq.distinct |> Seq.toList
0
Модератор
Эксперт функциональных языков программирования
3132 / 2279 / 469
Регистрация: 26.03.2015
Сообщений: 8,870
04.02.2021, 00:27
Цитата Сообщение от Almaninyo Посмотреть сообщение
То есть я так понимаю в принципе присоединение списков - дорогая операция?
Слияние списков - О(эн).

Цитата Сообщение от Almaninyo Посмотреть сообщение
а чем плоха хвостовая рекурсия?
Всем хороша. Поэтому избавились от нехвостовой рекурсии, сделав ее хвостовой.

Добавлено через 59 секунд
zverjuga,
В задании "Встроенные функции использовать нельзя."
0
Модератор
Эксперт функциональных языков программирования
3132 / 2279 / 469
Регистрация: 26.03.2015
Сообщений: 8,870
04.02.2021, 00:48
Цитата Сообщение от Almaninyo Посмотреть сообщение
На первых лекциях по F# у меня наоборот сложилось впечатление (очевидно, ошибочное ), что рекурсия - это наше всё,
Так и есть... в идеальном мире математики/информатики. Но в суровой реальности компиляторы пока! несовершенны. Они не всегда могут преобразовать функциональный код в оптимальный машинный код. Поэтому мы сталкиваемся с тем, что рекурсия медленнее цикла, а размер стека ограничен. Современные компиляторы умеют заменять хвостовую рекурсию циклом, а нехвостовую обычно нет (хотя это легко можно сделать с помощью относительно простых формальных преобразований).

Так же, в большинстве (90%) случаев рекурсию можно заменить понятиями более высокого порядка - отображение, свертка, фильтр. Конечно, утверждение "сумма списка - это голова (первый элемент) плюс сумма хвоста" выглядит очень математическим. Но лучше сказать, что "сумма списка - это свертка по сложению", оставляя за кадром низкоуровневые детали реализации вычисления свертки. Поэтому в учебном коде от Вас требуют использования рекурсии (для понимания), а в реальном коде лучше вместо явного использования рекурсии использовать встроенные функции map, filter, fold.
1
0 / 0 / 0
Регистрация: 02.02.2021
Сообщений: 9
04.02.2021, 16:28  [ТС]
Цитата Сообщение от Shamil1 Посмотреть сообщение
[] |> add alist |> add blist |> List.rev
Тут, правда, ошибка. Если на входе например листы [0;1] [0]

F#
1
add ([] |> add alist |> add blist ) []
должно сработать
0
Модератор
Эксперт функциональных языков программирования
3132 / 2279 / 469
Регистрация: 26.03.2015
Сообщений: 8,870
04.02.2021, 19:02
Цитата Сообщение от Almaninyo Посмотреть сообщение
Тут, правда, ошибка. Если на входе например листы [0;1] [0]
Какая ошибка?

F#
1
2
3
4
5
6
7
8
9
let union alist blist =
    let rec add a b =
        match a with
        | [] -> b
        | h::tail -> if List.contains h b then add tail b else add tail (h::b)
        
    [] |> add alist |> add blist |> List.rev
    
printfn "%A" <| union [0;1] [0]
Результат правильный:
Code
1
[0; 1]
0
0 / 0 / 0
Регистрация: 02.02.2021
Сообщений: 9
05.02.2021, 00:23  [ТС]
Да, извиняюсь, что-то я не так протестировала. Все в порядке, спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
05.02.2021, 00:23
Помогаю со студенческими работами здесь

Запуск макроса (написанного для актив. нужного листа) с др. листа (сложно)
Подскажите пожалуйста, есть большие макросы которые работают на активном листе, существует какой-то способ не прописывая везде нужный лист...

Сохранение листа книги в файле - проблема с защитой листа и привязкой макросов
С толкнулся с такой проблемой при сохранении листа в файле вот код который сохраняет лист в файле Sub red_row() ...

Считать данные с листа EXCEL в Listview. Выбор листа в Combobox
Как считать с листа Excel - где его имя - выбранное значение из combobox. Если я правильно понял то это событие ...

Перенос значений с одного листа в разные ячейки второго листа
прошу помощи, форумчане. Перед нами была поставлена задача оптимизировать наши расчеты. Суть оптимизации - на листе &quot;данные&quot;...

В ячейке B2 второго листа вывести значение ячейки A1 первого листа
Необходимо чтобы, например, в ячейке B2 второго листа автомотически вводилось значение ячейки A1 первого листа.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru