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