[Haskell-beginners] Eq a => [a]->[a]

[Brent Yorgey]

On Wed, Dec 02, 2009 at 06:47:54PM -0600, I. J. Kennedy wrote:
> I am looking for a function
>  f::Eq a => [a]->[a]
> that takes a list and returns the longest
> initial segment of the list for which all
> the elements are distinct.
> 
> For example f [2,3,6,4,3,5] = [2,3,6,4].
> 
> I didn't see anything that matched using Hoogle,
> but I thought this might be a common enough
> operation that this function might exists somewhere
> in the standard packages.

Not that I know of.  Here's how I would implement it (although you may
enjoy trying to implement it yourself):

  import qualified Data.Set as S

  f xs = map fst $ takeWhile (uncurry S.notMember) (zip xs cums)
    where cums = scanl (flip S.insert) S.empty xs

It works by incrementally building up a list of sets of the elements
found in prefixes of the list (with scanl), then goes down the list
(takeWhile) checking that each element isn't already in the
corresponding set of elements.

-Brent