[Haskell-cafe] function unique
alexteslin at yahoo.co.uk
Wed Jul 11 11:55:28 EDT 2007
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  = 
|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.
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
> 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..]
>> 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 
>>> = 2 : 4 : 1 : unique2  -- only a single 1 left, so it gets
>>> = [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
>>> 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!
>>> 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
>>>> a list with only elements that are unique to the input list (that
>>>> more than once). I defined a function with list comprehension which
>>>> but trying to implement with pattern matching and primitive recursion
>>>> 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:
>>>> Sent from the Haskell - Haskell-Cafe mailing list archive at
>>>> Haskell-Cafe mailing list
>>>> Haskell-Cafe at haskell.org
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
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.
More information about the Haskell-Cafe