[Haskell-cafe] function unique
Brent Yorgey
byorgey at gmail.com
Wed Jul 11 14:41:36 EDT 2007
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070711/bc7dd10d/attachment-0001.htm
More information about the Haskell-Cafe
mailing list