Re: [Haskell-cafe] function unique

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 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@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.