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

[Patrick LeBoutillier]

On Thu, Dec 3, 2009 at 11:38 AM, I. J. Kennedy <jack at realmode.com> wrote:
> 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

When I first saw this function I thought it looked complicated, and in
a naive attempt
to simplify it I came up with this:

import Data.List

f :: (Eq a) => [a] -> [a]
f = last . takeWhile (\l -> nub l == l) . inits

This worked well for short lists, but started to drag for large lists,
especially if the result was long, i.e. for input like ([1 .. 1000] ++
[1]).

Brent's version seems very fast no matter the list length. Maybe
someone can provide a O() analysis?

Patrick

>
> 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
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>



-- 
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada