[Haskell-cafe] function unique

[Hugh Perkins]

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 <hughperkins at gmail.com> 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 <westondan at imageworks.com> 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
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070711/ecc85fe5/attachment-0001.htm