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 <[EMAIL PROTECTED]> 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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
