[Haskell-cafe] function unique

[Alexteslin]

Thank you for your great suggestions, i will try to use lazy evaluation of
course.  But as a beginner I am on Chapter 7 of the textbook and will soon
(perhaps in few weeks) move on to that, which is Chapter 17.  And  as I
really would like to master the language I would not jump straight to that.

My unique looks like this:

unique2 :: [Int] -> [Int]
unique2 [] = []
unique2 (x:xs) 
	|elem x xs = unique2 (deleteElem x xs)
	|otherwise = x:unique2 xs
	
	
	
deleteElem :: Int -> [Int] -> [Int]
deleteElem x [] = []
deleteElem x (y:ys)
	|x == y = deleteElem x ys
	|otherwise = y:deleteElem x ys

And I did think about for every call it will go through an entire list - now
i know where the solution lies.
Thanks again


Dan Weston wrote:
> 
> 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
>>>
>>>
>> 
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 

-- 
View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11543116
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.