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
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@haskell.org http://www.haskell.org/mailman/listinfo/beginners