[Haskell-beginners] Eq a => [a]->[a]
I. J. Kennedy
jack at realmode.com
Thu Dec 3 11:38:50 EST 2009
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.
> Beginners mailing list
> Beginners at haskell.org
More information about the Beginners