[Haskell-cafe] function unique

Antoine Latter aslatter at gmail.com
Wed Jul 11 15:31:07 EDT 2007


On 7/11/07, Brent Yorgey <byorgey at gmail.com> 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


More information about the Haskell-Cafe mailing list