[Haskell-cafe] function unique
Alexteslin
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 [] = []
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.
More information about the Haskell-Cafe
mailing list