Как извлечь те же элементы из двух списков в Haskell?

вот мой вопрос: Как извлечь те же элементы из двух списков одинаковой длины в другой список? Например: в двух списках [2,4,6,3,2,1,3,5] и [7,3,3,2,8,8,9,1] ответ должен быть [1,2,3,3]. Обратите внимание, что порядок несуществен. Я фактически использую длину возвращаемого списка.Как извлечь те же элементы из двух списков в Haskell?

Я попытался это:

sameElem as bs = length (nub (intersect as bs))

но проблема nub удаляет все дупликации. Результатом использования моей функции в первом примере является 3 длина [1,3,2] вместо 4 длина [1,3,3,2]. Есть ли решение? Спасибо.

источник

2014-09-10 user3928256

Является ли позиция уместным здесь, как пример предполагает? Если это так, вы можете просто закрепить список в [(1,1), (3,3), (3,3), (2,2), (4,5) ...] и отбросить записи, в которых fst не является snd. –

Положение здесь не имеет отношения. Я изменил пример. Спасибо. – user3928256

Хорошо, тогда есть другое подобное решение. Заметим, что '(\ l-> \ k-> [x | x <-l, y <-k, x == y]) [2,4,6,3,2,1,3,5] [7 , 3,3,2,8,8,9,1] 'находит все совпадения, восстанавливая' [2,3,3,2,1,3,3] '. Вы можете исключить двойной подсчет, индексируя первый список и в конце выпадающие значения с повторяющимися вхождениями. –

Поскольку положение, кажется, не имеет значения, вы можете просто сортировать списки заранее, а затем пройти в обоих списках:

import Data.List (sort) 

intersectSorted :: Ord a => [a] -> [a] -> [a] 
intersectSorted (x:xs) (y:ys) 
| x == y = x : intersectSorted xs ys 
| x < y  = intersectSorted xs (y:ys) 
| x > y  = intersectSorted (x:xs) ys 
intersectSorted _ _ = [] 

intersect :: Ord a => [a] -> [a] -> [a] 
intersect xs ys = intersectSorted (sort xs) (sort ys)

Обратите внимание, что это также можно добиться этого с Map:

import Data.Map.Strict (fromListWith, assocs, intersectionWith, Map) 

type Counter a = Map a Int 

toCounter :: Ord a => [a] -> Counter a 
toCounter = fromListWith (+) . flip zip (repeat 1) 

intersectCounter :: Ord a => Counter a -> Counter a -> Counter a 
intersectCounter = intersectionWith min 

toList :: Counter a -> [a] 
toList = concatMap (\(k,c) -> replicate c k) . assocs 

intersect :: Ord a => [a] -> [a] -> [a] 
intersect xs ys = toList $ intersectCounter (toCounter xs) (toCounter ys)

источник

2014-09-10 08:31:50 Zeta

Мне жаль, что приведенный мною пример неуместен. На самом деле позиция должна быть несущественной. – user3928256

@ user3928256: Обратите внимание, что в вашем текущем примере отсутствует результат «2». – Zeta

О, спасибо. Я исправил это. – user3928256

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

import Data.List 

same (x:xs) ys = if x `elem` ys 
       then x:same xs (delete x ys) 
       else same xs ys 
same [] _ = [] 
same _ [] = []

delete x ys в тогдашней статье важно, без этого удалить командные элементы из первого списка, которые происходят по крайней мере один раз будет подсчитываться каждый раз, когда они встречаются.
Обратите внимание, что результат не сортируется, так как вас интересует только длина результирующего списка.

источник

2014-09-10 12:58:54

Спасибо! Это именно то, что я буду делать на Java. Раньше я не знал «удалить» в Haskell. – user3928256

import Data.List (delete) 

mutuals :: Eq a => [a] -> [a] -> [a] 
mutuals []  _    = [] 
mutuals (x : xs) ys | x `elem` ys = x : mutuals xs (delete x ys) 
        | otherwise = mutuals xs ys

дает

mutuals [2,4,6,3,2,1,3,5] [7,3,3,2,8,8,9,1] == [2,3,1,3]

источник

2017-02-15 06:04:27 suchtgott

Как извлечь те же элементы из двух списков в Haskell?

ответ

Смежные вопросы