toList generates a sorted list since it is implemented as toList = toAscList, but it's probably bad form to rely on that.
On 01/08/07, Andy Gimblett <[EMAIL PROTECTED]> wrote: > On Wed, Aug 01, 2007 at 01:42:52PM -0700, Dan Weston wrote: > > > Andy Gimblett wrote: > > > > > >>cartesian :: Ord a => S.Set a -> S.Set (a,a) > > >>cartesian x = S.fromList [(i,j) | i <- xs, j <- xs] > > >> where xs = S.toList x > > > > Your list comprehension always generates a sorted list, so changing > > S.fromList to its "unsafe" version (but guarateed by you) > > S.fromDistinctAscList should get you back to O(n). > > That'll do it: with that change, my program runs eight times faster; > according to the profiler, it's gone from spending ~85% of its time in > cartesian to ~0%. :-) > > I don't see why my list comprehension always generates a sorted list, > however: toList generates a sorted list? It doesn't claim to in the > docs. Do I perhaps need to use toAscList instead? > > I happen to have put my data into the Set in order in this example, so > maybe I just lucked out? Or am I missing something? > > > Of course the order of the generators was key (i before j). > > Lucky me. :-) > > Thanks! > > -Andy > > -- > Andy Gimblett > Computer Science Department > University of Wales Swansea > http://www.cs.swan.ac.uk/~csandy/ > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
