[Haskell-cafe] Tuple

[Richard O'Keefe]

On 11/04/2011, at 4:49 AM, Anwar Bari wrote:

> HI Cafe 
>     I have to make a function to check that I have one occurrence of the last 
> element (z) of the same list [a,b] in the tuple 
> 
> [([a,b],z)] 
> For example
> [([1,2],3),([1,1],5),([1,3],6).......]  this is true because there is one single 
> z for each single list.
> 
> while this one is false 
> [([1,2],3),([1,2],5),([1,3],6).......] because 3&5 were found for the same list 
> [1,2]
> 
> any Idea how to code this Fn. 

Let m = length xs

has_duplicate_key [] = False
has_duplicate_key ((k,v):xs) =
   if null [v' | (k',v') <- xs, k' == k]
      then has_duplicate_key xs
      else True

is perhaps the obvious code, but it's O(n**2).
Sorting on the first element of the pairs takes
O(n.lg n) time, and then checking for two adjacent
(k,v),(k,v') pairs takes O(n).

You can also use Data.Map in a fairly obvious way.