- Haskell-Cafe - Haskell.org

Re: Lazy Parsing
by John Hughes 28 Feb '02

28 Feb '02

There's a combinator which Phil Wadler called "guarantee" which makes a parser lazy -- guarantee p succeeds at once, with a result which will be produced, when demanded, by p. Many parsing libraries include it under one name or another... John

1 0

Re: higher-kind deriving ... or not
by C T McBride 27 Feb '02

27 Feb '02

Hi On Thu, 28 Feb 2002, Tom Pledger wrote: > C T McBride writes: > | > data Fix f = Fix (f (Fix f)) > | > | There's no equivalent first-order definition. This is where > | higher-kind parameters actually buy us extra stuff, and it's also the > | point at which the first-order constraint for show becomes hopeless. > > Did you see the technique Mark Tullsen posted last year, for making > instances in the presence of a fixpoint? I've found it useful. > > http://haskell.cs.yale.edu/pipermail/haskell/2001-May/003942.html Thanks for the pointer. Yes, that looks like a kind of hard-coding of the lifting to higher kinds that I'm after. If I understand things correctly, it would seem that for every type class C t, indexed by types, one can manufacture the constructor class FC f which asserts that f preserves C-ness. For each C-method m :: blah[t] one gives the FC method fm :: C t => blah[f t] One can lift further, by defining classes for constructors with higher-kind parameters which take FC-ness (or whatever) to C-ness. Requiring FC f (a first-order constraint on a higher-kind thing) is a plausible fake of requiring (forall a. C a => C (f a)) (a higher-order constraint on types). If I read correctly, automating this construction, effectively yielding computation of classes from kinds, is part of Simon PJ and Ralf Hinze's `Deriving Type Classes' proposal. The functionality is clearly desirable. It does, however, come at the cost of introducing a third and still separate programming language as a component of Haskell---the language of programming over kinds. It's no good asking when this will stop, because it doesn't. It is worth asking when the different layers of this hierarchy will acquire a greater uniformity. Cheers Conor

1 0

RE: higher-kind deriving ... or not
by Simon Peyton-Jones 27 Feb '02

27 Feb '02

| > data Wonky f | > = Wonky | > | Manky (f (Wonky f)) | > deriving Show | | The trouble is that when I ask either hugs -98 or ghci | -fglasgow-exts to | | show (Wonky :: Wonky Copy) | | the poor compiler's brain explodes. I fixed this a few weeks ago. GHC (5.03) now says: Foo.hs:3: No instance for `Show (f (Wonky f))' When deriving the `Show' instance for type `Wonky' | I tried to guess the type of the show instance derived for | Wonky. Being a naive sort of chap, I thought it might be | | show :: (forall a. Show a => Show (f a)) => Wonky f -> String Not naive. That's exactly the right type. See Section 7 of "Derivable type classes". http://research.microsoft.com/~simonpj/Papers/derive.htm Havn't implemented this, yet, alas. | It's clear that with typing problems, inference becomes | unsustainable pretty soon after you leave the safe harbours | of the Hindley-Milner system. However, lots of lovely | programs have more interesting types: it would be very | frustrating if Haskell forbade these programs just because | their types were not inferrable---not least since, for these | jobs, we usually do think of the type first and the code | afterwards. Sensibly, Haskell allows us to write these types | down, so the machine's task is merely checking. This hybrid | approach preserves type inference for `old' code, whilst | promoting more adventurous programming by allowing us to say | what we mean when the machine is too dim to guess. I agree wholeheartedly with this; it's exactly the approach I'm trying to take with GHC. One obvious extension is to let the user specify the context for a derived instance decl, but still let the compiler generate the code. Havn't done this either! Simon

1 0

higher-kind deriving ... or not
by C T McBride 27 Feb '02

27 Feb '02

Hi I'm rather fond of fixpoint constructions like this one: > newtype Copy a = Copy a deriving Show > data Wonky f > = Wonky > | Manky (f (Wonky f)) > deriving Show (Clearly this is an ill-motivated example, but the real example which caused this problem is available on request...) The trouble is that when I ask either hugs -98 or ghci -fglasgow-exts to show (Wonky :: Wonky Copy) the poor compiler's brain explodes. I take it this is a known problem with instance inference, deriving, etc. Of course, it's easy to write my own show for Wonky Copy, but that's a tad annoying. I tried to guess the type of the show instance derived for Wonky. Being a naive sort of chap, I thought it might be show :: (forall a. Show a => Show (f a)) => Wonky f -> String but that's a syntax error. A little more tinkering, and it looks like it might be show :: Show (f (Wonky f)) => Wonky f -> String Is this really the type of show? If so, no wonder there's a problem. I don't want to start an argument about how to solve this problem. I do want to suggest that, for the time being, it would be better to reject `deriving Show' for type constructors like Wonky (ie those with higher-kind parameters) than to generate instances which break the compiler. Or am I just being a spoilsport? Conor

3 4

java program
by Stewart Litt 27 Feb '02

27 Feb '02

dear sir/madam iam contacting you regarding a java problem which i have come across. My teacher at manchester met has set a problem for us to solve but thinking his teaching is excellent and everyone understands him wen no one does I would appreciate you helping me in this problem as it would save us from embarrassment. THE PROBLEM: Consider a simplified plan of the liverpool bus system. The system consists of a network of bus stops(at most 20) and bus lines (at most 5). Each bus stop has a unique name and each busline has a unique number. Each bus stop is connected to other bus stops by at most 3 different bus lines. Each of these bus lines connects a bus stop to exactly one other bus stop and for each bus stop and each connecting bus line it is known how many minutes the bus needs to get to the next bus stop. The objectives are to design and implement in java: 1. A representation of the bus system using suitable data structures. 2. A mechanism to go from one bus stop to a conected bus stop via a particular bus line. 3. A mechanism for searching for a connection between two given bus stops. A command line text based interface should be provided that will allow the user to issue a series of the following five commands: start: Allows to enter the current bus stop by name and resets the total journey time to zero. list: The system will show the total journey time so far, and all information on the current bus stop, that is, its name and the numbers of all outgoing bus lines. go: The system asks for the number of a busline. If the number is that of an outgoing busline, then the system finds out the busstop connected to the current bus stop and makes it the new current bus stop. If the number is not that of an outgoing bus line, then the system will indicate this by a message , but make no other changes. search: The system asks for the name of a bus stop. The system will then indicate whether there is a way to get to this bus stop from the current bus stop, but makes no other changes. exit: Stops and exits the system. Description of the liverpool bus stop below. THE LIVERPOOL BUS SYSTEM Bus Stop Outgoing bus line Connected bus stop Time in mins Bootle strand 22 South road 11 Pier head 10 Shiel road 14 22 Bootle strand 7 79 Edge hill 11 Edge hill 79 Picton clock 10 Green lane 10 Page moss 13 22 Bootle strand 18 Page moss 10 Prescot 8 Picton clock 79 Netherly 21 Shiel road 10 Green lane 5 South road 22 Green lane 9 _________________________________________________________________ MSN Photos is the easiest way to share and print your photos: http://photos.msn.com/support/worldwide.aspx

1 0

a more practical version of getLine???
by Rich 26 Feb '02

26 Feb '02

Hi, I'm writing a program for my final project at uni and I've come across the following annoying bug in my program. Basically, I have an interactive text prompt and I wish to be able to write commands into the prompt. I am currently using the function 'getLine', which as it's name suggests reads a line of text from the prompt. Unfortunately, when the delete key is used while writing to the prompt, the output differs (so typing "loaf" then 'delete' and then "d" does not seem to produce the same output as typing "load"). Also, the left and right arrow keys don't work, as they do in any normal text prompt. Any suggestins as to an alternative method to read the input??? (I'm by no means a Haskell expert btw, so I may have to be spoon fed!) thanks for your help, Rich.

3 2

Help
by Juan M. Duran 25 Feb '02

25 Feb '02

Hi, I need to parse a string to a list of integer, like this: "12 32\n15...." to [12,32,15...] f :: String -> [Int] What I´ve found is the function "words" which does words :: String -> [String] it is in the Prelude.hs then if I have something like "12 32\n15..." with words I get ["12","32","15"...] which is cool but not exactly what I need. Would you help me? Thanks J. ------------------------------------ Porque la única lucha que se pierde, es la que se abandona, ¡Ni un paso atrás!

2 2

RE: Monadic Call/CC?
by Simon Marlow 25 Feb '02

25 Feb '02

> At 2002-02-23 07:55, Marcin 'Qrczak' Kowalczyk wrote: > > >It's in GHC in module MonadCont, together with a monad transformer > >providing continuations and some instances. > > Could this sort of thing _please_ be added to > <http://www.haskell.org/ghc/docs/latest/set/book-hslibs.html> > or somewhere? Is this documented somewhere? My apologies for the lack of documentation for some of these libraries, and the generally poor state of the doumentation for hslibs. Some of the libraries come from external sources, and in some cases the authors didn't provide documentation, or provided it in a form that we couldn't use directly. For the next release of GHC, I'm hoping we can do a much better job, though not just by writing more documentation but by generating more of it automatically from the source code. That's the plan; we don't have anything concrete yet. Cheers, Simon

1 0

Re: Graphs
by David Feuer 25 Feb '02

25 Feb '02

I seem to remember an article about functional graph algorithms using extra-lazy arrays. Anyone know if these arrays have appeared in any mainstream implementation? David Feuer

2 1

RE: Survival of generic-classes in ghc
by Simon Peyton-Jones 25 Feb '02

25 Feb '02

| > Another possiblity would be to make the ConCls class look like this | > class ConCls c where | > name :: String | > arity :: Int | > ...etc... | > | > Now we'd have to give an explicit type argument at the call site: | > | > show {| Constr c t |} (Con x) = (name {| c |}) ++ show x | > | > I quite like the thought of being able to supply explicit type | > arguments.... but I don't konw how to speak about the order of type | > parameters. What order does map takes its two type parameters in? | | Sorry, this seems like a non-sequitur to me? | | 'map' has type '(a->b) -> [a] -> [b]'; supplying explicit | type parameters would mean giving values to 'a' and 'b'. If | I wanted to propose notation for this, I would suggest, e.g., | (map :: (String -> Int) -> [String] -> [Int]) length | ["Hello", "World"] | | 'name' (above) has type 'String'; the '{| c |}' is not | providing a type parameter in the same sense. Yes it is. 'name' would have type forall c. ConCls c => String It requires a type argument, just like map. Simon

1 0