- Haskell-Cafe - Haskell.org

Re: [Haskell] Read Instances for Data.Map and Data.Set
by dons＠cse.unsw.edu.au 20 Oct '05

20 Oct '05

mai99dgf: > Hi folks, > > I was really annoyed by the fact that for Data.Map and Data.Set are no Read > instances declared, but Show instances are! I believe there should be some > kind of unwritten rule that in the standart lib the Show and Read instances > come pairwise and are fully compatible. There are some things that are Showable, but would be wrong to be Readable. Dynamics come to mind. That's not the case with Map, though :) (moved to haskell-cafe@ just in case :) -- Don

1 0

RE: [Haskell-cafe] FPS lib
by Simon Marlow 20 Oct '05

20 Oct '05

On 18 October 2005 21:04, John Meacham wrote: > On Tue, Oct 18, 2005 at 10:39:24AM +0300, Einar Karttunen wrote: >> On 18.10 10:44, Bulat Ziganshin wrote: >>> 2) as i say you before, i need to sort filenames in windows fashion >>> (case-ignoring), so if you will include case-ignoring comparision >>> operators - i will be glad >> >> Case ignoring comparisons make only sense on characters - not on >> bytes. And fps is ignoring character set conversion issues. I think >> the proper way is to provide a layer on top of (and separate from) >> fps that does conversion into character strings where things like >> case make sense. > > My FastString library always stores everything as UTF8 to good effect. > I have some nice fast unboxed UTF8 character folding routines in there > too which you might want to grab if you go the UTF8 route. (which I > recommend highly). > > http://repetae.net/john/repos/jhc/PackedString.hs I believe I stole your UTF-8 code for my Data.PackedString.UTF8 version (which Don uploaded here http://www.cse.unsw.edu.au/~dons/packedstring.tar.gz) It might be slightly modified though; in my version I wanted to support foldr/build optimisation of things like (pack (map f xs)) and (unpack s ++ t). IIRC I got it working for unpack, but not for pack. Cheers, Simon

2 1

Parsec vs ReadP
by Sebastian Sylvan 20 Oct '05

20 Oct '05

Can anyone briefly compare these two parsing-libraries? In short, which one is better? /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

3 2

RE: [Haskell-cafe] Prebuilt FPS for Windows
by Simon Marlow 19 Oct '05

19 Oct '05

On 18 October 2005 17:01, Joel Reymont wrote: > Since I cannot build Data.FastPackedString on Windows (ghc crashes) > and it's the only library I really depend on, would someone have a > pre-built version or let me know how I can build it without Cabal? A workaround for that crashing problem is to compile the Setup.lhs script using GHC first, and then run it: $ ghc --make Setup.lhs -o setup $ ./setup configure etc. > On a related note, Haskell tools for Windows (happy, alex) come with > extra files (templates). Where are these to be placed? On Windows, they are placed in the same folder as the executable. Cheers, Simon

1 0

RE: [Haskell] reader-like IO, parents of threads
by Simon Marlow 19 Oct '05

19 Oct '05

Certainly, adding hooks to forkIO is possible. Also, providing thread local data directly is something we could do quite easily (and efficiently) in GHC. Cheers, Simon On 18 October 2005 19:12, Frederik Eaton wrote: > What about adding support for hooks in forkIO? These could be useful > for other things as well. Pthreads could be said to have this > functionality: > > -- Function: int pthread_atfork (void (*PREPARE)(void), void > (*PARENT)(void), void (*CHILD)(void)) > `pthread_atfork' registers handler functions to be called just > before and just after a new process is created with `fork'. The > PREPARE handler will be called from the parent process, just > before the new process is created. The PARENT handler will be > called from the parent process, just before `fork' returns. The > CHILD handler will be called from the child process, just before > `fork' returns. > > As well as: > > -- Function: void pthread_cleanup_push (void (*ROUTINE) (void *), > void *ARG) > `pthread_cleanup_push' installs the ROUTINE function with > argument ARG as a cleanup handler. From this point on to the > matching `pthread_cleanup_pop', the function ROUTINE will be > called with arguments ARG when the thread terminates, either > through `pthread_exit' or by cancellation. If several cleanup > handlers are active at that point, they are called in LIFO > order: the most recently installed handler is called first. > > Of course, 'fork' has a bit of a different meaning in pthreads. I > don't know if there is support for handlers which are run when a new > thread is created. > > (Pthreads also has support for "thread-specific data": > > -- Function: int pthread_setspecific (pthread_key_t KEY, const > void *POINTER) > `pthread_setspecific' changes the value associated with KEY > in the calling thread, storing the given POINTER instead. > > If there is no such key KEY, it returns `EINVAL'. Otherwise > it returns 0. > > -- Function: void * pthread_getspecific (pthread_key_t KEY) > `pthread_getspecific' returns the value currently associated > with KEY in the calling thread. > > If there is no such key KEY, it returns `NULL'. > ) > > Regards, > > Frederik > > On Tue, Oct 18, 2005 at 11:47:29AM +0100, Simon Marlow wrote: >> It seems that you can do this as long as you provide your own >> version of forkIO, but not if you want to use the built-in forkIO. >> >> One could argue that getting the parent ThreadId is something that >> should be supported natively by forkIO, and I might be inlined to >> agree. Unfortunately there are some subtleties: currently a ThreadId >> is represented by a pointer to the thread itself, which causes the >> thread to be kept alive. This has implications not only for space >> leaks, but also for reporting deadlock: if you have a ThreadId for a >> thread, you can send it an exception with throwTo at any time, and >> hence the runtime can never determine that the thread is deadlocked >> so it will never get the NonTermination exception. Perhaps we need >> two kinds of ThreadId: a weak one for use in Maps, and a strong one >> that you can use with throwTo. But then building a Map in which >> some elements can be garbage collected is a bit tricky (it can be >> done though; see our old Memo table implementation in >> fptools/hslibs/util/Memo.hs). >> >> Cheers, >> Simon >> >> On 16 October 2005 20:53, Frederik Eaton wrote: >> >>> John Meacham suggested that I should be a little more clear about >>> the semantics I'm seeking. Also, apparently it isn't possible to >>> implement writeTLRef/modifyTLRef with the data structure I gave: >>> >>>> data TLRef a = TLR a (MVar (Map ThreadId a)) >>> (the first argument is a default value, the second is a map storing >>> the values in each thread. The MVar is for safe concurrent access) >>> >>> Without those functions, it looks a little more like the Reader >>> monad I'm comparing it to. >>> >>> - What happens on fork? The child thread effectively gets a "copy" >>> of each TLRef in its parent. They have the same values, but >>> modifying them using withTLRef has no effect on the values in other >>> threads. >>> >>> - Can you pass a TLRef to a different thread? Yes, but the value it >>> holds will not be the same when it is dereferenced in a different >>> thread. >>> >>> The problem with writeTLRef is that if a child thread looks up the >>> default value for an unbound reference by looking up the value in >>> its parent, but after calling forkIO the parent changes the value >>> with writeTLRef, then the child thread will get the wrong value. It >>> is supposed to only see the value which was stored in the reference >>> at the point where forkIO was called. >>> >>> Also, for this reason, I think withTLRef would have to be >>> implemented by creating a separate thread with forkIO and waiting >>> for it to finish. This would avoid overwriting a value which other >>> child threads might still need to access. >>> >>> Note that an e.g. "myParentThreadId" function isn't enough - what >>> is needed is a >>> >>> parentThreadId :: ThreadId -> IO (Maybe ThreadId) >>> >>> which can look up the parent of an arbitrary thread. >>> >>> Alternatively, if 'forkIO' supported hooks to run before and/or >>> after forking, then a 'parentThreadId' function could be >>> implemented from that. >>> >>> Frederik >>> >>> On Sun, Oct 16, 2005 at 04:40:40AM -0700, Frederik Eaton wrote: >>>> Hi, >>>> >>>> I'm trying to get MonadReader-like functionality in the IO monad. >>>> It doesn't appear possible implement it with the interfaces that >>>> Haskell98 or GHC provide. I'm looking for something like >>>> "thread-local variables". The interface could be something like >>>> this: >>>> >>>> newTLRef :: a -> IO (TLRef a) >>>> withTLRef :: TLRef a -> a -> IO b -> IO b >>>> readTLRef :: TLRef a -> IO a >>>> writeTLRef :: TLRef a -> a -> IO () >>>> modifyTLRef :: TLRef a -> (a -> a) -> IO () >>>> >>>> This would have a lot of uses. I am aware of the "Implicit >>>> Configurations" paper by Kiselyov and Shan, but a solution such as >>>> theirs which requires modifying the type signatures of all >>>> intermediate function calls is not suitable. I want to be able to >>>> say "run algorithm A using database D" without requiring all of the >>>> functions in algorithm A to know that databases are somehow >>>> involved. One way to look at it is that I am seeking something >>>> like the type-based approach, but easier and with less explicit >>>> syntax; another way to look at it is that I am seeking something >>>> like a global IORef based approach, but more safe. >>>> >>>> An implementation based on ThreadId-keyed maps is almost workable: >>>> >>>> data TLRef a = TLR a (MVar (Map ThreadId a)) >>>> >>>> The problem with this is that while it is possible to find out the >>>> ThreadId of the current thread, it doesn't appear to be possible to >>>> get the ThreadId of the parent thread, which would be needed for >>>> values to be properly inherited. >>>> >>>> Is there a way around this? Will there ever be standard support for >>>> either finding the thread id of the parent of the current thread, >>>> or for something like the thread-local references I have proposed? >>>> >>>> Thanks, >>>> >>>> Frederik >>>> _______________________________________________ >>>> Haskell mailing list >>>> Haskell(a)haskell.org >>>> http://www.haskell.org/mailman/listinfo/haskell >>>> >>> _______________________________________________ >>> Haskell mailing list >>> Haskell(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/haskell >> >> _______________________________________________ >> Haskell mailing list >> Haskell(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell

1 0

pre-built ghc 6.4.1 crashes building FPS
by Joel Reymont 19 Oct '05

19 Oct '05

Folks, I downloaded and installed the pre-built ghc 6.4.1 on Windows XP and Win2k. I tried building FastPackedStrings but ghc crashes soon after starting. Any tips? I'm gonna try with a hand-built ghc but somehow doubt it will help. Thanks, Joel -- http://wagerlabs.com/

7 13

Re: [Haskell-cafe] Regular Expressions without GADTs
by oleg＠pobox.com 19 Oct '05

19 Oct '05

Conor McBride wrote: > Neither Oleg nor Bruno translated my code; they threw away my > structurally recursive on-the-fly automaton and wrote combinator parsers > instead. That's why there's no existential, etc. The suggestion that > removing the GADT simplifies the code would be better substantiated if > like was compared with like. The following code specifically tries to be as close to the original Conor McBride's code as possible. I only removed local type annotations (turn out unnecessary) and replaced `ap' with `liftM' as a matter of personal preference. > Where we came in, if you recall, was the use of a datatype to define > regular expressions. I used a GADT to equip this type with some useful > semantic information (namely a type of parsed objects), and I wrote a > program (divide) which exploited this representation to compute the > regexp the tail of the input must match from the regexp the whole input > must match. This may be a bit of a weird way to write a parser, but it's > a useful sort of thing to be able to do... That particular feature is fully preserved. Data types are used to define regular expression: > p = (Star (Mult (Star (Check (== 'a'))) (Star (Check (== 'b'))))) > > testp = parse p "abaabaaabbbb" Moreover, *RX> :t p p :: Star (Mult (Star (Check Char)) (Star (Check Char))) the regular expression is apparent in the type of the `parser' (or its representation, to be precise). One can easily define data types Digit, Alphanumeric, WhiteSpace, etc. and so type will look more informative. Here's one step to regular types... Instead of GADT, a type class is used to associate semantic information with the data type (with labels). Typing is more explicit now. > And that's the point: not only does the GADT have all the disadvantages > of a closed datatype, it has all the advantages too! A type class can be closed too, thanks to functional dependencies. You were right: the code below is just the mechanical reshuffling of the original code, using the translation I come across a year ago. `empty' and `division' are now grouped by the parser type, which I personally like. It is hard to see any loss of expressiveness by getting rid of GADTs in this case. More explicit type is an advantage. Also an advantage is the fact that `pattern match' is guaranteed exhaustive. If I forgot to implement some particular parser, that would be a type error (rather than a pattern-match run-time error, as is the case with ADT/GADT). > Moreover, once you have to start messing about with equality > constraints, the coding to eliminate GADTs becomes a lot hairier. I > implemented it back in '95 (when all these things had different names) > and I was very glad not to have to do it by hand any more. The discovery of the presence of type equality in Haskell changes things a great deal. It would be interesting to see how your code of '95 will look now. Writing an equality and even _dis-equality_ constraint is just as simple as |TypeEq a b HTrue| or |TypeEq a b HFalse|. {-# OPTIONS -fglasgow-exts #-} module RX where import Control.Monad class RegExp r tok a | r tok -> a where empty :: r -> [tok] -> Maybe a divide :: tok -> r -> Division tok a data Zero = Zero data One = One newtype Check tok = Check (tok -> Bool) data Plus r1 r2 = Plus r1 r2 data Mult r1 r2 = Mult r1 r2 newtype Star r = Star r data Empty = Empty data Division tok x = forall r y. RegExp r tok y => Div r (y -> x) parse :: (RegExp r tok x) => r -> [tok] -> Maybe x parse r t@[] = empty r t parse r (t : ts) = case divide t r of Div q f -> liftM f $ parse q ts nullt :: tok -> [tok] nullt _ = [] instance RegExp Zero tok Empty where empty _ _ = mzero divide _ _ = Div Zero naughtE instance RegExp One tok () where empty _ _ = return () divide _ _ = Div Zero naughtE instance RegExp (Check tok) tok tok where empty _ _ = mzero divide t (Check p) | p t = Div One (const t) divide _ _ = Div Zero naughtE instance (RegExp r1 tok a, RegExp r2 tok b) => RegExp (Plus r1 r2) tok (Either a b) where empty (Plus r1 r2) t = (liftM Left $ empty r1 t) `mplus` (liftM Right $ empty r2 t) divide t (Plus r1 r2) = case (divide t r1, divide t r2) of (Div q1 f1, Div q2 f2) -> Div (Plus q1 q2) (f1 +++ f2) instance (RegExp r1 tok a, RegExp r2 tok b) => RegExp (Mult r1 r2) tok (a,b) where empty (Mult r1 r2) t = liftM2 (,) (empty r1 t) (empty r2 t) divide t (Mult r1 r2) = case (empty r1 (nullt t), divide t r1, divide t r2) of (Nothing, Div q1 f1, _) -> Div (Mult q1 r2) (f1 *** id) (Just x1, Div q1 f1, Div q2 f2) -> Div (Plus (Mult q1 r2) q2) (either (f1 *** id) (((,) x1) . f2)) instance RegExp r tok a => RegExp (Star r) tok [a] where empty _ _ = return [] divide t (Star r) = case (divide t r) of Div q f -> Div (Mult q (Star r)) (\ (y, xs) -> (f y : xs)) (***) :: (a -> b) -> (c -> d) -> (a, c) -> (b, d) (f *** g) (a, c) = (f a, g c) (+++) :: (a -> b) -> (c -> d) -> Either a c -> Either b d (f +++ g) (Left a) = Left (f a) (f +++ g) (Right c) = Right (g c) naughtE :: Empty -> x naughtE = undefined p = (Star (Mult (Star (Check (== 'a'))) (Star (Check (== 'b'))))) testp = parse p "abaabaaabbbb"

1 0

Parsing in Practice
by Tom Hawkins 19 Oct '05

19 Oct '05

I am writing a parser for a big, ugly, standard language and I need to decide between using either Happy or Parsec. I currently have a priliminary LALR(1) grammar, so a port to Happy would be relatively easy. But, I'm wondering if life would be easier if I chose Parsec's combinator parsing instead. It's error reporting seems to be top notch and it's "optional", "many", and "sepBy1" combinators are very elegant. However, I have a few concerns with Parsec. First is performance; what factor of slow-down should I expect? Second is bug prevention. I don't have much experience writing LL(n) grammars, so how easy is it to introduce bugs in a Parsec grammar? Even though I hate debugging LALR(1) parsing ambiguities, it prevents problems. Also, it appears the GHC developers chose Happy for Haskell. What was their rational? Thanks for your recommendations, one way or another. -Tom

3 2

Prebuilt FPS for Windows
by Joel Reymont 19 Oct '05

19 Oct '05

Folks, Since I cannot build Data.FastPackedString on Windows (ghc crashes) and it's the only library I really depend on, would someone have a pre-built version or let me know how I can build it without Cabal? On a related note, Haskell tools for Windows (happy, alex) come with extra files (templates). Where are these to be placed? Thanks, Joel -- http://wagerlabs.com/

1 0

Re: [Haskell-cafe] Regular Expressions, was Re: Interest in helping w/ Haskell standard
by Martin Sulzmann 18 Oct '05

18 Oct '05

Semantic subtyping issue: Assume we have a function f of type f :: Reg (r*) -> ... to which we pass a value x of type Reg (r,r*). We have that (r,r*) is a semantic subtype of r*, hence, the code f x is accepted in languages such as XDuce/CDuce. I'm just saying that the fact regexp can be represented via GADTs doesn't imply that we get the same expressive power of languages such as XDuce/CDuce. Martin Hongwei Xi writes: > Hi Martin: > > Thanks for the message. > > No, I am not on the list. > > Back then, we did something similar but for a different > purpose. The idea is like this: > > We wanted to represent an XML document as a pair: > > XML (r) * Reg (r) > > where r stands for some regexp and Reg(r) is a > singleton type. When performing search over XML(r), > we can use Reg(r) as some kind of pilot value > (which is a lot smaller than XML(r)) to guide the > search. For instance, it is often easy to tell from > Reg(r) that an item to be found is not in XML(r) and > thus we can skip searching XML(r) entirely. > This is sort of like indexing scheme in database. > > BTW, I am not sure what kind of 'semantic typing' > you have in mind. An example? > > --Hongwei > > Computer Science Department > Boston University > 111 Cummington Street > Boston, MA 02215 > > Email: hwxi(a)cs.bu.edu > Url: http://www.cs.bu.edu/~hwxi > Tel: +1 617 358 2511 (office) > Fax: +1 617 353 6457 (department) > > > > On Mon, 17 Oct 2005, Martin Sulzmann wrote: > > >> > >>Very interesting Conor. Do you know Xi et al's APLAS'03 paper? > >>(Hongwei, I'm not sure whether you're on this list). > >>Xi et al. use GRDTs (aka GADTs aka first-class phantom types) > >>to represent XML documents. There're may be some connections > >>between what you're doing and Xi et al's work. > >> > >>I believe that there's an awful lot you can do with GADTs > >>(in the context of regular expressions). But there're two things > >>you can't accomplish: > >>semantic subtyping and regular expression pattern matching > >>a la XDuce/CDuce. Unless somebody out there proves me wrong. > >> > >>Martin > >> > >> > >> > >>Hi folks, > >> > >>Inspired by Ralf's post, I thought I'd just GADTize a dependently typed=20 > >>program I wrote in 2001. > >> > >>Wolfgang Jeltsch wrote: > >> > >>> Now lets consider using an algebraic datatype for regexps: > >>> > >>> data RegExp > >>> =3D Empty | Single Char | RegExp :+: RegExp | RegExp :|: RegExpt | Ite= > >>r RegExp > >>> > >>>Manipulating regular expressions now becomes easy and safe =E2=80=93 you= > >> are just not=20 > >>>able to create "syntactically incorrect regular expressions" since durin= > >>g=20 > >>>runtime you don't deal with syntax at all. > >>> =20 > >>> > >> > >>A fancier variation on the same theme... > >> > >> > data RegExp :: * -> * -> * where > >> > Zero :: RegExp tok Empty > >> > One :: RegExp tok () > >> > Check :: (tok -> Bool) -> RegExp tok tok > >> > Plus :: RegExp tok a -> RegExp tok b -> RegExp tok (Either a b) > >> > Mult :: RegExp tok a -> RegExp tok b -> RegExp tok (a, b) > >> > Star :: RegExp tok a -> RegExp tok [a] > >> > >> > data Empty > >> > >>The intuition is that a RegExp tok output is a regular expression=20 > >>explaining how to parse a list of tok as an output. Here, Zero is the=20 > >>regexp which does not accept anything, One accepts just the empty=20 > >>string, Plus is choice and Mult is sequential composition; Check lets=20 > >>you decide whether you like a single token. > >> > >>Regular expressions may be seen as an extended language of polynomials=20 > >>with tokens for variables; this parser works by repeated application of=20 > >>the remainder theorem. > >> > >> > parse :: RegExp tok x -> [tok] -> Maybe x > >> > parse r [] =3D empty r > >> > parse r (t : ts) =3D case divide t r of > >> > Div q f -> return f `ap` parse q ts > >> > >>Example > >> > >>*RegExp> parse (Star (Mult (Star (Check (=3D=3D 'a'))) (Star (Check (=3D=3D= > >>=20 > >>'b'))))) "abaabaaabbbb" > >>Just [("a","b"),("aa","b"),("aaa","bbbb")] > >> > >>The 'remainder' explains if a regular expression accepts the empty=20 > >>string, and if so, how. The Star case is a convenient=20 > >>underapproximation, ruling out repeated empty values. > >>=20 > >> > empty :: RegExp tok a -> Maybe a > >> > empty Zero =3D mzero > >> > empty One =3D return () > >> > empty (Check _) =3D mzero > >> > empty (Plus r1 r2) =3D (return Left `ap` empty r1) `mplus` > >> > (return Right `ap` empty r2) > >> > empty (Mult r1 r2) =3D return (,) `ap` empty r1 `ap` empty r2 > >> > empty (Star _) =3D return [] > >> > >>The 'quotient' explains how to parse the tail of the list, and how to=20 > >>recover the meaning of the whole list from the meaning of the tail. > >> > >> > data Division tok x =3D forall y. Div (RegExp tok y) (y -> x) > >> > >>Here's how it's done. I didn't expect to need scoped type variables, but=20 > >>I did... > >> > >> > divide :: tok -> RegExp tok x -> Division tok x > >> > divide t Zero =3D Div Zero naughtE > >> > divide t One =3D Div Zero naughtE > >> > divide t (Check p) | p t =3D Div One (const t) > >> > | otherwise =3D Div Zero naughtE > >> > divide t (Plus (r1 :: RegExp tok a) (r2 :: RegExp tok b)) =3D > >> > case (divide t r1, divide t r2) of > >> > (Div (q1 :: RegExp tok a') (f1 :: a' -> a), > >> > Div (q2 :: RegExp tok b') (f2 :: b' -> b)) -> > >> > Div (Plus q1 q2) (f1 +++ f2) > >> > divide t (Mult r1 r2) =3D case (empty r1, divide t r1, divide t r2) of > >> > (Nothing, Div q1 f1, _) -> Div (Mult q1 r2) (f1 *** id) > >> > (Just x1, Div q1 f1, Div q2 f2) -> > >> > Div (Plus (Mult q1 r2) q2) (either (f1 *** id) (((,) x1) . f2)) > >> > divide t (Star r) =3D case (divide t r) of > >> > Div q f -> Div (Mult q (Star r)) (\ (y, xs) -> (f y : xs)) > >> > >>Bureaucracy. > >> > >> > (***) :: (a -> b) -> (c -> d) -> (a, c) -> (b, d) > >> > (f *** g) (a, c) =3D (f a, g c) > >> > >> > (+++) :: (a -> b) -> (c -> d) -> Either a c -> Either b d > >> > (f +++ g) (Left a) =3D Left (f a) > >> > (f +++ g) (Right c) =3D Right (g c) > >> > >> > naughtE :: Empty -> x > >> > naughtE =3D undefined > >> > >>It's not the most efficient parser in the world (doing some algebraic=20 > >>simplification on the fly wouldn't hurt), but it shows the sort of stuff=20 > >>you can do. > >> > >>Have fun > >> > >>Conor > >>_______________________________________________ > >>Haskell-Cafe mailing list > >>Haskell-Cafe(a)haskell.org > >>http://www.haskell.org/mailman/listinfo/haskell-cafe > >>

2 1