Oh, lol because I'm stupid and put the arguments the wrong way around in the
first recursive call to testunique' ;-)
On 7/11/07, Hugh Perkins <[EMAIL PROTECTED]> wrote:
Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to
be lazy. This seems to work:
testunique :: Eq a => [a] -> [a]
testunique list = testunique' list []
where testunique' :: Eq a => [a] -> [a] -> [a]
testunique' [] elementssofar = []
testunique' (x:xs) elementssofar | x `elem` elementssofar =
(testunique' elementssofar xs)
| otherwise = x : ( testunique'
xs (x:elementssofar))
Now, a question, why is this happening:
doesnt block:
take 10 (testunique ([1,3] ++ [7..]))
take 10 (testunique ([7..] ++ [1,3,7]))
blocks forever:
take 10 (testunique ([1,3,7] ++ [7..]))
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?
On 7/11/07, Dan Weston <[EMAIL PROTECTED]> 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 <[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
> >>> Haskell-Cafe@haskell.org
> >>> http://www.haskell.org/mailman/listinfo/haskell-cafe
> >>>
> >> _______________________________________________
> >> Haskell-Cafe mailing list
> >> Haskell-Cafe@haskell.org
> >> http://www.haskell.org/mailman/listinfo/haskell-cafe
> >>
> >>
> >
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
