February 2004 - Haskell

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

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

17 Feb '04

> >It may seem so to western europeans, but others may differ. > >A case could be made for UTF-8. > > I tend to agree. Further, the choice of defaulting to > Latin-1 seems a > strange one when much of the rest of the world (well, the > networking world) > seems to be moving towards more universal character set > encodings. 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 Cheers, Simon

1 0

updating graphs non-destructively
by S. Alexander Jacobson 17 Feb '04

17 Feb '04

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

2 1

RE: [Haskell] non-ASCII characters in Haddock documentation
by Simon Marlow 16 Feb '04

16 Feb '04

> Am Freitag, 13. Februar 2004 01:23 schrieben Sie: > > wolfgang: > > > Hello, > > > > > > how do I insert non-ASCII and maybe even non-Latin-1 characters in > > > Haddock documentation? > > > > > > Wolfgang > > > > Looks like it might be difficult. The haddock lexer src has: > > > > $alphanum = [A-Za-z0-9] > > > > So, non-ascii might not be lexed. > > Hello, > > I meant non-ASCII characters in source code comments like this: > {-| > The execution time of this function is /n³/. > -} > Currently, Haddock seems to copy the bytes making up the > non-ASCII character > verbatim to the HTML file. But since the HTML file doesn't contain a > character set specification, it is illformed and it depends > on the browser how this situation is handled. It shouldn't be too hard to fix this, at least for Latin-1 (full Unicode would be somewhat harder). I'll add it to the TODO list. Cheers, Simon

4 4

RE: [Haskell] non-ASCII characters in Haddock documentation
by Simon Marlow 16 Feb '04

16 Feb '04

> On Mon, Feb 16, 2004 at 10:20:30AM -0000, Simon Marlow wrote: > > Wolfgang Jeltsch <wolfgang(a)jeltsch.net> writes: > > > I meant non-ASCII characters in source code comments like this: > > > {-| > > > The execution time of this function is /n³/. > > > -} > > > Currently, Haddock seems to copy the bytes making up the > > > non-ASCII character > > > verbatim to the HTML file. But since the HTML file > doesn't contain a > > > character set specification, it is illformed and it depends > > > on the browser how this situation is handled. > > > > It shouldn't be too hard to fix this, at least for Latin-1 (full > > Unicode would be somewhat harder). I'll add it to the TODO list. > > While Haskell's source charset is specified as Unicode, Haskell source > files don't specify the byte encoding they use, so any source > file using non-ASCII characters isn't portable. Entrenching Latin-1 > would make the move to Unicode more difficult. True, but GHC currently assumes Latin-1 as the encoding for source files. I don't see it as entrenching Latin-1, just that we only accept Latin-1 encoded source files; at some point in the future we might accept other encodings. Making the same simplifying assumption in Haddock doesn't seem that big a deal. Cheers, Simon

1 0

Wiki manager change
by Keith Wansbrough 16 Feb '04

16 Feb '04

Hi all... the Haskell Wiki http://haskell.org/hawiki/ is under new management. From now on, please contact Shae Erisson <shae(a)ScannedInAvian.com> with your requests, comments, or feedback on the Wiki site - or, of course, improve and extend the site yourself! Thanks all for your contributions - please keep them coming, and make this resource even more useful. Cheers, --KW 8-) Former Haskell Wiki manager -- Keith Wansbrough <kw217(a)cl.cam.ac.uk> http://www.cl.cam.ac.uk/users/kw217/ University of Cambridge Computer Laboratory.

1 0

3d or Nd geometry library?
by Abraham Egnor 16 Feb '04

16 Feb '04

I was somewhat surprised to see that there's only one geometry library on the haskell libraries page, and further dismayed to find that it for the most part only does 2d. It seems like haskell should be a natural fit for higher-order geometric libraries - has anyone heard of such? Abe

2 1