Oh, lol because I'm stupid and put the arguments the wrong way around in the first recursive call to testunique' ;-)<br><br><div><span class="gmail_quote">On 7/11/07, <b class="gmail_sendername">Hugh Perkins</b> <
<a href="mailto:hughperkins@gmail.com">hughperkins@gmail.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work:
<br><br>testunique :: Eq a => [a] -> [a]<br>testunique list = testunique' list []<br> where testunique' :: Eq a => [a] -> [a] -> [a]
<br> testunique' [] elementssofar = []<br> testunique' (x:xs) elementssofar | x `elem` elementssofar = (testunique' elementssofar xs)<br> | otherwise = x : ( testunique' xs (x:elementssofar))
<br><br><br>Now, a question, why is this happening:<br><br>doesnt block:<br>
<br>
take 10 (testunique ([1,3] ++ [7..]))<br>
take 10 (testunique ([7..] ++ [1,3,7]))<br>
<br>blocks forever:<br><br>take 10 (testunique ([1,3,7] ++ [7..]))<br>
<br>The expression ([1,3,7] ++ [7..]) itself doesnt block: things like "take 10 ( [1,3,7] ++ [7 ..] )" work just fine, so what is going on?<div><span class="e" id="q_113b6faccc5da21d_1"><br><br><div><span class="gmail_quote">
On 7/11/07, <b class="gmail_sendername">
Dan Weston</b> <<a href="mailto:westondan@imageworks.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">westondan@imageworks.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Alexteslin wrote:<br> > I'v got it - it produces the right output.<br> > Thank you.<br><br>Now that you've done the exercise, the fun starts! What assumptions did<br>you build in to your solution?<br><br>1) You just need uniqueness, so counting the number of copies is not
<br>only overkill, but requires you to go through the entire list to count them.<br><br>2) The list might be infinite, and your function should work if you make<br>only want to use the first part of it, so the following should return
<br>[1,2,3,4,5] in a finite amount of time:<br><br>take 5 (unique [1..])<br><br>Your algorithm fails both of these. Consider a *lazy* approach:<br><br>1) Keep the head of the list<br>2) Then filter the tail, keeping only elements different from the head
<br>3) Then put the two together<br><br>Don't worry in step #2 about having an infinite number of list elements<br>to be filtered out of the list. Think of it like asking a lazy child to<br>clean the house. They're only going to do it just before mom gets home
<br>(who knows, with any luck she'll be in a car crash and forget about<br>having asked you to clean!)<br><br>This works for infinite lists, and puts off the work until you actually<br>need the elements.<br><br>I won't cheat you out of the fun, but here's the solution to a *very*
<br>similar problem using the Sieve of Eratosthenes to find prime numbers:<br><br>isNotDivisor divisor dividend = dividend `rem` divisor /= 0<br><br>keepOnlyLowestMultiple (x:xs) =<br> x : keepOnlyLowestMultiple (filter (isNotDivisor x) xs)
<br><br>primes = keepOnlyLowestMultiple [2..]<br><br>Dan<br><br>> Brent Yorgey wrote:<br>>> The problem with your second implementation is that elements which occur<br>>> more than once will eventually be included, when the part of the list
<br>>> remaining only has one copy. For example:<br>>><br>>> unique2 [1,1,2,4,1]<br>>> = unique2 [1,2,4,1]<br>>> = unique2 [2,4,1]<br>>> = 2 : unique2 [4,1]<br>>> = 2 : 4 : unique2 [1]
<br>>> = 2 : 4 : 1 : unique2 [] -- only a single 1 left, so it gets mistakenly<br>>> included<br>>> = [2,4,1]<br>>><br>>> When you determine that a certain number should not be included in the
<br>>> output, you need to delete all remaining occurrences of it from the list,<br>>> so<br>>> it won't get included later.<br>>><br>>> unique2 (x:xs)<br>>> |elemNum2 x xs == 1 = x:unique2 xs
<br>>> |otherwise = unique2 (deleteElt x xs)<br>>><br>>> I'll let you figure out how to implement the deleteElt function.<br>>><br>>> hope this is helpful!<br>>> -Brent<br>
>>
<br>>> On 7/10/07, Alexteslin <<a href="mailto:alexteslin@yahoo.co.uk" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">alexteslin@yahoo.co.uk</a>> wrote:<br>>>><br>>>> Hi, i am a beginner to Haskell and i have a beginner's question to ask.
<br>>>><br>>>> An exercise asks to define function unique :: [Int] -> [Int], which<br>>>> outputs<br>>>> a list with only elements that are unique to the input list (that appears<br>
>>> no<br>>>> more than once). I defined a function with list comprehension which<br>>>> works<br>>>> but trying to implement with pattern matching and primitive recursion<br>>>> with
<br>>>> lists and doesn't work.<br>>>><br>>>> unique :: [Int] -> [Int]<br>>>> unique xs = [x | x <- xs, elemNum2 x xs == 1]<br>>>><br>>>><br>>>> elemNum2 :: Int -> [Int] -> Int
<br>>>> elemNum2 el xs = length [x| x <- xs, x == el]<br>>>><br>>>> //This doesn't work, I know because the list shrinks and produces wrong<br>>>> result but can not get a right //thinking
<br>>>><br>>>> unique2 :: [Int] -> [Int]<br>>>> unique2 [] = []<br>>>> unique2 (x:xs)<br>>>> |elemNum2 x xs == 1 = x:unique2 xs<br>>>> |otherwise = unique2 xs
<br>>>><br>>>><br>>>> Any help to a right direction would be very appreciated, thanks.<br>>>> --<br>>>> View this message in context:<br>>>> <a href="http://www.nabble.com/function-unique-tf4058328.html#a11528933" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
http://www.nabble.com/function-unique-tf4058328.html#a11528933</a><br>>>> Sent from the Haskell - Haskell-Cafe mailing list archive at <a href="http://Nabble.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
Nabble.com</a>.<br>>>><br>>>> _______________________________________________
<br>>>> Haskell-Cafe mailing list<br>>>> <a href="mailto:Haskell-Cafe@haskell.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">Haskell-Cafe@haskell.org</a><br>>>> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
http://www.haskell.org/mailman/listinfo/haskell-cafe
</a><br>>>><br>>> _______________________________________________<br>>> Haskell-Cafe mailing list<br>>> <a href="mailto:Haskell-Cafe@haskell.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
Haskell-Cafe@haskell.org</a><br>>> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>>><br>>><br>><br><br><br>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.haskell.org/mailman/listinfo/haskell-cafe</a>
<br></blockquote></div><br>
</span></div></blockquote></div><br>