- Haskell - Haskell.org

Re: graphs and trees again
by Wolfgang Jeltsch 23 Feb '04

23 Feb '04

Am Dienstag, 13. Januar 2004 22:56 schrieb Ross Paterson: > On Tue, Jan 13, 2004 at 09:36:58PM +0100, Wolfgang Jeltsch wrote: > > Am Dienstag, 13. Januar 2004 19:12 schrieb Ross Paterson: > > > * made the types abstract, but provided the equivalent constructor and > > > destructor functions. I'm not sure that gains anything. > > > > Well, I did this to be consistent with the Graph module where abstract > > types are crucial. Yes, it doesn't make much sense. But declaring > > Forest via newtype instead of type surely makes sense because this way > > you're able to define a meaningful Functor instance. > > You get to write fmap instead of map . fmap, but you lose the ability > to treat forests simply as lists. With an seperate forest type, you are also able to use functions which work with arbitrary functors. > > > * added upwards and downwards accumulators (except that your "upwards" > > > accumulator is actually a variant downwards accumulator, with > > > quadratic performance). > > > > What do you mean with "a variant"? Is foldl a variant foldr? > > A downwards accumulation normally replaces each value with the foldl > of the path (list) of items from the root to here (as yours does). > An upwards accumulation normally replaces the values each item with > the (tree) fold of that subtree: > > foldTree :: (a -> [b] -> b) -> Tree a -> b > foldTree n (Node a ts) = n a (map (foldTree n) ts) > > upAccumTree :: (a -> [b] -> b) -> Tree a -> Tree b > upAccumTree f = foldTree ft > where ft a ts = Node (f a (map root ts)) ts > root (Node a _) = a > > It's a different generalization of scanr: yours replaces each item with > a foldr on the list of ancestors. > > BTW, do you have any uses for these things? (The unfolds are useful > for search problems.) I use flattenTree $ downAccuTree (flip (:)) [] $ spanningTree vertex graph to get paths from a graph vertex to every reachable vertex (actually, the reversed paths). Wolfgang

2 2

CVS access library in Haskell?
by Jan Scheffczyk 23 Feb '04

23 Feb '04

Hi all, does anyone know of a Haskell library that provides access to CVS controlled files? Access libraries to other revision control systems, e.g., subversion or arch, would also be greatly appreciated. Yes, I know of darcs, which is great work I think. Still, direct CVS access is of importance. Cheers, Jan

2 1

Compiling HXmlToolbox-3.01 on Mac OS X
by Sachin Desai 23 Feb '04

23 Feb '04

Has anyone successfully compiled this Toolbox on Mac OS X (10.3.2)? I've installed ghc made through darwinports, compiled and installed MD5 and am getting errors when building the toolbox. For example, when I perform "make HXmlParser", I get the following (the first run compiled the modules, hence the Skipping) ghc -Wall -O -fglasgow-exts -i./hparser:./hdom:./hvalidator:./hxpath:./parsec:./http:./popen --make -package lang -package net -package util -o HXmlParser examples/HXmlParser.hs Chasing modules from: examples/HXmlParser.hs Skipping RE ( ./hvalidator/RE.hs, ./hvalidator/RE.o ) Skipping AssocList ( ./hdom/AssocList.hs, ./hdom/AssocList.o ) Skipping NTree ( ./hdom/NTree.hs, ./hdom/NTree.o ) Skipping ParsecPos ( ./parsec/ParsecPos.hs, ./parsec/ParsecPos.o ) Skipping ParsecError ( ./parsec/ParsecError.hs, ./parsec/ParsecError.o ) Skipping ParsecPrim ( ./parsec/ParsecPrim.hs, ./parsec/ParsecPrim.o ) Skipping ParsecChar ( ./parsec/ParsecChar.hs, ./parsec/ParsecChar.o ) Skipping ParsecCombinator ( ./parsec/ParsecCombinator.hs, ./parsec/ParsecCombinator.o ) Skipping Base64 ( ./http/Base64.hs, ./http/Base64.o ) Skipping XmlTreeTypes ( ./hdom/XmlTreeTypes.hs, ./hdom/XmlTreeTypes.o ) Skipping XmlKeywords ( ./hdom/XmlKeywords.hs, ./hdom/XmlKeywords.o ) Skipping XmlTreeFunctions ( ./hdom/XmlTreeFunctions.hs, ./hdom/XmlTreeFunctions.o ) Skipping MonadStateIO ( ./hdom/MonadStateIO.hs, ./hdom/MonadStateIO.o ) Skipping Parsec ( ./parsec/Parsec.hs, ./parsec/Parsec.o ) Skipping POpen ( ./popen/POpen.hs, ./popen/POpen.o ) Skipping HTTP ( ./http/HTTP.hs, ./http/HTTP.o ) Compiling Browser ( ./http/Browser.hs, ./http/Browser.o ) .. lots of warnings ... ./http/Browser.hs:196: Warning: Pattern match(es) are non-exhaustive In the definition of `headerToCookies': Patterns not matched: _ (Header (HdrCustom _) _) _ (Header HdrCacheControl _) _ (Header HdrConnection _) _ (Header HdrDate _) ... ./http/Browser.hs:926: Warning: Pattern match(es) are non-exhaustive In a case alternative: Patterns not matched: HEAD PUT OPTIONS TRACE ghc-6.2: unknown package name: Main make: *** [HXmlParser] Error 1 Does anyone have any insight on why I'm getting this? I've just started to learn Haskell and am not too familiar with the compilation process. Thanks. -- Sachin.

2 1

hmake -- on Windows?
by Graham Klyne 20 Feb '04

20 Feb '04

I just took a quick look at hmake, and it appears to be very Unix/Linux-centred in its applicability. In particular, the installation instructions seem to dpeend on a 'configure' utility, which I think is a Unix/Linux feature that I'm not aware is available for Windows. Am I missing something here? #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

3 2

URI handling code; proposed Network.URI replacement
by Graham Klyne 20 Feb '04

20 Feb '04

I've completed the functionality of my proposed upgrade to Network.URI, though there are still a couple of issues that need to be resolved with the ongoing RFC2396bis work (none critical to the general functionality). This is still work-in-progress, but I'm airing it now to see if folks think it's an acceptable upgrade to the existing Network.URI module. There is an extensive test suite that runs without fault under Hugs and GHCi. This module duplicates the general functionality of the old GHC Network.URI module, and adds: - functions to parse different categories of URI (relative, absolute, URI-reference, etc.) - functions to test for different kinds of URI (returning Bool instead of Maybe URI). - 'relativeFrom', a function to calculate a relative URI with respect to a given base, to complement the existing 'relativeTo'. - functions to perform some common forms of URI normalization. - default behaviour is to not display the password field associated with userinfo in a URI. (This area needs some tidying up). The structure of the underlying URI implementation has changed quite a lot, but I've also defined some accessor functions that reflect the original structure fields. (Oops, I just noticed I forgot to export them) The code can be browsed at: http://www.ninebynine.org/Software/HaskellUtils/Network/ #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

RE: [Haskell] Re: Data.Set whishes
by Bayley, Alistair 20 Feb '04

20 Feb '04

Excuse my ignorance, but why can't you just say: import qualified Data.Set as Set > Hello, > > the naming scheme you mention is nice, in my opinion. > > Alas, it has a problem with hierarchical module names. For > example, you > cannot write Set.empty but have to write Data.Set.empty > instead. As modules > get more and more nested, the qualified names get longer and longer. > > A solution would be if Haskell would allow "partially > qualified" names, e.g., > you import Data and are able to say "Set.empty" afterwards. > > Wolfgang ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

2 1

Parsec question: attempted 'notMatching' combinator
by Graham Klyne 18 Feb '04

18 Feb '04

I've attempted to define a Parsec combinator thus: [[ notMatching :: Show a => GenParser tok st a -> GenParser tok st () notMatching p = try ( do { a <- p ; unexpected (show a) } <|> return () ) ]] It's modelled on the Parsec-provided combinator 'notFollowedBy', but is less fussy about the type of parser allowed. It is an attempt to do a look-ahead. It compiles OK, but it doesn't work as I might expect, e.g. as in: [[ relativeUri :: UriParser URI relativeUri = do { notMatching uscheme ; ua <- option "" ( do { try (string "//") ; uauthority } ) ; up <- upath ; uq <- option "" ( do { string "?" ; uquery } ) ; uf <- option "" ( do { string "#" ; ufragment } ) ; return $ URI { scheme = "" , authority = ua , path = up , query = uq , fragment = uf } } ]] It has the effect of causing several otherwise valid parses to fail. Notably, it is cases that do not match the 'uscheme' parser that fail when they should be matched overall. I *suspect* that the 'try' logic is not interacting cleanly with the case that uscheme parser does not succeed, but I don't have any hard evidence. Can anyone see anything obviously wrong with this? (I have a work-around to the problem, but one that sometimes involves parsing an entire URI twice when trying to isolate relative URIs. I could restructure the code in other ways, but that would defeat my goal of keeping the code very close to the work-in-progress URI specification.) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

4 8

Re: [Haskell] updating graphs non-destructively
by S. Alexander Jacobson 18 Feb '04

18 Feb '04

Thank you for the link to FGL. I also looked at the boilerplate stuff. If *feels* like there should be a way to embed the graph stuff in the boilerplate stuff to allow non-destructive update of arbitrary object graphs without handcoding the mapping of the datastructure to an object graph? Is this possible? Has anyone does this? Any reason to believe its a bad idea? Alternatively, I could decide up front to represent my data as RDF triples (amenable to a graph system), but I'd rather take advantage of Haskell's type system. -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com On Mon, 16 Feb 2004, andrew cooke wrote: > > have you looked at the functional graph library? i can't remember the > details, but think it is efficient and it is certainly a better way to > think about graphs :o) - the details are in the paper by erwig > > http://web.engr.oregonstate.edu/~erwig/fgl/ > > andrew > > S. Alexander Jacobson said: > > In imperative languages, updating an object in a > > graph is an O(1) operation. However, > > non-destructive update appears to be O(n) with the > > size of the graph. For example, suppose we were > > to implement an auction system like eBay: > > > > --Data structures > > data Bid = Bid BidId Auction User Price DateTime > > data Auction = Auction Seller Title Description [Bid] > > data User = User UserId Name [Auction] [Bid] > > > > --Top level database > > type Auctions = FiniteMap AuctionId Auction > > type Users = FiniteMap UserId User > > type Bids = FiniteMap BidId Bid > > type Database = (Auctions,Users,Bids) > > > > If I want to add a bid, it seems like I have > > to traverse the whole Database looking for objects > > that point to the bid. > > > > One alternative is to store pointers rather than > > values e.g. > > > > data Bid = Bid BidId AuctionId UserId Price DateTime > > data Auction = Auction SellerId Title Description [BidId] > > data User = User UserId Name [AuctionId] [BidId] > > > > But that makes graph traversal expensive as each > > edge traversal then costs O(log n). O(log n) may > > be okay for this app, but what if I was > > implementing Friendster/LinkedIn/Tribe/etc.? > > > > Is there a better way to think about this? > > > > -Alex- > > > > _________________________________________________________________ > > S. Alexander Jacobson mailto:me@alexjacobson.com > > tel:917-770-6565 http://alexjacobson.com > > _______________________________________________ > > Haskell mailing list > > Haskell(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell > > > > > > > -- > personal web site: http://www.acooke.org/andrew > personal mail list: http://www.acooke.org/andrew/compute.html >

1 0

Program code storage space exhausted
by Christian Maeder 17 Feb '04

17 Feb '04

Hi, does hugs Nov 2003 allow to increase the space for the program being loaded? (This is not the heap size!) Cheers Christian

1 0

RE: [Haskell] non-ASCII characters in Haddock documentation
by Graham Klyne 17 Feb '04

17 Feb '04

At 10:35 17/02/04 +0000, Simon Marlow wrote: >We didn't choose Latin-1 over UTF-8: the current situation just reflects >the fact that we haven't implemented UTF-8 yet. It's not trivial to >expand GHC's current Alex specification to handle the whole Unicode >character set. See this message for some musings: > >http://www.haskell.org/pipermail/glasgow-haskell-users/2003-December/006 >094.html Ah, yes. It seems that there are two issues here: (1) a way to use alternative character set encodings for Haskell source programs. (2) using an extended repertoire of characters outside comment bodies in a Haskell source module. My comments were directed toward (1). I can see that (2) might be more challenging, but maybe less important to address? You mentioned the obvious place in which one might wish to include extended characters in Haskell non-comment code, viz. in strings. I'm not sure if that would be a good thing to do, for reasons of source code portability/exchangeability, at least until such time as text editors routinely support a fuller character repertoire. (I think that allowing escape sequences and a native Char representation that supports Unicode is basically a solved problem, is it not?) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0