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

[I. J. Kennedy]

Thanks for the response and thanks for the implementation.

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

I absolutely love (what I know so far) Haskell, but I must say
when I see this kind of function, or write it myself, I am strongly
reminded of programming in Forth thirty years ago.


On Wed, Dec 2, 2009 at 8:46 PM, Brent Yorgey <byorgey at seas.upenn.edu> wrote:
>
> 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
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners