Filter function in haskell

Question

I have two lists

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

the result i want to get is the common part of these two lists: [3,4,5,6] I tried to use filter function, but it always output error

filter (== a) b 
filter (== b) a

then combine them together

Answer 1

If your lists are built of increasing positive numbers, as they seem to be, you can have an O(n) solution instead of the quadratic intersect and friends:

ordzip :: (Ord a, Num a) => [a] -> [a] -> [(a,a)]
ordzip a b = g a b where 
  g a@(x:r) b@(y:q)  | x < y     = (x,0) : g r b 
                     | y < x     = (0,y) : g a q 
                     | otherwise = (x,y) : g r q 
  g a       []                   = [(x,0) | x <- a]
  g []      b                    = [(0,y) | y <- b]

diff xs ys = [x | (x,y)<- ordzip xs ys, x/=0 && y==0 ]  -- set difference
meet xs ys = [y | (x,y)<- ordzip xs ys, x/=0 && y/=0 ]  --     intersection
joyn xs ys = [z | (x,y)<- ordzip xs ys, let z=max x y]  --     union

The one you want here is meet:

Prelude> meet [1,2,3,4,5,6] [3,4,5,6,7,8,9]
[3,4,5,6]

The above is just a toy code, to give us an idea. Normally, you would use Maybe a to convey the information of a possible value, instead of using the specially separated element, like I do with 0 above. A value of type Maybe a can be either Nothing or Just a.

But actually, we would never have a (Nothing, Nothing) combination, as we choose either one of the two or both in ordzip, but never none, right? So what we really need here is Data.These.These:

import Data.These

ordzip :: (Ord a) => [a] -> [b] -> [These a b]
ordzip a@(x:t) b@(y:r) = case compare x y of
                            LT -> This  x   : ordzip t b 
                            GT -> That    y : ordzip a r 
                            EQ -> These x y : ordzip t r 
ordzip a       []      = map This a
ordzip []      b       = map That b

diff = catThis .: ordzip 
meet = map snd .: catThese .: ordzip
joyn = map (these id id const) .: ordzip
-- infixr 8 .: ; (f .: g) x y = f (g x y)

Re-writing these three set functions by merging their definitions with the ordzip above can lead to more efficient code in some cases (e.g. there's no need to attach the extra tails with ordzip a [] or ordzip [] b just so they are discarded in meet). Moreover, it would made meet (or diff) properly productive when one of its argument lists is infinite and the other is finite. The three definitions above are more of an executable specification.

Also sometimes we might need to decide the equality with some additional predicate, not just plain compare, and we might construct the elements of the result differently, as we might need them (e.g. including both x and y in the results in meet).

These functions work with ordered lists. There's also the data-ordlist package for this with much more tools in it.

Answer 2

intersect a b = [x| x <- a, x `elem` b]

Using list a argument as a generator in x <- a. The Boolean expression x elem b filters each element. If True added to x else discarded.

Answer 3

Here's a one-liner

[x | x <- a, y <- b, x == y ]

Answer 4

While you can directly use the intersect function on lists, I should recommend you use a more efficient, dedicated container instead of lists. If you really mean to express sets, then why don't you use Data.Set?

Prelude> import qualified Data.Set as Set
Prelude Set> let a = Set.fromList [1,2,3,4,5,6]; b = Set.fromList [3,4,5,6,7,8,9]
Loading package array-0.5.0.0 ... linking ... done.
Loading package deepseq-1.3.0.2 ... linking ... done.
Loading package containers-0.5.5.1 ... linking ... done.
Prelude Set> Set.intersection a b
fromList [3,4,5,6]

This is O(n ⋅ log n) rather than O(n²), much faster for large sets. Also, it expresses your intention much better if you use a dedicated set type: it makes it clear that you count out duplicates, and don't have any nontrivial ordering of the elements.

The downside is, the elements need to be Ord because the implementation uses the canonical ordering. An alternative would be HashSet.

Answer 5

If you look just for common elements use intersect from Data.List

a `intersect` b == [3,4,5,6]

A related question: is there union and intersect Haskell Prelude implementation?

Answer 6

you need to use intersect function to take common elements from two list.

See how to use intersect function on lists.

Answer 7

You need to iterate one list using filter and check if the elements from that list is present in the other list using the elem function:

inte :: Eq a => [a] -> [a] -> [a]
inte a b = filter (\x -> x `elem` a) b

Another way is see if there is any built-in library function present. As a first step, write the type signature for the function you want:

[a] -> [a] -> [a]

Then run a hoogle query to see if there is any prebuilt function for that. There is an intersect function in Data.List which achieves exactly your objective.