[Haskell] Re: DData AscList
--- John Meacham <[EMAIL PROTECTED]> wrote:
> So, pursuient to discussion on the various other
> haskell lists and some talk about DData recently,
> I was wondering whether adding an ordered
> list type might be useful. Often, when one knows a
> list is ordered, many algorithms (like building a
> tree-based set, or a map) become more
> efficient, however it is up to the programmer to
> ensure an ordered list is used where one is
> expected or obscure bugs might occur.
>
> I was thinking... (off the top of my head)
>
> module
>
Data.OrdList(OrdList,toList,fromList,unsafeFromAscList)
> where
>
> newtype Ord a => OrdList a = OrdList { toList :: [a]
> }
>
> fromList = OrdList . sort
> unsafeFromAscList xs = OrdList xs
>
> with some appropriate instances which make an
> OrdList behave pretty much
> exactly like a list, except maintaining the ordered
> invarient...
>
>
> then we can safely convert between the various
> container types in O(n)
> time without the posibility of messing up...
>
> comments?
Fine, but OrdList should be a subtype of List... and
so it has to be done in an "adhoc" fashion. Encoding
every other property in a class hierarchy might lead
to a big mess. (The ordered property is applicable to
any sequence; crossing all independant properties
leads to an explosion of the number of types.)
To go a bit further, I find it unfortunate to define
an extra type for essentially the same structure with
more information on it. I'm interested on what Oleg
has to say about this, in relation of his recent
findings. Also, I wonder how the problem is approached
in a dependent-types language. (understand epigram)
For this purpose I move to the mother list.
> where is the current proposed DData library anyway?
Simon Marlow expressed the wish to include part of it
(excluding sequences) in the standard distribution.
In the meantime, find it on my homepage:
users.skynet.be/jyp/DData/ddata.tar.gz
Cheers,
JP.
__
Do you Yahoo!?
New and Improved Yahoo! Mail - 100MB free storage!
http://promotions.yahoo.com/new_mail
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] comment on language shootout
--- Gour <[EMAIL PROTECTED]> wrote: > Any comment from some experienced Haskell programmer > about the latest > language shootout published on: > > http://shootout.alioth.debian.org/index.php > regarding Haskell (ghc-6.2.1) score? I would have liked to re-implement some of the benchmarks, some of them should not be looked at by non-haskell programmers, that would give them an awfulidea of what the language looks like/how it should be used. I haven't found where to submit though. BTW, regex matching might be regarded as a bit biased toward ghc :) Cheers, JP. > > > __ > Do you Yahoo!? > Take Yahoo! Mail with you! Get it on your mobile > phone. > http://mobile.yahoo.com/maildemo > __ Do you Yahoo!? Yahoo! Mail is new and improved - Check it out! http://promotions.yahoo.com/new_mail ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Correct interpretation of the curry-howard isomorphism
Hi, --- Bruno Oliveira <[EMAIL PROTECTED]> wrote: > coerce :: a -> b > coerce x = undefined > > As an obvious consequence, Haskell type system would > be unsound. Actually, in the isomrphism, "undefined" is a proof that any theorem is correct. Somehow it can represent an assumption that a subtheorem is true (in place of a real proof -- another function). Of course, this makes "corece = undefined" rather uninteresting as a proof. > So, I assumed that this would be a wrong > interpretation. Would the following be more correct? > > -- > if we can write a function: > > coerce :: a -> b > > without calling any other function or primitive > (that is, just with making use of the type system), > then this would > mean that the type system is unsound. I'd say, check what any primitive 'proves' before using it. Besides that, calling other functions is ok. Cheers, JP. __ Do you Yahoo!? Yahoo! Photos: High-quality 4x6 digital prints for 25¢ http://photos.yahoo.com/ph/print_splash ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Re: RFC: DData in hierarchical libraries
--- Christian Maeder <[EMAIL PROTECTED]> wrote: > Simon Marlow wrote: > > Why are there IntBags but no Bags? > > As I've said before, rename MultiSet to Bag. Daan's remark about the difference between bags and multisets is: " A multi set differs from a /bag/ in the sense that it is represented as a map from elements to occurrence counts instead of retaining all elements. This means that equality on elements should be defined as a /structural/ equality instead of an equivalence relation. If this is not the case, operations that observe the elements, like 'filter' and 'fold', should be used with care. " Yet it can be argued that Eq is (nearly) always assumed to be defined by structural equality, so "Bag" would be just as good as "MultiSet". Since a true "Bag" type may be added later, I did not bother to change the name. > > Internal functions like DData.Set.valid should not > be visible. > > "valid" may be useful for debugging purposes if > certain (for efficiency > reasons unsafe) functions like "fromDistinctAscList" > may produce invalid > representations (if the argument is not strictly > ascending). But I don't > know if this is the case. Indeed. Maybe the best is just to rename the function to a name less likely to clash. Cheers, JP. __ Do you Yahoo!? Yahoo! Search - Find what youre looking for faster http://search.yahoo.com ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] RFC: DData in hierarchical libraries
Hi, > Maybe the documentation to the "0rdered lists" > section can be improved. Could you be more specific about this? > The functions Set.fromAscList and > Set.fromAscDistinctList should be > marked as "unsafe", since it's not clear what sets > result if the input > is not ascending (and/or has duplicates). Would you prefix the function name with unsafe? I wonder what is the best way to do such a marking. > Furthermore, already for > Set.fromList I expect it to be linear, if the input > list happens to be > ascending. I'm afraid it's not, unfortunately. I intend not to fiddle with the implementation, to avoid the involved instability. > "Set.map" is (still) missing. There are two variants > of map functions > with type: > > (Ord a, Ord b) => (a -> b) -> Set a -> Set b > > The first variant requires the function argument f > to be strongly > ascending, a < b => f a < f b, and corresponds to a > map on the > associated ascending lists. > > The second variant does not restrict the function > argument but may > result in a set of smaller size. Maybe this variant > should be called > "Set.image". > > The first variant, maybe call it "Set.mapAsc", is I'd choose "mapMonotonic", from Edison. > again "unsafe", since > the argument function may not be ascending. (The > descending case can be > ignored.) > > The same argument about "ordered lists" apply to the > Map module. In > addition, it would be nice if there were a variant > of "Map.keys" that > returns a set of keys, since the invariant that the > keys are ascending > and distinct may easily get lost, if not captured by > the Set type. A > straight forward implementation is: > > Map.keySet = Set.fromDistinctAscList . Map.keys > > The use of "Set.fromDistinctAscList" is safe in this > case, but - alas - > Map needs to import Set. (But maybe there is even a > faster > implementation of Map.keySet that exploits the > internal representation.) Fine. I'll come up with a revision soon. Thanks for your feedback, JP. __ Do you Yahoo!? Yahoo! Search - Find what youre looking for faster http://search.yahoo.com ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
[Haskell] RFC: DData in hierarchical libraries
Dear haskellers, I propose to add a modified version of DData to the hierachical libraries. DData is a concrete library of collection types, by Daan Leijen. My modifications intend to make DData fit better in the hierarchical libraries. The haddock-generated documentation can be found here: http://users.skynet.be/jyp/DData/doc/index.html while the source code is at http://users.skynet.be/jyp/DData/ddata.tar.gz Any comment is welcome. (Including "I support this proposal" :)) Cheers, JP. PS. For those who don't follow the libraries list, the reasoning leading to this proposal goes as such: * Data.FiniteMap & Data.Set don't use the module system * We need better collection types * A fully fledged collection framework is difficult to agree on for integration in standard. * We should have a concrete types library, leaving the framework for later. * DData looks like a good candidate __ Do you Yahoo!? Yahoo! Search - Find what youre looking for faster http://search.yahoo.com ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] performance tuning Data.FiniteMap
> I believe FiniteMap works by representing the data > in binary trees. It is therefore O(log2(n)) to > read and update. > > However, if my application reads many more times > than it writes, then perhaps I can get a > substantial performance boost by increasing the > branch factor on the tree. For example, if each > node was an array of 256 elements, reads would be > O(log256(n)), a 128x improvement! Not quite. In fact, O(log256(n)) is equivalent to O(log2(n)), because there is only a constant factor between the two. That's why basis of logarithms are usually omitted in O() expressions. Besides, the ratio between log256(n) and log2(n) is more like 8 than 128. (And you'd loose this factor in searching the right subtree, as Ketil pointed out) Tuning Data.FiniteMap probably is not what you want. I don't know, but you can have a look at Data.Hashtable. Just my 2 cents, JP. __ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Re: Use of tab characters...
--- "Sean L. Palmer" <[EMAIL PROTECTED]> wrote: > Joking aside, surely you intelligent people realize > that the internals of a > file format have nothing whatsoever to do with the > user interface of the > editing tool. Something like this would be > completely transparent *if* you > used the right tools. > > This just shows how deeply ingrained the ascii plain > text mindset is in the > programming community. I don't expect anything like > this to ever fly, for > this reason. You guys won't let it. :( M... The dark side clouds everything... Seriously, Plain Text (TM) is a proven technology for editing code, and leveraging the power of XML just to improve over indentation might be off-target. Seriously, programs can (or should...) be encoded at a level of abstraction that matches their semantics more closely than matrix of caracters, and you're right to raise the issue. Seriously, Haskell is already so powerful (read: enables the programmer to define it own astractions) that any layer above it is easily useless. Obviously, something can be done though; http://www.cs.kent.ac.uk/projects/refactor-fp/hare.html Just some thoughts... Cheers! JP. __ Do you Yahoo!? Yahoo! SiteBuilder - Free web site building tool. Try it! http://webhosting.yahoo.com/ps/sb/ ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: High-level technique for program options handling
> > I have a question about error reporting. You use > 'error' quite often. I > > think that this can cause errors to pop up at > strange moments during > > program evaluation. It this a real problem? I > prefer reporting errors > > early in the IO monad. I think there is some > trade-off involved, but I > > can't name it now. > > You're right, it can lead to late error messages. > For example, if two output > files are specified then the program might read its > input, spend some time > processing and only report an error after some > considerable time has passed. > (I haven't actually seen this happen but I'm sure it > would.) > > One reason for using error in functions like > 'uniqueNoDefault' (which checks > that a list has precisely one element and either > returns it or prints a > useful error message) is that I use this function > both from the IO monad and > from pure code. I'm reluctant to duplicate the code > just to avoid this. > > But maybe I should put it in a monad anyway (and go > back and 'fix' all > non-monadic uses)? The error messages produced are > basically telling the > user that they made a mistake so I must have just > read some input from a > file, the command line or the console. I'm not certain this applies, but it should be possible to force evaluation order with a technique similar to deepSeq. It might be cleaner than using IO. http://www.haskell.org/pipermail/haskell/2001-August/007712.html Cheers, JP. __ Do you Yahoo!? Yahoo! Hotjobs: Enter the "Signing Bonus" Sweepstakes http://hotjobs.sweepstakes.yahoo.com/signingbonus ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Canonic labeling of graphs
Hello all, As an exercise, I've implemented an algorithm for canonic relabeling of graphs. (Two graphs are isomorphic iff they have the same canonic labelling) The method used is stolen from Brendan McKay, "Practical graph isomorphism". http://cs.anu.edu.au/~bdm/nauty/PGI/ In the hope that it is useful to anyone, I attach the code (for GHC 6). Any remark is welcome. Cheers! --JP. __ Do you Yahoo!? Yahoo! SiteBuilder - Free, easy-to-use web site design software http://sitebuilder.yahoo.com Nauty.tar.gz Description: Nauty.tar.gz ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
