[Haskell-beginners] Eq a => [a]->[a]
Brent Yorgey
byorgey at seas.upenn.edu
Wed Dec 2 21:46:43 EST 2009
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
More information about the Beginners
mailing list