CODEWITHSUNDEEP
haskell
derpnallday
derpnallday

Reputation: 49

Haskell: finding tuples of elements that equal n

I am trying to write a function in Haskell that takes a list of integers and an integer n and finds all tuples that equal n. So far I have an implementation that works

tuplesum :: (Eq b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = [(x1,x2) | x1 <- xs, x2 <- xs, x1 + x2 == n, x1 <= x2]

so if I gave this function the input 

tuplesum [5,1,4,0,5,6,9] 10

the output is [(5,5),(5,5),(1,9),(4,6),(5,5),(5,5)] However, I have 4 duplicates of the (5,5) solution. I would like the function to output [(5,5),(1,9),(4,6)]but I cant figure out how to constrain tuples that have the same integers without removing it as a solution entirely.

Upvotes: 2

Views: 380

Answers (2)

fp_mora
fp_mora

Reputation: 714

I just really liked your function tuplesum xs n = [(x1,x2) | x1 <- xs, x2 <- xs, x1 + x2 == n, x1 <= x2] because it is a Cartesian product and it eliminates most symmetrical pairs that would otherwise constitute about half. It gets the predicate matches so very well. The only problem remaining is the duplicate elements. I had forgotten about this until recently and Pg. 86 of Graham Hutton's "Programming in Haskell" and his rmdups function. What I like about his rmdups is that it neither depends on imports.

rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs) = x : filter (/= x) (rmdups xs)

Hutton's solution is wonderfully general and classically recursive. I did not want to post his solution here without adding something original so here is a list comprehension to eliminate duplicates of any data type including tuples.

rmdups ls = [d|(z,d)<- zip [0..] ls, notElem d $ take z ls]

You can place either rmdups function in front of your function rmdups.tuplesum Your function eliminates most symmetrical pairs so rmdups does not.

rmdups [(5,5),(5,5),(1,9),(4,6),(5,5),(5,5)]

[(5,5),(1,9),(4,6)]

Or

rmdups "abcabcdefdef" OR "abcdefabcdef"

"abcdef"

Upvotes: 0

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476584

Symmetry breaking in tuple generation

I have the impression that you are looking for a way to select two elements out of the list such that x1 is always located before x2.

A common way to always let x2 iterate over the remainder of the list is by using tails :: [a] -> [[a]]. For a list, tails will generate a list of all tails of the list, starting with the list itself. For example:

Prelude Data.List> tails [1, 4, 2, 5]
[[1,4,2,5],[4,2,5],[2,5],[5],[]]

We can use this with pattern matching to select one element, and get a reference to the remaining element. For example:

import Data.List(tails)

tuplesum :: (Eq b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = [(x1,x2) | (x1:x2s) <- tails xs, x2 <- x2s, x1 + x2 == n]

Note that it is still possible to obtain duplicates here, for example if 5 would occur three times in the list, since in that case x1 can select the first 5, and then x2 can select the second 5 as well as the last one. We can make use of a uniqness filter like nub :: Eq a => [a] -> [a] for this:

import Data.List(nub, tails)

tuplesum :: (Eq b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = nub [(x1,x2) | (x1:x2s) <- tails xs, x2 <- x2s, x1 + x2 == n]

Note that it is however still better to use tails here, since it will increase performance, since we will simply generate a smaller amount of duplicates in the first place.

Using a hashset to obtain the "other" element

The above algorithm is still O(n2), and not very fast. We can however solve the problem the other way around: we can first construct a HashSet of the elements, and the for each element x1, check if n - x1 is a member, like:

import Data.Hashable(Hashable)
import Data.HashSet(fromList, member)

tuplesum :: (Ord b, Hashable b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = nub [(x1,x2) | x1 <- xs, let x2 = n-x1, x1 <= x2, member x2 hs]
    where hs = fromList xs

But the runtime is still O(n2) because of the nub, we can however use a hashNub :: (Eq a, Hashable a) => [a] -> [a] here:

hashNub :: (Eq a, Hashable a) => [a] -> [a]
hashNub = go HashSet.empty
  where
    go _ []     = []
    go s (x:xs) =
      if x `HashSet.member` s
      then go s xs
      else x : go (HashSet.insert x s) xs

and then let it work with:

import Data.Hashable(Hashable)
import Data.HashSet(fromList, member)

tuplesum :: (Ord b, Hashable b, Num b) => [b] -> b -> [(b, b)]
tuplesum xs n = hashNub [(x1,x2) | x1 <- xs, let x2 = n-x1, x1 <= x2, member x2 hs]
    where hs = fromList xs

Now it works in O(n log n).

Upvotes: 6

Related Questions