LINUX.ORG.RU
решено Форум — Development  

Определить, есть ли элемент, общий для двух списков

 ,


0

2

Есть два списка, А и B. Для каждого списка определен метод exists, который выдает true, если переданный ему аргумент присутствует в списке. Как пользуясь этим методом, определить наличие общих элементов в списках A и Б? Описать в функц стиле.

★★★

только не точеный

anonymous
()

Забыл уже синтаксис Haskell'а, но вот что-то такое видится:

filter(A ++ B, \item -> exists(A, item) and exists(B, item))
CARS ★★★★
()

Для поиска пересечения двух множеств - это не самая оптимальная (с т.з O(g(N))) стратегия её реализации.

nerdogeek ★
()
Последнее исправление: nerdogeek (всего исправлений: 1)
Ответ на: комментарий от nerdogeek

Для поиска пересечения двух множеств - это не самая оптимальная (с т.з O(g(N))) стратегия её реализации.

оптимальная, шмоптимальная. учительница сказала, надо через exists и на списках

MyTrooName ★★★★★
()
Ответ на: комментарий от MyTrooName

а, я тред по диагонали просмотрел

anonymous
()
Ответ на: комментарий от Legioner

Что такое Cons(x,xs), что оно обозначает?

LIKAN ★★★
() автор топика
Ответ на: комментарий от Legioner

На самом деле задание звучит несколько по другому, есть список слов А, для него определен метод exists и текст (строка) Б, для которого нужно определить, есть ли в нем слово из списка, для него определен метод contains. Т е получается, что в реализации придется обязательно применять exists к А и contains к Б, а у вас как-то одним применением обошлось.

LIKAN ★★★
() автор топика 
exists(X, [X|T]).
exists(X, [_|T]) :- exists(X, T).

common(X, L1, L2) :- exists(X, L1), exists(X, L2).

?- exists(4, [1,2,3,X,5]).
X = 4 .

?- common(X, [1,2,3], [6,5,4,3,2]).
X = 2 ;
X = 3 ;
false.
hlebushek ★★
()
Ответ на: комментарий от LIKAN

для этого есть «более лучший способ одеваться»

для текста строишь суффиксное дерево ( O(NlogN) а можид O(N)) а затем опрашиваеш его твоими словами ( очень быстро кстати ибо префиксы сила).

qulinxao ★★☆
()

Функциональщиной здесь и не пахнет. Алгоритм как был, так и остался: а) проходим по первому списку; б) если элемент из первого списка есть во втором, добавляем его в результирующий список.

В функцональном стиле делается из filter и any.

Никаким настоящим пересечением здесь и не пахнет, но именно такой алгоритм используется в Data.List.intersect.

Для получения настоящего пересечения списки нужно отсортить, убрать дубликаты и только после этого засунуть в intersect. Короче, адъ полнейший.

Намного проще пользоваться специальной структурой, например Set из штатного пакета containers. Для нее пересечение выполняется значительно эффективнее. Подробнее, должно быть у К. Окасаки.

PS: если уж функциональщина, то забудь слово «метод».

Macil ★★★★★
()

Неразрешимо. Уточни задание.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development