Oh, lol because I&#39;m stupid and put the arguments the wrong way around in the first recursive call to testunique&#39; ;-)<br><br><div><span class="gmail_quote">On 7/11/07, <b class="gmail_sendername">Hugh Perkins</b> &lt;
<a href="mailto:hughperkins@gmail.com">hughperkins@gmail.com</a>&gt; 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 &#39;uniq&#39;), and getting it to be lazy.&nbsp; This seems to work:
<br><br>testunique :: Eq a =&gt; [a] -&gt; [a]<br>testunique list = testunique&#39; list []<br>&nbsp;&nbsp; where testunique&#39; :: Eq a =&gt; [a] -&gt; [a] -&gt; [a]
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; testunique&#39; [] elementssofar = []<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; testunique&#39; (x:xs) elementssofar | x `elem` elementssofar = (testunique&#39; elementssofar xs)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise = x : ( testunique&#39; 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&nbsp; &quot;take 10 ( [1,3,7] ++ [7 ..] )&quot; 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> &lt;<a href="mailto:westondan@imageworks.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">westondan@imageworks.com</a>&gt; 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> &gt; I&#39;v got it - it produces the right output.<br> &gt; Thank you.<br><br>Now that you&#39;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&#39;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&#39;re only going to do it just before mom gets home
<br>(who knows, with any luck she&#39;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&#39;t cheat you out of the fun, but here&#39;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>&nbsp;&nbsp; x : keepOnlyLowestMultiple (filter (isNotDivisor x) xs)
<br><br>primes = keepOnlyLowestMultiple [2..]<br><br>Dan<br><br>&gt; Brent Yorgey wrote:<br>&gt;&gt; The problem with your second implementation is that elements which occur<br>&gt;&gt; more than once will eventually be included, when the part of the list
<br>&gt;&gt; remaining only has one copy. For example:<br>&gt;&gt;<br>&gt;&gt; unique2 [1,1,2,4,1]<br>&gt;&gt; = unique2 [1,2,4,1]<br>&gt;&gt; = unique2 [2,4,1]<br>&gt;&gt; = 2 : unique2 [4,1]<br>&gt;&gt; = 2 : 4 : unique2 [1]
<br>&gt;&gt; = 2 : 4 : 1 : unique2 []&nbsp;&nbsp; -- only a single 1 left, so it gets mistakenly<br>&gt;&gt; included<br>&gt;&gt; = [2,4,1]<br>&gt;&gt;<br>&gt;&gt; When you determine that a certain number should not be included in the
<br>&gt;&gt; output, you need to delete all remaining occurrences of it from the list,<br>&gt;&gt; so<br>&gt;&gt; it won&#39;t get included later.<br>&gt;&gt;<br>&gt;&gt; unique2 (x:xs)<br>&gt;&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |elemNum2 x xs == 1 = x:unique2 xs
<br>&gt;&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |otherwise = unique2 (deleteElt x xs)<br>&gt;&gt;<br>&gt;&gt; I&#39;ll let you figure out how to implement the deleteElt function.<br>&gt;&gt;<br>&gt;&gt; hope this is helpful!<br>&gt;&gt; -Brent<br>
&gt;&gt;
<br>&gt;&gt; On 7/10/07, Alexteslin &lt;<a href="mailto:alexteslin@yahoo.co.uk" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">alexteslin@yahoo.co.uk</a>&gt; wrote:<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; Hi, i am a beginner to Haskell and i have a beginner&#39;s question to ask.
<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; An exercise asks to define function unique :: [Int] -&gt; [Int], which<br>&gt;&gt;&gt; outputs<br>&gt;&gt;&gt; a list with only elements that are unique to the input list (that appears<br>

&gt;&gt;&gt; no<br>&gt;&gt;&gt; more than once).&nbsp;&nbsp;I defined a function with list comprehension which<br>&gt;&gt;&gt; works<br>&gt;&gt;&gt; but trying to implement with pattern matching and primitive recursion<br>&gt;&gt;&gt; with
<br>&gt;&gt;&gt; lists and doesn&#39;t work.<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; unique :: [Int] -&gt; [Int]<br>&gt;&gt;&gt; unique xs = [x | x &lt;- xs, elemNum2 x xs == 1]<br>&gt;&gt;&gt;<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; elemNum2 :: Int -&gt; [Int] -&gt; Int
<br>&gt;&gt;&gt; elemNum2 el xs = length [x| x &lt;- xs, x == el]<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; //This doesn&#39;t work, I know because the list shrinks and produces wrong<br>&gt;&gt;&gt; result but can not get a right //thinking
<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; unique2 :: [Int] -&gt; [Int]<br>&gt;&gt;&gt; unique2 [] = []<br>&gt;&gt;&gt; unique2 (x:xs)<br>&gt;&gt;&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |elemNum2 x xs == 1 = x:unique2 xs<br>&gt;&gt;&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |otherwise = unique2 xs
<br>&gt;&gt;&gt;<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; Any help to a right direction would be very appreciated, thanks.<br>&gt;&gt;&gt; --<br>&gt;&gt;&gt; View this message in context:<br>&gt;&gt;&gt; <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>&gt;&gt;&gt; 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>&gt;&gt;&gt;<br>&gt;&gt;&gt; _______________________________________________
<br>&gt;&gt;&gt; Haskell-Cafe mailing list<br>&gt;&gt;&gt; <a href="mailto:Haskell-Cafe@haskell.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">Haskell-Cafe@haskell.org</a><br>&gt;&gt;&gt; <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>&gt;&gt;&gt;<br>&gt;&gt; _______________________________________________<br>&gt;&gt; Haskell-Cafe mailing list<br>&gt;&gt; <a href="mailto:Haskell-Cafe@haskell.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
Haskell-Cafe@haskell.org</a><br>&gt;&gt; <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>&gt;&gt;<br>&gt;&gt;<br>&gt;<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>