March 2004 - Haskell - Haskell.org

Re: [Haskell-cafe] matching constructors
by Brandon Michael Moore 09 Mar '04

09 Mar '04

I think the generics approach really is overkill here, but it's nice to know the generics library. For option processing Tomasz Ziolonka described a nice technique in the post I refered to. You can find the post in the archives at http://www.haskell.org//pipermail/haskell/2004-January/013412.html The big example at the end of his post seems to have exactly the otpion structure you want, with input, output, a verbose flag, and a (composable) selection of filters to use. The basic idea is to make a record containing the options in their most useful form and make each options descriptor (I assume you are using (System.Console.)GetOpt here) return a function that transforms an option record to reflect that option. Now to handle the list of values you get back you just apply each transformer in turn to the default options. It somewhat resmbles building up option values in a collection of mutable variables, although of course values are rather more flexible in Haskell than most other languages, and the "state" is encapsulated and well behaved. Brandon

1 0

Final CFP: GPCE'04 (electronic submission open)
by Eelco Visser 08 Mar '04

08 Mar '04

FINAL CALL FOR PAPERS ---------------------------------------------------------------------- Third International Conference on Generative Programming and Component Engineering (GPCE'04) Vancouver, October 24-28, 2004 co-located with OOPSLA 2004 and ISMM 2004 http://gpce04.gpce.org ---------------------------------------------------------------------- ------------------------------------ Electronic submission is now open ------------------------------------ http://gpce.program-transformation.org ------------------------------------ Important Dates ------------------------------------ Pre-submission: March 12, 2004 Submission: March 19, 2004 ------------------------------------ Page limit is 20 pages LNCS format ------------------------------------ ------------------------------------ Scope ------------------------------------ Generative and component approaches have the potential to revolutionize software development in a similar way as automation and components revolutionized manufacturing. Generative Programming (developing programs that synthesize other programs), Component Engineering (raising the level of modularization and analysis in application design), and Domain-Specific Languages (elevating program specifications to compact domain-specific notations that are easier to write and maintain) are key technologies for automating program development. GPCE arose as a joint conference, merging the prior conference on Generative and Component-Based Software Engineering (GCSE) and the Workshop on Semantics, Applications, and Implementation of Program Generation (SAIG). The goal of GPCE is to provide a meeting place for researchers and practitioners interested in cutting edge approaches to software development. We aim to foster further cross-fertilization between the software engineering research community on the one hand, and the programming languages community on the other, in addition to supporting the original research goals of both the GCSE and the SAIG communities. We seek papers both in software engineering and in programming languages, and especially those that bridge the gap and are accessible to both communities at the same time. --- more information at http://gpce04.gpce.org

1 0

Parsing Typed Data from a String
by Simon D. Foster 08 Mar '04

08 Mar '04

I am currently trying to implement a method of allowing arbitrary record syntax data-types to be converted to and from an XML representation of them using the Read and Show class; i.e. simply derive either Show and then parse the given String to extract the name/value pairs which can then be converted to XML, or using the XML generate a representation of the data entity (e.g. "Person{name=\"Fred Smith\", age=47}") and read this back into an actual value. However I have one small problem; the order of the incoming parameters of the XML data-type representations is not guaranteed, but according to Haskell 98 report; "If the constructor is defined using record syntax...the fields must be given in the same order as the original declaration." So my question is, is there any method in GHC which allows you to extract the order of the constructors in a type or to parse a type-representation in such a way that the order of the records doesn't matter (I am looking for ease/simplicity of use)? Or do I just tell them to put the records in alphabetical order? -Si. (Please CC replies to me). -- Simon D. Foster <u1sf(a)dcs.shef.ac.uk> Sheffield University

3 2

[Haskell] regular expression syntax - perl ain't got nothin on haskell
by John Meacham 08 Mar '04

08 Mar '04

Inspired by an idea by Andrew Pang and an old project of mine, I decided to fill out a reusable regular expression library which is similar to Perl's, but much more expressive. It provides regular and monadic versions, a very overloaded and useful interface, as well as extensibility. although currently the only instance is based on Text.Regex, it generalizes to matching lists of arbitrary type, not just strings, and also leaves the door open for compile-time checked and optimized regular expressions via template Haskell. so, does this seem interesting? I am really enjoying the =~ syntax already in projects, and the monadic version is great for concise ad-hoc parsers. my next steps are to 1. finish my template Haskell regex compiler, not only to optimize at compile time, but allow matching of arbitrary types. not just strings. (perhaps reusing some code from the old Regular Expressions in Haskell project) 2. make a pcre binding. hook it in. and possible ideas for the future are * remove restriction to lists, so tree-like structures can be matched. perhaps grabbing default value from Monoid. The only reason I don't have this now is I didn't want to enable overlapping-instances, things are already complicated enough :) * add further optimized versions of match*, perhaps split up class for when there is no clear concept of the preceding part and postceeding parts around a match.. * develop a substitution syntax * implement pcre in pure Haskell although, even now, it seems quite useful. new versions will appear at http://repetae.net/john/computer/haskell/RegexSyntax.hs plus, this is something to brag about to Perl people, they can only do things differently based on scalar vs. list context. our =~ does 10 different things typesafely and probably some more I missed :) {-# OPTIONS -fglasgow-exts #-} module RegexSyntax(RegexLike(..), RegexLikeImp(..), RegexContext(..), (!~)) where import Array import Text.Regex import Maybe {- basic usage: > string =~ "regular expression" returns different things depending on context type - what it evaluates to --------------------------- Int - number of times the regular expression matches String - matching portion of string (String,String,String) - (text before match, matching text, text after match) [Either String String] - list of matching and nonmatching strings, if concated, the original string results. Left = notmatching, Right = matching. Bool - whether the string matches () - always returns () (useful in monad context, see below) [String] - list of matches Array Int String - list of substring matches for first match (String, Array Int String) - full matching text and substring matches [(String, Array Int String)] - all matches, full match plus substrings [Array Int String] - all substrings from all matches also, there is the monadic version (=~~) which always behaves exactly the same as (=~) except when the match fails, instead of returning a default value, the monad fails. s !~ re = not (s =~ re) for convinience regular expressions: these may be strings, which are interpreted as regular expressions, or Regex's from the Text.Regex module. or any other instance of the RegexLike class. when using strings, you may prefix the regex by "i/" for a case-insensitive match and "s/" to treat the string as a single line. (or both as "si/") A leading "/" is ignored, other than these cases "/" is not special. advanced features: not just strings can be matched, but rather lists of anything a matcher is defined for. RegexLikeImp data class can be used for in-place code generated by template haskell for compile-time checked regular expresions -} class RegexLike r a | r -> a where matchOnce :: r -> [a] -> Maybe ([a],[a],[a],Array Int [a]) matchTest :: r -> [a] -> Bool matchAll :: r -> [a] -> [Either [a] ([a],Array Int [a])] matchShow :: r -> String -- for error messages matchTest r xs = isJust (matchOnce r xs) matchAll r xs = case matchOnce r xs of Nothing -> pn xs [] Just (p,m,rest,as) -> pn p (Right (m,as):matchAll r rest) where pn x = if null x then id else (Left x:) matchShow _ = "Unknown" instance RegexLike Regex Char where matchOnce re xs = fmap f (matchRegexAll re xs) where f (x,y,z,ls) = (x,y,z,listArray (1,length ls) ls) matchShow _ = "Regex" instance RegexLike String Char where matchOnce re xs = fmap f (matchRegexAll (mr re) xs) where f (x,y,z,ls) = (x,y,z,listArray (1,length ls) ls) mr ('i':'/':re) = mkRegexWithOpts re True False mr ('s':'/':re) = mkRegexWithOpts re False True mr ('i':'s':'/':re) = mkRegexWithOpts re False False mr ('s':'i':'/':re) = mkRegexWithOpts re False False mr ('/':re) = mkRegex re mr (re) = mkRegex re matchShow re = re class RegexContext x a where (=~) :: RegexLike r x => [x] -> r -> a (=~~) :: (Monad m, RegexLike r x) => [x] -> r -> m a -- s =~~ re = return (s =~~ re) not default because probably not what you want s !~ re = not (s =~ re) regexFailed re = fail $ "regex failed to match: " ++ matchShow re instance RegexContext x Int where s =~ re = let xs = matchAll re s in length [x | Right x <- xs] s =~~ re = case (s =~ re) of 0 -> regexFailed re xs -> return $ xs instance RegexContext x ([x],[x],[x]) where s =~ re = case matchOnce re s of Nothing -> (s,[],[]) Just (x,y,z,_) -> (x,y,z) s =~~ re = case matchOnce re s of Nothing -> regexFailed re Just (x,y,z,_) -> return (x,y,z) instance RegexContext x [Either [x] [x]] where s =~ re = map f $ matchAll re s where f (Left s) = Left s f (Right (x,_)) = Right x s =~~ re = case (s =~ re) of [Left _] -> regexFailed re xs -> return $ xs instance RegexContext x [x] where s =~ re = case matchOnce re s of Nothing -> [] `asTypeOf` s Just (_,s,_,_) -> s s =~~ re = case matchOnce re s of Nothing -> regexFailed re Just (_,s,_,_) -> return s -- useful in non-monad context instance RegexContext x Bool where s =~ re = matchTest re s s =~~ re = case s =~ re of False -> regexFailed re True -> return True -- useful in monad context instance RegexContext x () where s =~ re = () s =~~ re = case s =~ re of False -> regexFailed re True -> return () instance RegexContext x [[x]] where s =~ re = [x | Right (x,_) <- matchAll re s] s =~~ re = case (s =~ re) of [] -> regexFailed re xs -> return xs instance RegexContext x [([x],Array Int [x])] where s =~ re = [x | Right x <- matchAll re s] s =~~ re = case (s =~ re) of [] -> regexFailed re xs -> return xs instance RegexContext x [Array Int [x]] where s =~ re = [x | Right (_,x) <- matchAll re s] s =~~ re = case (s =~ re) of [] -> regexFailed re xs -> return xs instance RegexContext x (Array Int [x]) where s =~ re = case matchOnce re s of Nothing -> listArray (1,0) [] Just (_,_,_,z) -> z s =~~ re = case matchOnce re s of Nothing -> regexFailed re Just (_,_,_,z) -> return z -- this is used for template haskell to generate compile-time parsed regular -- expressions data RegexLikeImp a = RegexLikeImp { reImpMatchOnce :: [a] -> Maybe ([a],[a],[a],Array Int [a]), reImpMatchTest :: [a] -> Bool, reImpMatchAll :: [a] -> [Either [a] ([a],Array Int [a])], reImpMatchShow :: String -- for error messages } instance RegexLike (RegexLikeImp a) a where matchOnce = reImpMatchOnce matchTest = reImpMatchTest matchAll = reImpMatchAll matchShow = reImpMatchShow -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john(a)foo.net --------------------------------------------------------------------------

8 12

GHC EXE Windows
by Stenio 08 Mar '04

08 Mar '04

3 2

RE: [Haskell] Per-type function namespaces (was: Data.Set whishes)
by Simon Peyton-Jones 05 Mar '04

05 Mar '04

| detail, of course ;). What I'm secretly hoping is that the | GHC/hugs/HBC people will see what I'm trying to achieve, tell me I'm | totally nuts, and then suggest an alternative, much simpler approach | which gives us exactly the same goal ... As I implied earlier, I am thus far unconvinced that the complexity cost justifies the benefit. Let me suggest two simpler alternatives. Alternative 1 ~~~~~~~~ Given import FiniteMap( FM, add {- :: FM a b -> a -> b -> FM a b -} ) and fm :: FM Int Bool, you want fm.add x y to mean the same as add fm x y (but in addition allow lots of unrelated 'add' functions) My objection is that the type of 'fm' is a matter of inference, whereas in Java it'd be a matter of explicit declaration. But you could adapt your story to be more explicit, thus FM.add fm x y The qualifier here is the *type* not the *module*. (Let's assume they share a name space for now.) This would work for record selectors too: data T = T { x::Int, y::Int } data S = S { x::Int, y::Int } Now f p q = T.x p + S.y q I guess the rule is that you can qualify a function by the name of the outermost type constructor of its first argument. I would restrict this only to functions with explicitly-declared types, so that there's no interaction with inference. Alternative 2 ~~~~~~~~ If the big bug-bear is record selectors, let's focus on them exclusively. I now think that ML got it right. ML records are simply labelled tuples. So just as (Bool,Int) is an anonymous type, so is {x::Bool, y::Int}. Indeed (Bool,Int) is just shorthand for {#1::Bool, #2::Int}. In Haskell, a function with a tuple argument takes exactly that tuple: f :: (Bool,Int) -> Bool f (x,y) = x Here, f cannot take a 3-tuple or a 89-tuple. In ML it's the same with records (I'm not getting the ML syntax right, but you'll get the idea): f :: {x::Bool, y::Int} -> Bool f r = r.x Here f cannot take a record of shape other than {x::Bool,y::Int}. You are allowed to write f {x, ...} = x but you must then explain f's argument type separately. For example you can write f :: {x::Bool, p::String, q::Bool} -> Bool f {x, ...} = x So there is no sub-typing, no row polymorphism, no attempt to give f r = r.x a fancy type that makes f applicable to any record with an x field. On the other hand, there is also no problem with many records having the same field name either, which is the problem we started with. There are no implicitly-defined record selectors either: you have to use pattern matching for that. My personal view is this: we should have adopted the ML view of records. It solves the immediate problem, and no more elaborate scheme seems sufficiently "right" to be declared the winner. Alas, like all other proposals, it's not backward compatible, and hence not likely to fly. Simon

5 4

RE: [Haskell] Per-type function namespaces (was: Data.Set whishes)
by Simon Peyton-Jones 05 Mar '04

05 Mar '04

| From: Ross Paterson [mailto:ross@soi.city.ac.uk] | | On Thu, Mar 04, 2004 at 09:21:23AM -0000, Simon Peyton-Jones wrote: | > My personal view is this: we should have adopted the ML view of records. | > It solves the immediate problem, and no more elaborate scheme seems | > sufficiently "right" to be declared the winner. Alas, like all other | > proposals, it's not backward compatible, and hence not likely to fly. | | About a year ago, you were toying with a simple polymorphic system with | just "has" predicates. If these were automatically derived, it seems | you'd get something quite close to backward compatible, except for the | pesky extra lifting in record types, and not being able to omit fields | when constructing the record. (And update might not statically check | that all fields belong to the same constructor, for the simple version | of the type system.) Is that just too clunky? It's possible, but I don't know. Speaking for myself, I've rather lost motivation on the records front, because the design space does not seem to have a clear optimum point. Adding has predicates in full glory seems overkill to get re-use of labels. Ah, but they also give you polymorphic record operations! Yes, but so do other versions, with different and rather subtle technical tradeoffs. That's why I've backed up to something extremely simple: either (a) disambiguate record labels by qualifying with the type constructor or (b) go the ML route. None of this is to discourage people from experimenting with variants -- quite the reverse. That's how we may find out what a good system is. Simon

1 0

[Haskell] Final call for papers, WRS'04, submission deadline (firm) March 17
by Sergio Antoy 04 Mar '04

04 Mar '04

=============================================================== Final call for paper, WRS'04, firm deadline March 17, 2004. We apologize for multiple copies of this announcement. =============================================================== ******************************** * * * WRS'04 Call for Papers * * * ******************************** http://www-i2.informatik.rwth-aachen.de/WRS04/ The Fourth International Workshop on Reduction Strategies in Rewriting and Programming (WRS'04) will be held on June, 2, 2003, in Aachen, Germany, as a part of the Federated Conference on Rewriting, Deduction, and Programming (RDP'04). IMPORTANT DATES: March 17, 2004 Deadline for electronic submission of papers April 14, 2004 Notification of acceptance of papers May 2, 2004 Deadline for final versions of accepted papers June 2, 2004 Workshop TOPICS include, but are not restricted to: * theoretical foundations for the definition and semantic description of reduction strategies * strategies in different frameworks (term rewriting, graph rewriting, infinitary rewriting, lambda calculi, higher order rewriting, conditional rewriting, rewriting with built-ins, narrowing, constraint solving, etc.) and their application in (equational, functional, functional-logic) programming (languages) * properties of reduction strategies / computations under strategies (e.g., completeness, computability, decidability, complexity, optimality, (hyper-)normalization, cofinality, fairness, perpetuality, context-freeness, neededness, laziness, eagerness, strictness) * interrelations, combinations and applications of reduction under different strategies (e.g., evaluation mechanisms in programming languages, equivalence conditions for fundamental properties like termination and confluence, applications in modularity analysis, connections between strategies of different frameworks, etc.) * program analysis and other semantics-based optimization techniques dealing with reduction strategies * rewrite systems / tools / implementations with flexible / programmable strategies as essential concept / ingredient * specification of reduction strategies in (real) languages * tutorials and systems related to evaluation strategies INVITED TALKS will be given by: * Olivier Danvy (University of Aarhus, Denmark), Normalization by Evaluation * Jan Willem Klop (Vrije Universiteit Amsterdam, The Netherlands), Reduction Cycles PROGRAM COMMITTEE: Sergio Antoy Portland (USA) (co-chair) Roberto Di Cosmo Paris VII (France) Juergen Giesl Aachen (Germany) Bernhard Gramlich Wien (Austria) Salvador Lucas Valencia (Spain) Aart Middeldorp Innsbruck (Austria) Jaco van de Pol Amsterdam (The Netherlands) Pierre Rety Orleans (France) Amr Sabry Bloomington (USA) Yoshihito Toyama Sendai (Japan) (co-chair) SUBMISSIONS: We solicit papers on all aspects of reduction strategies in rewriting and programming. Submissions should describe unpublished work, except for survey papers which are explicitly welcome, too. Submissions should not exceed 10 pages (however, survey papers may be longer) and be sent in PostScript or PDF format to the PC co-chairs at wrs04(a)redstar.cs.pdx.edu by March 17, 2004. The use of the style file available from the RDP workshop style page is encouraged. The call-for papers is also available in PDF format. Submissions should include the title, authors' names, affiliations, addresses, and e-mail. Selection of papers by the PC will be based on originality, significance, and correctness. Final versions will be due by May 2, 2004. PUBLICATION: Accepted papers will be included in the preliminary workshop proceedings that will be available at the workshop. The final workshop proceedings will be published in Elsevier's Electronic Notes in Theoretical Computer Science (ENTCS) series. For further questions please contact the program co-chairs: Sergio Antoy and Yoshihito Toyama at wrs04(a)redstar.cs.pdx.edu.

1 0

natural numbers
by Iavor S. Diatchki 04 Mar '04

04 Mar '04

hello, looking through the documentation for Data.Word I run into the follwoing comment: "it would be very natural to add a type Natural providing an unbounded size unsigned integer, just as Integer provides unbounded size signed integers. We do not do that yet since there is no demand for it." if that is not too much work could we have that in the library? i think it would be very useful. (i am trying to generate demand :-) it would also be useful to have finite natural numbers, ala C's "unsigned int". -iavor -- ================================================== | Iavor S. Diatchki, Ph.D. student | | Department of Computer Science and Engineering | | School of OGI at OHSU | | http://www.cse.ogi.edu/~diatchki | ==================================================

3 2

RE: [Haskell] Per-type function namespaces (was: Data.Set whishes)
by Simon Peyton-Jones 04 Mar '04

04 Mar '04

| So there is no sub-typing, no row polymorphism, no attempt to give | f r = r.x | a fancy type that makes f applicable to any record with an x field. | | On the other hand, there is also no problem with many records having the | same field name either, which is the problem we started with. There are | no implicitly-defined record selectors either: you have to use pattern | matching for that. Andreas says: | Actually, #l is just syntactic sugar for (\{l=x,...}->x), which implies | that you might need type annotations. Yes I was wrong to say that there are no implicitly-defined record selectors; (#l r) is exactly that. Syntactically I'd prefer (r.l); but regardless, it's a syntactic construct distinct from function application, which must be monomorphic. Yes, that's a kind of interaction between binding and type system (of the kind I objected to) but a very weak and well-behaved kind of interaction. Simon

2 1