[Haskell-cafe] function unique

[Hugh Perkins]

By the way, this is something that is hard in Haskell compared to say C#.

In C#, when you call a function you type "(" and instantly you get a popup
box telling you what the name of the first argument is, then when you've
written the first argument and hit "," you get the name (and type) of the
second argument.

It's pretty hard not to put the right arguments in the right order.

Not so in Haskell where I spend insane amounts of time trying to remember
what argument is what in a function I wrote 30 seconds ago.

On 7/11/07, Hugh Perkins <hughperkins at gmail.com> wrote:
>
> 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/68ecaeb0/attachment.htm