哈斯克尔与重复相交 [英] Haskell intersection with duplicates

问题描述

我是Haskell的新手，这很简单，但我一直在网上搜索一个小时而没有找到方便的答案。

我想要什么是一个返回两个列表的交集的函数：列表中存在两个列表中的元素，考虑到重复。

我认为函数 intersect 会是我想要的，但正如文档中所述，如果第一个列表包含重复项，结果也是如此。例如：

  [1,2,2,2,3,4]`intersect` [6,4,4,2 ，2] == [2,2,2,4] 
  

这不是我想要的，因为[2,2,2,4]不是[6,4,4,2,2]的一部分，因为该列表中只有两个2。我希望的结果是：

$ p $ [1,2,2,2,3,4]`intersect` [6,4， 4,2,2] == [2,2,4]


这怎么能完成？

解决方案

一种低效率的方式是

  intersect'xs ys = xs \\（xs \\ ys）
  

例如

  [1,2,2,2,3,4] \\\ [6,4,4， 2,2] == [1,2,3] 
 [1,2,2,2,3,4] \\ [1,2,3] == [2,2,4] 
  

和

  [6,4,4,2,2] \\ [1,2,2,2,3,4] == [6,4] 
 [6,4,4， 2,2] \\ [6,4] == [4,2,2] 
  

从 http://hackage.haskell.org/package/base-4.7。 0.1 / docs / Data-List.html ：

在 xs \\ ys ，首先出现 ys 的每个元素（如果有）已从 xs 中删除​​。因此



 （xs ++ ys）\\ xs == ys。 
  




I am new to Haskell and this has to be quite simple, but I have been searching the net for an hour without finding a convenient answer.

What I want is a function that returns an 'intersection' of two lists: a list of the elements that exists in both lists, taking account of duplicates.

I thought the function intersect would be what I wanted but, as stated in the docs, if the first list contains duplicates, so will the result. E.g.:

[1,2,2,2,3,4] `intersect` [6,4,4,2,2] == [2,2,2,4]

This is not what I want, since [2,2,2,4] isn't a part of [6,4,4,2,2] because there are only two 2's in that list. My desired result is:

[1,2,2,2,3,4] `intersect` [6,4,4,2,2] == [2,2,4]

How could this be accomplished?

解决方案

One inefficient way is

intersect' xs ys = xs \\ (xs \\ ys)

For example

[1,2,2,2,3,4] \\ [6,4,4,2,2]   == [1,2,3]
[1,2,2,2,3,4] \\ [1,2,3]       == [2,2,4]

And

[6,4,4,2,2]   \\ [1,2,2,2,3,4] == [6,4]
[6,4,4,2,2]   \\ [6,4]         == [4,2,2]

From http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-List.html :

In the result of xs \\ ys, the first occurrence of each element of ys in turn (if any) has been removed from xs. Thus

(xs ++ ys) \\ xs == ys.

这篇关于哈斯克尔与重复相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！