[Haskell-cafe] function unique

[Dan Weston]

Alexteslin wrote:
 > I'v got it - it produces the right output.
 > Thank you.

Now that you've done the exercise, the fun starts! What assumptions did 
you build in to your solution?

1) You just need uniqueness, so counting the number of copies is not 
only overkill, but requires you to go through the entire list to count them.

2) The list might be infinite, and your function should work if you make 
only want to use the first part of it, so the following should return 
[1,2,3,4,5] in a finite amount of time:

take 5 (unique [1..])

Your algorithm fails both of these. Consider a *lazy* approach:

1) Keep the head of the list
2) Then filter the tail, keeping only elements different from the head
3) Then put the two together

Don't worry in step #2 about having an infinite number of list elements 
to be filtered out of the list. Think of it like asking a lazy child to 
clean the house. They're only going to do it just before mom gets home 
(who knows, with any luck she'll be in a car crash and forget about 
having asked you to clean!)

This works for infinite lists, and puts off the work until you actually 
need the elements.

I won't cheat you out of the fun, but here's the solution to a *very* 
similar problem using the Sieve of Eratosthenes to find prime numbers:

isNotDivisor divisor dividend = dividend `rem` divisor /= 0

keepOnlyLowestMultiple (x:xs) =
   x : keepOnlyLowestMultiple (filter (isNotDivisor x) xs)

primes = keepOnlyLowestMultiple [2..]

Dan

> Brent Yorgey wrote:
>> The problem with your second implementation is that elements which occur
>> more than once will eventually be included, when the part of the list
>> remaining only has one copy. For example:
>>
>> unique2 [1,1,2,4,1]
>> = unique2 [1,2,4,1]
>> = unique2 [2,4,1]
>> = 2 : unique2 [4,1]
>> = 2 : 4 : unique2 [1]
>> = 2 : 4 : 1 : unique2 []   -- only a single 1 left, so it gets mistakenly
>> included
>> = [2,4,1]
>>
>> When you determine that a certain number should not be included in the
>> output, you need to delete all remaining occurrences of it from the list,
>> so
>> it won't get included later.
>>
>> unique2 (x:xs)
>>         |elemNum2 x xs == 1 = x:unique2 xs
>>         |otherwise = unique2 (deleteElt x xs)
>>
>> I'll let you figure out how to implement the deleteElt function.
>>
>> hope this is helpful!
>> -Brent
>>
>> On 7/10/07, Alexteslin <alexteslin at yahoo.co.uk> wrote:
>>>
>>> Hi, i am a beginner to Haskell and i have a beginner's question to ask.
>>>
>>> An exercise asks to define function unique :: [Int] -> [Int], which
>>> outputs
>>> a list with only elements that are unique to the input list (that appears
>>> no
>>> more than once).  I defined a function with list comprehension which
>>> works
>>> but trying to implement with pattern matching and primitive recursion
>>> with
>>> lists and doesn't work.
>>>
>>> unique :: [Int] -> [Int]
>>> unique xs = [x | x <- xs, elemNum2 x xs == 1]
>>>
>>>
>>> elemNum2 :: Int -> [Int] -> Int
>>> elemNum2 el xs = length [x| x <- xs, x == el]
>>>
>>> //This doesn't work, I know because the list shrinks and produces wrong
>>> result but can not get a right //thinking
>>>
>>> unique2 :: [Int] -> [Int]
>>> unique2 [] = []
>>> unique2 (x:xs)
>>>         |elemNum2 x xs == 1 = x:unique2 xs
>>>         |otherwise = unique2 xs
>>>
>>>
>>> Any help to a right direction would be very appreciated, thanks.
>>> --
>>> View this message in context:
>>> http://www.nabble.com/function-unique-tf4058328.html#a11528933
>>> Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
>