Re: [Haskell-cafe] function unique
Tim Chevalier wrote: On 7/12/07, Jonathan Cast <[EMAIL PROTECTED]> wrote: No. Of course not. Before making wild guesses about how GHC is implementing your code, read (and understand[1]) the STG paper: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/spineless-tagless-gmachine.ps.gz&pub=34 In this particular case, reading the simplifier paper would probably be more relevant: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/comp-by-trans.ps.gz&pub=18 Or even just understanding the syntax of Core, really. [1] Understanding the STG paper is not a requirement to using Haskell, just to making wild (incorrect) guesses about how the compiler's going to treat your code. But, of course, making wild (incorrect) guesses about how the compiler's going to treat your code is not a requirement to using Haskell. Amen! Cheers, Tim I realize now that it was inappropriate to pose a question to this list before I knew the answer! :( Anyway, it turned out that the two ghc -ddump-simpl outputs were in fact identical, but only after identifier renaming. It would be very useful to have a tool that takes two core files and attempts to rename identifiers from the second to match the first. Is there already such a smart-diff tool out there? Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On 7/12/07, Jonathan Cast <[EMAIL PROTECTED]> wrote: No. Of course not. Before making wild guesses about how GHC is implementing your code, read (and understand[1]) the STG paper: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/spineless-tagless-gmachine.ps.gz&pub=34 In this particular case, reading the simplifier paper would probably be more relevant: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/comp-by-trans.ps.gz&pub=18 Or even just understanding the syntax of Core, really. [1] Understanding the STG paper is not a requirement to using Haskell, just to making wild (incorrect) guesses about how the compiler's going to treat your code. But, of course, making wild (incorrect) guesses about how the compiler's going to treat your code is not a requirement to using Haskell. Amen! Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt "Everyone's too stupid." -- _Ghost World_ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Thursday 12 July 2007, Dan Weston wrote: > While we're at it, the second pattern match is superfluous. Once you > take out nonempty lists from the list type, the only thing left is an > empty one! > > unique :: Eq a => [a] -> [a] > unique (x:xs) = x : (unique . filter (/= x) $ xs) > unique _ = [] > > One question left: would the second definition be more efficient if > written: > > unique e = e > > Inquiring minds want to know... No. Of course not. Before making wild guesses about how GHC is implementing your code, read (and understand[1]) the STG paper: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/spineless-tagless-gmachine.ps.gz&pub=34 And then as many as you can of the other papers available here. http://research.microsoft.com/~simonpj/Papers/papers.html To answer your question: [] is treated like a variable, except it's a variable whose behavior is statically known, so the compiler can do more with it. In fact, all of your versions given are equivalent in GHC, but only because you're taking advantage of more and more of the heroic work GHC does to convert your later versions into your earlier ones. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs [1] Understanding the STG paper is not a requirement to using Haskell, just to making wild (incorrect) guesses about how the compiler's going to treat your code. But, of course, making wild (incorrect) guesses about how the compiler's going to treat your code is not a requirement to using Haskell. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On 7/12/07, Dan Weston <[EMAIL PROTECTED]> wrote: Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions: unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = [] This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first! Of course GHC detects that the cases are mutually exclusive. The code above desugars into a single definition of unique with a case expression on its argument. In Core, case expressions have at most one alternative for each data constructor of the type of the scrutinee, and since each alternative corresponds to a different top-level data constructor, alternatives are mutually exclusive. As for point (b), it hardly matters, since GHC will rearrange case alternatives at will (and I don't think the order of alternatives has any operational meaning anyway.) If you want to see this for yourself, try running GHC with the -ddump-simpl flag on a simple example (like the one above). Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt "What doesn't kill you, makes you stronger -- or puts you on a talk show." --Carrie Fisher ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Thursday 12 July 2007, Dan Weston wrote: > Now that I mention it, the base case is much less often called than the > recursive case, so I would in hindsight flip the order of the two > (mutually exclusive) partial function definitions: > > unique :: Eq a => [a] -> [a] > unique (x:xs) = x : (unique . filter (/= x) $ xs) > unique [] = [] > > This should be marginally more efficient. I doubt that GHC would > automatically detect that a) they are mutually exclusive and b) the > second is called less often than the first! Actually, it would (well, sort of). GHC expends a good deal of effort looking for cases where pattern-matching is mutually-exclusive, and flattens it out to unique xn' = case xn' of [] -> [] x : xn -> x : unique (filter (/= x) xn) where each branch is equally efficient. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
While we're at it, the second pattern match is superfluous. Once you take out nonempty lists from the list type, the only thing left is an empty one! unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique _ = [] One question left: would the second definition be more efficient if written: unique e = e Inquiring minds want to know... Dan Dan Weston wrote: Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions: unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = [] This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first! Dan Dan Weston wrote: > Close. Actually, the author upstream (i.e. me) had in mind: > uniq :: Eq a => [a] -> [a] > uniq [] = [] > uniq (x:xs) = x : uniq (filter (/= x) xs) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions: unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = [] This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first! Dan Dan Weston wrote: > Close. Actually, the author upstream (i.e. me) had in mind: > uniq :: Eq a => [a] -> [a] > uniq [] = [] > uniq (x:xs) = x : uniq (filter (/= x) xs) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Philip Armstrong wrote: On Wed, Jul 11, 2007 at 10:31:36PM +0200, Hugh Perkins wrote: Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work: It's slightly worse than that: unix uniq only eliminates *consecutive* identical lines from its input. If you want to eliminate all duplicates, you have to pipe your input through sort first. 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)) I suspect the author upthread had something more like this in mind: uniq :: Eq a => [a] -> [a] uniq [] = [] uniq (x:xs) = x : filter (x/=) (uniq2 xs) Obviously a true 'unique' function has to traverse the entire list before it creates any output, as has been pointed out upthread. Phil Close. Actually, the author upstream (i.e. me) had in mind: > uniq :: Eq a => [a] -> [a] > uniq [] = [] > uniq (x:xs) = x : uniq (filter (/= x) xs) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Wed, Jul 11, 2007 at 10:31:36PM +0200, Hugh Perkins wrote: Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work: It's slightly worse than that: unix uniq only eliminates *consecutive* identical lines from its input. If you want to eliminate all duplicates, you have to pipe your input through sort first. 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)) I suspect the author upthread had something more like this in mind: uniq :: Eq a => [a] -> [a] uniq [] = [] uniq (x:xs) = x : filter (x/=) (uniq2 xs) Obviously a true 'unique' function has to traverse the entire list before it creates any output, as has been pointed out upthread. Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Wed, Jul 11, 2007 at 04:33:19PM -0500, Jonathan Cast wrote: > On Wednesday 11 July 2007, you wrote: > > On Wed, Jul 11, 2007 at 03:59:45PM -0500, Jonathan Cast wrote: > > > One could put up the Haddock doc-comment. Or, say, one could extend > > > Haddock to support parameter names: > > > > > > testunique' :: Eq a > > > => [a] -- ^ $list List of elements to test > > > -> [a] -- ^ $elementssofar List of elements seen thus far > > > -> [a] -- ^ List of unique elements in 'list'. > > > > > > No patch forthcoming from this corner, though. > > > > None necessary! Haddock already supports that syntax. > > > > http://haskell.org/haddock/haddock-html-0.8/ch03s02.html#id289091 > > I think you missed my overloading of the section-label syntax to get argument > names. Indeed. > And it's not even quite supported; trying the example gets you > > $ haddock -h Foo.hs > Warning: Foo: the following names could not be resolved: > Eq list Uhm... that's a *successful* run. I think you meant to copy the messages from a failed run? Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Wednesday 11 July 2007, you wrote: > On Wed, Jul 11, 2007 at 03:59:45PM -0500, Jonathan Cast wrote: > > One could put up the Haddock doc-comment. Or, say, one could extend > > Haddock to support parameter names: > > > > testunique' :: Eq a > > => [a] -- ^ $list List of elements to test > > -> [a] -- ^ $elementssofar List of elements seen thus far > > -> [a] -- ^ List of unique elements in 'list'. > > > > No patch forthcoming from this corner, though. > > None necessary! Haddock already supports that syntax. > > http://haskell.org/haddock/haddock-html-0.8/ch03s02.html#id289091 I think you missed my overloading of the section-label syntax to get argument names. And it's not even quite supported; trying the example gets you $ haddock -h Foo.hs Warning: Foo: the following names could not be resolved: Eq list Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Wed, 11 Jul 2007 22:49:27 +0200, you wrote: >Well, there's a fundamental reason it wont work for Haskell: we dont >actually define the names of the parameters to the function! Yes, but you know the type, which is what really counts. And, taking that a step further, once you've entered something for the first argument, a real-time compiler might be able to narrow down the set of allowed types for the second argument, and so on. Of course, if you're in the habit of creating functions with type signatures like Int -> Int -> Int -> Int -> Int -> Int, and you can't remember which Int does what, then you have only yourself to blame Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Wed, Jul 11, 2007 at 03:59:45PM -0500, Jonathan Cast wrote: > One could put up the Haddock doc-comment. Or, say, one could extend Haddock > to support parameter names: > > testunique' :: Eq a > => [a] -- ^ $list List of elements to test > -> [a] -- ^ $elementssofar List of elements seen thus far > -> [a] -- ^ List of unique elements in 'list'. > > No patch forthcoming from this corner, though. None necessary! Haddock already supports that syntax. http://haskell.org/haddock/haddock-html-0.8/ch03s02.html#id289091 Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On Wednesday 11 July 2007, Hugh Perkins wrote: > Well, there's a fundamental reason it wont work for Haskell: we dont > actually define the names of the parameters to the function! > > Have a look at the function above, the function is defined as: > > testunique' :: Eq a => [a] -> [a] -> [a] > testunique' [] elementssofar = [] > testunique' (x:xs) elementssofar > > There's an agreement here that the second parameter is called > "elementssofar"... but only because I was consistent in my naming in this > example. What if we had multiple constructors for a particular type? > > The first argument has no obvious naming at all. > > We could do things like write it in comments: > > testunique' :: Eq a => [a] -> [a] -> [a] > -- testunique' :: remainingelements -> elementssofar -> uniqueelements > testunique' [] elementssofar = [] > testunique' (x:xs) elementssofar > > ... but we all know that no-one bothers writing comments, and certainly > never maintaining them, and in any case this is becoming insanely difficult > to read. > > I dont have a solution, apart from using C# for production programming ;-) > , but things like this are really important to solve in any "mainstream" > version of Haskell. One could put up the Haddock doc-comment. Or, say, one could extend Haddock to support parameter names: testunique' :: Eq a => [a] -- ^ $list List of elements to test -> [a] -- ^ $elementssofar List of elements seen thus far -> [a] -- ^ List of unique elements in 'list'. No patch forthcoming from this corner, though. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Well, there's a fundamental reason it wont work for Haskell: we dont
actually define the names of the parameters to the function!
Have a look at the function above, the function is defined as:
testunique' :: Eq a => [a] -> [a] -> [a]
testunique' [] elementssofar = []
testunique' (x:xs) elementssofar
There's an agreement here that the second parameter is called
"elementssofar"... but only because I was consistent in my naming in this
example. What if we had multiple constructors for a particular type?
The first argument has no obvious naming at all.
We could do things like write it in comments:
testunique' :: Eq a => [a] -> [a] -> [a]
-- testunique' :: remainingelements -> elementssofar -> uniqueelements
testunique' [] elementssofar = []
testunique' (x:xs) elementssofar
... but we all know that no-one bothers writing comments, and certainly
never maintaining them, and in any case this is becoming insanely difficult
to read.
I dont have a solution, apart from using C# for production programming ;-) ,
but things like this are really important to solve in any "mainstream"
version of Haskell.
On 7/11/07, Steve Schafer <[EMAIL PROTECTED]> wrote:
On Wed, 11 Jul 2007 22:39:27 +0200, you wrote:
>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.
That's not a feature of C# itself, but rather a feature of the
development environment you're using. You can write C# code in NotePad,
and I will guarantee you that you won't see any such popups. ;)
There do exist various development environments for Haskell, but I don't
think any of them are particularly popular.
Steve Schafer
Fenestra Technologies Corp.
http://www.fenestra.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
Re: [Haskell-cafe] function unique
On Wed, 11 Jul 2007 22:39:27 +0200, you wrote:
>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.
That's not a feature of C# itself, but rather a feature of the
development environment you're using. You can write C# code in NotePad,
and I will guarantee you that you won't see any such popups. ;)
There do exist various development environments for Haskell, but I don't
think any of them are particularly popular.
Steve Schafer
Fenestra Technologies Corp.
http://www.fenestra.com/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Hugh Perkins wrote:
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.
Good point!
Hmm... sounds kind of hard to do in Haskell. I mean, the function might
be curried. ;-) Still, you'd think it's doable.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
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 <[EMAIL PROTECTED]> 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 < [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 :: I
Re: [Haskell-cafe] function unique
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 > >>> > >>
Re: [Haskell-cafe] function unique
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 h
Re: [Haskell-cafe] function unique
Simple answer: you always have to have the single element first, then the list bit second. It's just the way it is. You can learn why later on ;-) On 7/11/07, Alexteslin <[EMAIL PROTECTED]> wrote: Oh, I am lost now - for now anyway. I am attempting to do next exercise in the book to define reverse function using primitive recursion and pattern matching on lists. But getting stack because when i con in front of xs (xs:x) i get en error, which i thought i would be getting anyway. I tried to define a helper function and cons there in front of xs and i get type errors again. I know these are easy and boring questions but i would appreciate a hint. Thank you Neil Mitchell wrote: > > Hi > >> unique = unique' [] >> >> unique' _ [] = [] >> unique' history (x:xs) = if x `elem` history >> then next >> else (x:next) where next = (uniq' (x:hist) xs) > > You can express this more neatly: > > unique' _ [] = [] > unique' history (x:xs) = [x | x `notElem` history] ++ unique' (x:history) > xs > > Thanks > > Neil > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11547781 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
Re: [Haskell-cafe] function unique
On 7/11/07, Alexteslin <[EMAIL PROTECTED]> wrote: Oh, I am lost now - for now anyway. I am attempting to do next exercise in the book to define reverse function using primitive recursion and pattern matching on lists. But getting stack because when i con in front of xs (xs:x) i get en error, which i thought i would be getting anyway. I tried to define a helper function and cons there in front of xs and i get type errors again. I know these are easy and boring questions but i would appreciate a hint. Thank you Let's look at the type of the cons operator: Prelude> :t (:) (:) :: a -> [a] -> [a] That is, it takes an element of any type (here represented by 'a'), and a list of the same type, and produces a list. So (xs:x) does not make sense, assuming that xs is a list and x has the same type as an element of xs; cons expects an element followed by a list, and you are giving it a list followed by an element. If you want to append an element onto the end of a list you can do xs ++ [x] ++ is the list append operator, so this says "make x into a list with one element, and append it onto the end of the list xs". Does that help? It's hard to help without seeing any code or the specific errors you are seeing, but hopefully that should give you a push in the right direction. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
> I don't think this is possible. Perhaps you misread the original problem > description? The unique function is supposed to return a list of those > elements which occur exactly once in the input list, which is impossible to > determine for an infinite input list (the only way to prove that a given > element occurs only once in a list, in the absence of any other information, > is to examine every element of the list). Of course, a function that > behaves like the unix utility "uniq" ( i.e. returning only one copy of every > list element) is possible to implement lazily in the manner you describe. Why wouldn't this work? (I haven't tested it, sorry) unique = unique' [] unique' _ [] = [] unique' history (x:xs) = if x `elem` history then next else (x:next) where next = (uniq' (x:hist) xs) Again, this is solving a different problem than what the OP stated. Using your definition: Prelude> :l unique [1 of 1] Compiling Main ( unique.hs, interpreted ) Ok, modules loaded: Main. *Main> unique [1,2,3,1] [1,2,3] *Main> ...which behaves like the Unix utility 'uniq'. But the problem described originally is to write a function which produces [2,3] when given the same input; 1 is not included in the output since it occurs more than once. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Oh, I am lost now - for now anyway. I am attempting to do next exercise in the book to define reverse function using primitive recursion and pattern matching on lists. But getting stack because when i con in front of xs (xs:x) i get en error, which i thought i would be getting anyway. I tried to define a helper function and cons there in front of xs and i get type errors again. I know these are easy and boring questions but i would appreciate a hint. Thank you Neil Mitchell wrote: > > Hi > >> unique = unique' [] >> >> unique' _ [] = [] >> unique' history (x:xs) = if x `elem` history >> then next >> else (x:next) where next = (uniq' (x:hist) xs) > > You can express this more neatly: > > unique' _ [] = [] > unique' history (x:xs) = [x | x `notElem` history] ++ unique' (x:history) > xs > > Thanks > > Neil > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11547781 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
Re: [Haskell-cafe] function unique
Hi unique = unique' [] unique' _ [] = [] unique' history (x:xs) = if x `elem` history then next else (x:next) where next = (uniq' (x:hist) xs) You can express this more neatly: unique' _ [] = [] unique' history (x:xs) = [x | x `notElem` history] ++ unique' (x:history) xs Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
On 7/11/07, Brent Yorgey <[EMAIL PROTECTED]> wrote: > take 5 (unique [1..]) I don't think this is possible. Perhaps you misread the original problem description? The unique function is supposed to return a list of those elements which occur exactly once in the input list, which is impossible to determine for an infinite input list (the only way to prove that a given element occurs only once in a list, in the absence of any other information, is to examine every element of the list). Of course, a function that behaves like the unix utility "uniq" ( i.e. returning only one copy of every list element) is possible to implement lazily in the manner you describe. Why wouldn't this work? (I haven't tested it, sorry) unique = unique' [] unique' _ [] = [] unique' history (x:xs) = if x `elem` history then next else (x:next) where next = (uniq' (x:hist) xs) Whether or not it's a good idea is a separate issue. Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
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..]) I don't think this is possible. Perhaps you misread the original problem description? The unique function is supposed to return a list of those elements which occur exactly once in the input list, which is impossible to determine for an infinite input list (the only way to prove that a given element occurs only once in a list, in the absence of any other information, is to examine every element of the list). Of course, a function that behaves like the unix utility "uniq" (i.e. returning only one copy of every list element) is possible to implement lazily in the manner you describe. @Alexteslin: It probably would still be a useful exercise for you, though, to get rid of the redundancy Dan describes in determining whether to keep each element. A function to count the occurrences of a given element (although useful in its own right) is overkill here, since you only care whether the element occurs once, or more than once. You could implement a function isUnique :: Int -> [Int] -> Bool which tells you whether the given element occurs only once (True) or more than once (False), and doesn't evaluate more of the list than necessary to determine this. I doubt you'd have much trouble implementing this function. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Yeah, I didn't see that part of the email, sorry. - Original Message From: Alexteslin <[EMAIL PROTECTED]> To: haskell-cafe@haskell.org Sent: Wednesday, July 11, 2007 8:59:33 AM Subject: Re: [Haskell-cafe] function unique Thans Gregory, But I sticked to the original solution because the exercise was about primitive recursion and pattern matching over lists. Never miss an email again! Yahoo! Toolbar alerts you the instant new Mail arrives. http://tools.search.yahoo.com/toolbar/features/mail/___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Thans Gregory, But I sticked to the original solution because the exercise was about primitive recursion and pattern matching over lists. Gregory Propf wrote: > > Well there's this approach. Granted you need to split the input list into > *both* args of the fold (i.e. the "input list" is really [1,4,5,3] but you > can get this with head and tail). I'm just learning about the fold family > myself. - Greg > > Prelude> foldl (\a b -> if (any (\x -> x == b) a) then a else b:a) [1] > [4,5,3,3,4] > [3,5,4,1] > > > > - Original Message > From: Alexteslin <[EMAIL PROTECTED]> > To: haskell-cafe@haskell.org > Sent: Tuesday, July 10, 2007 1:40:56 PM > Subject: [Haskell-cafe] function unique > > > 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 > > > > > > > > > > Shape Yahoo! in your own image. Join our Network Research Panel today! > http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7 > > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11543175 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
Re: [Haskell-cafe] function unique
Thank you for your great suggestions, i will try to use lazy evaluation of course. But as a beginner I am on Chapter 7 of the textbook and will soon (perhaps in few weeks) move on to that, which is Chapter 17. And as I really would like to master the language I would not jump straight to that. My unique looks like this: unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elem x xs = unique2 (deleteElem x xs) |otherwise = x:unique2 xs deleteElem :: Int -> [Int] -> [Int] deleteElem x [] = [] deleteElem x (y:ys) |x == y = deleteElem x ys |otherwise = y:deleteElem x ys And I did think about for every call it will go through an entire list - now i know where the solution lies. Thanks again Dan Weston 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 > ht
Re: [Haskell-cafe] function unique
There was a typo in my last email. The input list is [1,4,5,3,3,4] not [1,4,5,3]. - Greg - Original Message From: Alexteslin <[EMAIL PROTECTED]> To: haskell-cafe@haskell.org Sent: Tuesday, July 10, 2007 1:40:56 PM Subject: [Haskell-cafe] function unique 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 It's here! Your new message! Get new email alerts with the free Yahoo! Toolbar. http://tools.search.yahoo.com/toolbar/features/mail/___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
Well there's this approach. Granted you need to split the input list into *both* args of the fold (i.e. the "input list" is really [1,4,5,3] but you can get this with head and tail). I'm just learning about the fold family myself. - Greg Prelude> foldl (\a b -> if (any (\x -> x == b) a) then a else b:a) [1] [4,5,3,3,4] [3,5,4,1] - Original Message From: Alexteslin <[EMAIL PROTECTED]> To: haskell-cafe@haskell.org Sent: Tuesday, July 10, 2007 1:40:56 PM Subject: [Haskell-cafe] function unique 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 Shape Yahoo! in your own image. Join our Network Research Panel today! http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] function unique
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
Re: [Haskell-cafe] function unique
I'v got it - it produces the right output. Thank you. 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 > > -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11529400 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
Re: [Haskell-cafe] function unique
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] function unique
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
