[Haskell-cafe] function unique

Hugh Perkins hughperkins at gmail.com
Wed Jul 11 16:31:36 EDT 2007


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/3c0ecec0/attachment.htm


More information about the Haskell-Cafe mailing list