February 2004 - Haskell

WS-FM 2004 Call For Participation
by Mario Bravetti 20 Jul '05

20 Jul '05

---------------------------------------------------------------------- We apologize if you receive multiple copies of this announcement. ---------------------------------------------------------------------- ====================================================================== 1st International Workshop on Web Services and Formal Methods (WS-FM 2004) February 23-24, 2004, Pisa, Italy Workshop affiliated to COORDINATION 2004, February 24-27, 2004 WS-FM 2004 homepage: http://www.cs.unibo.it/~lucchi/ws-fm04/ ====================================================================== - The technical program is available at: http://www.cs.unibo.it/~lucchi/ws-fm04/ - Information about registration, travel and accomodation can be found at the COORDINATION 2004 web site: http://www.di.unipi.it/Coordination2004/ If you intend to participate, we recommend you to register and book the hotel as soon as possible. The Coordination 2004 Organizing Committee informed us that hotels are going to be fully booked in short time.

1 1

CfP: SNPD'03 Workshop on High-Level Approaches to Parallel and Distributed Computing
by Clemens Grelck 08 Jul '04

08 Jul '04

Please apologize in case you receive multiple copies of this information. ========================================================================== CALL FOR PAPERS Workshop on High-Level Approaches to Parallel and Distributed Computing held in the context of the Fourth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD'03) October 16th - 18th, 2003 Luebeck, Germany http://www.isp.uni-luebeck.de/snpd03/Workshop/ws02/index.htm ========================================================================== Scope and Topics: ================== Today parallel and distributed computing systems are readily available and provide a continuously improving price/performance ratio. However, this technological breakthrough in hardware is not accompanied by similar progress in software technology. Parallel and distributed programming is still dominated by low-level techniques such as explicit message passing. This low level of abstraction makes programming these systems exceedingly difficult, time-consuming, and error-prone. Hence, parallel and distributed computing requires new programming models which liberate programmers from low-level concerns and increase programming productivity while maintaining reasonable trade-offs between level of abstraction and runtime performance. Topics of interest include, but are not limited to - methodologies for high-level parallel programming, - parallel programming languages, - high-level libraries for parallel computing, - compilers and runtime systems for parallel computing, - implementation aspects of high-level parallel programming environments, - compiler-based optimization and parallelization, - experience with high-level parallel programming environments, - support for debugging and performance analysis, - concurrent array programming, - programming concepts for the grid. This workshop provides a forum for researchers and practitioners interested in the design, implementation, and evaluation of high-level parallel programming concepts. It aims at creating some focus within the otherwise broad spectrum of the SNPD'03 conference. Workshop Chair and Organizer: ============================== Clemens Grelck University of Luebeck Institute of Software Technology and Programming Languages Seelandstr. 1A 23569 Luebeck, Germany E-Mail: grelck(a)isp.uni-luebeck.de Papers and Publication: ======================== Original, unpublished papers in English not exceeding 8 pages in ACIS double column format are solicited. For detailed formatting instructions see the SNPD'03 conference web site at http://www.isp.uni-luebeck.de/snpd03/index.htm Please send your papers as PDF documents by electronic mail directly to the workshop chair: grelck(a)isp.uni-luebeck.de Please indicate your paper submission by the subject SNPD03 WORKSHOP SUBMISSION Accepted papers will be published in the conference proceedings with ISBN. A selection of excellent papers presented at the conference including its workshops will be published in a special issue of the International Journal of Computer and Information Science. Important Deadlines: ===================== Full paper submission due: August, 30th Notification of acceptance: September, 10th Camera-ready papers due: September, 24th

1 3

Haddock, QuickCheck, and Functional Design by Contract
by Robert Will 22 Mar '04

22 Mar '04

> import QuickCheck Dear developers of QuickCheck and Haddock, Dear Haskell-Community, ((Summary: I'm trying to find notations for Design by Contract in Haskell which can be standardised to be used by tools like Haddock and QuickCheck. This will give Haskell programmers an order-of-magnitude gain in productivity, since it brings semantic abstraction into the programming language. See [1] and my earlier posts to this list [2].)) I consider it the most important advantage of Haddock, that it encourages the separation of module internal and external documentation (marked with -- | or -- ^). This is added value, even if a module user only reads the source, not the generated documentation. I consider it one of the most important advantanges of QuickCheck, that it allows the automatic verification of (formal) documentation, namely algebraic properties of functions. Yes, I think that that (well-written) QuickCheck properties are excellent documentation, much more worth than just type signatures (which I can look at in the interpreter). I consider it the essence of Design by Contract to have an explicit redundancy in the code, namely Pre- and Post-Conditions, Assertions, whose consistency with the rest of the code is automatically checked during run-time, making it a tight net in which bugs are caught. And what's more, this redundant view is more abstract than the original code, so that it makes for excellent documentation, which can never be out of date (due to the run-time checks). Both the principles "Only one document for code and documentation" and "Contracts have to be run-time checked" were already articulated in 1988 [3]. A standarised notation for contracts should therefore be part of any programming language. The following six points summarise a functional version of Design by Contract. Point 4 is still unclear, others can still change syntax. The rest is relatively straight- forward and we should make it a standard as soon as possible. 1. A notation for postconditions: No problem, use QuickCheck properties. > prop_sort_post xs = let xs' = sort xs > in is_sorted xs' && bag xs == bag xs' - Haddock can automatically include this "postcondition" in the documentation for function @sort@ (removing the prefix "prop_" and the suffix "_post" from the QuickCheck-Property). - For QuickCheck it is already in the right format. 2. A notation for specificative functions. That is, we document / specify a function by giving a more readable (but less efficient) version with the same semantics. For example, the best way to document exponentiation (besides the informal "@x ^ n@ is the @n@th power of @x@.") is the following code: > x ^ 0 = 1 > x ^ n = x * x^(n-1) Or the standard function @scanl@ is specified as > scanl f e = map (foldl f e) . inits > -- @inits@ see appendix. Both of those definitions are not the actual implementation (which is asymptotically faster in both cases), but they are perfectly suited for inclusion in the documentation and as raw material for QuickCheck. We can realise that by a simple notation: > scanl_spec f e = map (foldl f e) . inits Haddock would then publish the definition @scanl f e = ..@ (i.e. with the suffix "_spec" removed) in the documentation. QuickCheck would generate the testing property: prop_scanl_spec f e = scanl f e == scanl_spec f e The same can be done for functions with operator names, e.g. with "//" as suffix for the specification function and "\\" as prefix in "prop_"'s place: x \\^// n = x ^ n == x ^// n (We could also generate names, like "roof_spec" and "prop_roof_spec" for use in the code. The documentation, however, will only show the clear @x ^ n@.) 3. A notation to mark self-specifying functions. These are functions where the implementation is at the same time the simplest (still formal) specification. For example the function @square@ from the Haddock manual: square x = x * x -- || The double bar tells Haddock to export the complete function definition to the user documentation. Another example comes from DData: (<>) = append -- || Only syntactic sugar. Or: lookup k map | member k map = Just (find k map) -- || | otherwise = Nothing -- || -- | Perhaps implement more efficiently later. The documentation that contains those defintions does not reveal whether the functions are really implemented as given, or whether it's only a specificative functions according to point 2. However, since point 2 guarantees semantic equivalence through tests, users don't need to care. For many people self-specifying code seems to be opposed to design by contract, however, this is not at all the case. The modern view of Programming by Refinement (see, e.g. [5]) softens the frontier between specifications and implementations to allow practical compromises between readability and efficiency while at the same time avoiding negative redundancy between code and spec (i.e. simply duplicated information instead of a useful different view). Incidentally most of the Prelude functions are self- specifying in this way. The examples of point 2 are notable exceptions. 4. A notation for preconditions. For simple functions a Precondition can be calculated automatically from the Patterns: > head (x:xs) = x Gives the Precondition @xs /= []@ for @head xs@. This only needs some simple knowledge about @data@ and @newtype@ declarations. (We could also choose to leave it out, if it's too much work, for too few cases where it works. Then programmers would have to state all preconditions explicitly as shown next.) Presently I use the following coding style: > take n xs | not (n >= 9) = error "take.Precondition" The precondition can simply be extracted as <<the bracketed expression behind @not@ in a line containing the words @error@ and "Precondition">>. However it has the disadvantage that I can't simply disable run-time checking of the Precondition (as I could when using @assert@). Furthermore it is also rather ugly. Does anyone have a better idea? The use of Preconditions is expecially important: - Automatically checked on run-time (like @assert@). - Used in documentation. - Used by QuickCheck to create (==>) guards in the automatic @prop_foo_spec@ properties. 5. Default implementations of type class members are often a special case of specification functions: the overwriting provides the same semantics, more efficiently. (Occurs often in Abstract Data Structures, see [2].) A typical example is: > is_empty coll = size coll == 0 -- || We can use the double bar (or whatever we decide to standardise), to mark the function definition for export to the documentation. However, it is more difficult to create test properties which compare the two implementations of a function, since the default implementation is no more accessible after having been overwritten. The property generator will have to copy the default definition to a definition with name @is_empty_spec@ (for example) and can then generate the usual @prop_is_empty_spec@ (as in point 2). The copying of the function definition happens only for testing and is not seen in normal code or documentation. (The overwriting corresponds slightly to the contract refinement in object-oriented inheritance. See [3].) By the way, we can use -- || on a type class header, saying to export all it't default definitions to the documentation. (In my data structure library this is always the case. See, e.g., http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/AlgebraBasic.hs ) 6. Invariants are an important part of Design by Contract according to [3]. In Functional Programming it has been proven practical to check (and at the same time: document) data structure invariants in a smart constructor; the invariant resides only in this place (is not redundantly mentioned in the code) and is run-time checked on each creation of a data cell. This works with @assert@ and doesn't need QuickCheck properties. Also, such internal invariants are not relevant for the external documentation. (Otherwise we could documentation- export the definition of the smart constructor, using -- ||.) External Invariants are nothing else than algebraic properties of data structures. They can be documented using normal QuickCheck- Properties, and these can be documentation- exported via -- ||. As a consequence, invariants need no special notation. I only mention them her for methodological reasons. In order to keep the standard short, I suggest only to include this notations, the discrimination between internal and external comments (as in Haddock) and the discrimination of identifiers in comments (also editors can have hyperlinking and different colors.) Further markup concerns only the documentation generator and not other tools. Users of QuickCheck have reported an order-of-magnitude gain in productivity. That's because redundancy in form of checkable documentation comes very near to semantically automated software engineering. Together with proper documentation mechanisms, we can make such rendundant programming more literate, thus bringing an order-of-magnitude gain in productivity to whole programmer _teams_. Finally, I think, that the topic "Functional Programming and Design by Contract" is also a topic for a keynote lecture. Those who are in the relevant positions might about that. Similar applies to the authors of functional programming text books (and teachers, by the way). Or, and fans of program proving (hello LARCH and OBJ2) might want to statically check those contracts... so far, Robert [1] myself: "Modularity without Abstraction is no more than Syntactic Sugar" http://www.stud.tu-ilmenau.de/~robertw/eiffel/modularity_abstraction.txt [2] myself: "Posts on Functional Data Structures" http://www.mail-archive.com/haskell@haskell.org/msg13980.html http://www.mail-archive.com/haskell@haskell.org/msg13979.html [3] Bertrand Meyer: "Object-Oriented Software Construction", 1st edition, 1988 [4] Richard Bird: "Introduction to Functional Programming using Haskell", 2nd ed. [5] Eric Hehner: "A Practical Theory for Programming", 2nd ed., 2004 http://www.cs.toronto.edu/~hehner/aPToP/ > -- | List of initial segments (including []) of a list > -- in increasing order of size. > inits [] = [[]] > inits (x:xs) = [] : > map (x:) (inits xs) > > prop_inits_initial xs = forAll (elements $ inits xs) (\ ys -> > ys == take (length ys) xs ) > > prop_inits_increasing_length xs > = striclty_increasing $ map length $ inits xs > -- Also checks, that no segment occurs twice.

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

Announce: wxHaskell 0.6
by Daan Leijen 03 Mar '04

03 Mar '04

Announcement: wxHaskell version 0.6 ---------------------------------------------------------------------- <http://wxhaskell.sourceforge.net> This new release fixes many bugs, adds basic support for MDI applications and compiles with the latest CVS snapshots of wxWidgets. For now, only an installer for windows is provided. All the best, Daan. News (see the wxHaskell website for more information): - wxWindows is now called wxWidgets! (and yes, it is due to Microsoft :-) - wxWidgets runs on mobile phones (Symbian OS). - Borland Builder-X will ship with wxWidgets as its windowing toolkit. Updates: - Support for MDI applications - Combobox now catches enter keys through "on command" - Many list-like controls now react on "on select" instead of "on command" - Attribute "enable" is now called "enabled" - Resize bugs are fixed, new "dynamic" layout combinator added - Repaint bugs are fixed, new "fullRepaintOnResize" attribute added. - Basic support for unicode fonts (see the screenshots page) Tested on: - windowsXP and windows 2000 with ghc 6.2, 6.0.1, and wxMSW 2.4.2 - MacOS X 10.3 (Panther) with ghc 6.2 and wxMAC 2.5.1 (20 feb 2004) - MacOS X 10.2 (Jaguar) with ghc 6.0.1 and wxMAC 2.4.2 - Red Hat Linux 10 (Fedora) with ghc 6.2 - FreeBSD, with ghc 5.05.xxxx and wxGTK 2.4.1 - and wxHaskell has been known to run on other platforms :-) ---------------------------------------------------------------------- wxHaskell is a portable GUI library for Haskell. The goal of the project is to provide an industrial strength portable GUI library, but without the burden of developing (and maintaining) one ourselves. wxHaskell is therefore build on top of wxWidgets -- a comprehensive C++ library that is portable across all major GUI platforms; including GTK, Windows, X11, and MacOS X. Furthermore, it is a mature library (in development since 1992) that supports a wide range of widgets with native look-and-feel, and it has a very active community (ranked among the top 25 most active projects on sourceforge). Since most of the interface is automatically generated from the wxEiffel binding, the current release of wxHaskell already supports about 75% of the wxWindows functionality -- about 2900 methods in 500 classes with 1400 constant definitions. wxHaskell has been build with GHC 6.x on Windows, MacOS X and Unix systems with GTK. A binary distribution is available for Windows and MacOS X. And even if you don't intend to write GUI's yourself, it will be fun to check out the screenshots at <http://wxhaskell.sourceforge.net>. All the best, Daan Leijen.

4 7

Re: [Haskell] performance tuning Data.FiniteMap
by JP Bernardy 03 Mar '04

03 Mar '04

> I believe FiniteMap works by representing the data > in binary trees. It is therefore O(log2(n)) to > read and update. > > However, if my application reads many more times > than it writes, then perhaps I can get a > substantial performance boost by increasing the > branch factor on the tree. For example, if each > node was an array of 256 elements, reads would be > O(log256(n)), a 128x improvement! Not quite. In fact, O(log256(n)) is equivalent to O(log2(n)), because there is only a constant factor between the two. That's why basis of logarithms are usually omitted in O() expressions. Besides, the ratio between log256(n) and log2(n) is more like 8 than 128. (And you'd loose this factor in searching the right subtree, as Ketil pointed out) Tuning Data.FiniteMap probably is not what you want. I don't know, but you can have a look at Data.Hashtable. Just my 2 cents, JP. __________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools

6 9

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

28 Feb '04

> The idea that I've been throwing around is to be able to define a > separate namespace for each type; a function can either belong in a > "global" (default) namespace, or belong in a particular type's > namespace. So, in the above example, instead of writing "addToFM fm > ...", we could instead associate an 'add' function with the FiniteMap > type, so we could write "fm.add ..." instead. Provided that fm's type > is monomorphic, it should be possible to call the 'correct' add > function; if we defined another 'add' function that's associated with Remember, too, that in OO languages the type of 'fm' is usually declared, in advance, by the programmer. In Haskell it isn't. That makes it much harder to figure out which 'add' function is going to be used. Which 'add' function is chosen depends on type type of 'fm'. But the add function that is chosen in turn influences the type of the other arguments. For example, in the call (fm.add foo), the type of 'foo' is influenced by the choice of 'add'. But the type of 'foo' might (by the magic of type inference) affect the type of 'fm'.... In Haskell today, you can at least tell what value is bound to each identifier in the program, *without* first doing type checking. And the binding story, all by itself, is somewhat complicated. The typing story is also (very) complicated. Winding the two into a single indissoluble whole would make it far more complicated still. My nose tells me that this way lies madness. But I've been wrong before. Simon

5 4

Re: Data.Set whishes
by Wolfgang Jeltsch 28 Feb '04

28 Feb '04

Am Montag, 16. Februar 2004 10:05 schrieb Ketil Malde: > Wolfgang Jeltsch <wolfgang(a)jeltsch.net> writes: > > * subsetOf :: Ord element => Set element -> Set element -> Bool > > (Isn't "isSubsetOf" a better name?) So is "isElementOf". I just said "subsetOf" to be consistent with "elementOf". Well, the naming in the Data.* modules should generally undergo some changes. > Would > > x `isSubsetOf` y = x `union` y == y > > do, or did you want something more efficient? It's unefficient if, e.g., the x sets are always very small but so are union, intersect etc. I think, at first a complexity of O(|x| + |y|) would be acceptable so that your definition would be fine. Maybe, the implementation of union, intersect etc. should be changed so that the complexity is more like O(min(|x|,|y|)). > -kzm Wolfgang

19 31

Regular Patterns (RE: [Haskell] regular expression syntax)
by Niklas Broberg 27 Feb '04

27 Feb '04

>Subject: [Haskell] regular expression syntax - perl ain't got nothin on >haskell Agreed, Perl certainly ain't got nothing on Haskell, but we could go even further than just imitating (although better than the original) Perl functionality. =) Hence: As a spin-off of another project [1], we found ourselves in need of a nice way of expressing regular expression matching in Haskell, and not only for strings. We came up with the idea of HaRP: Haskell Regular Patterns. We have implemented this as a pre-processor to ordinary Haskell and it works quite well. However it is something we are still working on, and if it hadn't been for this discussion on the list we would probably have waited a few weeks more before presenting it, but here goes: Simple pattern matching on concrete, fully specified lists can be done in Haskell as so: foo [Foo, Bar, Baz] = ... We propose an extension of this to regular pattern matching, example: foo [/ Foo Bar* Baz /] = ... The intuition of the above is that we get a match for any list that starts with a Foo, ends with a Baz, and has zero or more Bar in between. Regular patterns that can be used are: * - match zero or more + - match one or more ? - match zero or one a | b - match a or b (/ a b /) - match the sequence of a, then b (this is also implicit in the top level [/ ... /]). Applying the regular expressions on patterns gives some extra nice features. One is that the regular patterns are "type safe", i.e. they are not encoded in strings. Another is that identifiers can be named and bound inside regular patterns, examples: foo [/ _* a /] = ... => a is bound to the last element of the list foo [/ a@(/ _ _ /) _* /] = ... => a is bound to the list containing the first two elements foo [/ (/ a _ /)* /] = ... => a is bound to the list of the first, third, fifth etc elements of a list of even length Note that since we introduce bindings of identifiers inside what we call numerating patterns, i.e. patterns that imply an uncertain number of matches, identifiers are automatically bound to lists inside such patterns. We also introduce an explicit list-binding operator, @:, for accumulating items in lists as so: foo [/ (_ a@:(/ _ _ /))* /] = ... => a is bound to a list of lists (exactly what the elements will be is left as an exercise to the reader ;) The types of sub-patterns are as follows (a :: a, b :: b): a* => [a] a+ => [a] a? => Maybe a (/ ... /) => [e], where e is the type of the elements in the list matched, regardless of sub-patterns ( a | b ) => Either a b As more complete example using all the presented features: foo [/ _ a@1 b c@3* 4+ d@5? e@(/ f@:6 g /)* h@( 8 | (/ 9 i /) ) /] = (a,b,c,d,e,f,g,h,i) Assuming all the numerical literals are of type Int, foo will have the following type: foo :: [Int] -> (Int, Int, [Int], Maybe Int, [[Int]], [Int], [Int], Either Int [Int], [Int]) Examples of applying foo to some lists: ?> foo [0,1,2,3,4,5,6,7,8] (1, 2, [3], Just 5, [[6,7]], [6], [7], Left 8, []) ?> foo [0,1,2,3,3,3,4,6,0,6,1,6,2,9,10] (1,2,[3,3,3], Nothing, [[6,0],[6,1],[6,2]], [6,6,6], [0,1,2], Right [9,10], [10]) Discussion of each variable in detail: a :: Int - a binds to a single element at top level (top level meaning it is bound outside any numerating pattern). b :: Int - b binds to a single element at top level. c :: [Int] - c is bound to a zero-or-many pattern, and it will contain all the matches of the sub-pattern, in this case all matches of 3. d :: Maybe Int - d is bound to a zero-or-one pattern, and it will be Nothing in case of zero matches, and Just the match to the sub-pattern in case of a match, in this case 5. e :: [[Int]] - e is bound to a zero-or-more pattern, and will thus contain a list of all the matches of the sub-pattern. In this case the sub-pattern is a sequence, which has a list type, so the type of e is a list of lists. f :: [Int] - f is bound using the list-binding operator @:, so its type will always be a list of the type of the sub-pattern, regardless of the context it appears in. It will contain all matches of the sub-pattern (Note that a normal bind using @ would have been illegal here). At top level (and in ordinary pattern matching), the pattern foo is equivalent to foo@_, but inside numerating patterns the pattern foo is equivalent to foo@:_. (see discussion below) g :: [Int] - g is equivalent to g@:_ as mentioned above, so the same will hold for g as for f. h :: Either Int [Int] - h is bound to a choice pattern (or union pattern if you prefer), so it will be bound to the match of one of the two sub-patterns, annotated with Left or Right. In this case the left sub-pattern matches a single element of type Int, whereas the right sub-pattern matches a sequence of type [Int]. i :: [Int] - Since the choice pattern is numerating (each of the sub-patterns are matched zero or one times), i is equivalent to i@:_. For completeness, another example to show how sequences work: bar :: [Int] -> [Int] bar [/ 0 a@(/ 1* 2 (3|4) (/ 5 6 /) 7? /) /] = a In this case a will have the type [Int], since a sequence will always have the type [e] where e is the type of the elements of the list to match. So in this example, ?> bar [0,2,3,5,6] [2,3,5,6] ?> bar [0,1,1,1,2,4,5,6,7] [1,1,1,2,4,5,6,7] Hopefully that's enough examples, it should be fairly clear how it all works. =) Regarding @ vs @:, it would be fully possible to implement this just using @ and change its behavior depending on the context it appears in, much like we do with identifiers bound without using the explicit @ operator. We feel that doing so could lead to (even more) confusion regarding how variables are bound, and have therefore chosen to introduce the extra @: operator to make this differing behavior explicit. That identifiers bound without a @ or @: have differing semantics depending on context is unfortunate but unavoidable, and we feel that the added confusion is minor in this case. As we said at the beginning we have implemented this as a preprocessor to ordinary Haskell, but it still needs some more alpha-testing before we release it... we need to catch the big fish first. There are a number of open issues still, one is the choice of delimeter token. We have chosen to delimit patterns with just a whitespace, but using a comma might be better. The motivation for the current choice is that [/ a, b*, c /] lends the feeling that each pattern is an element of sorts, when in fact each pattern may represent any number of elements. Any input on this? Another open issue is greedy vs. non-greedy matching of * and +. The current implementation is greedy, but some voices were raised earlier on this list that non-greedy matching would be better as default. We envision a system where you can choose behavior by adding "flags" to the pattern, i.e. [g/ .... /] might indicate a greedy match etc. Strings are a special syntactic case of a list, and we are planning a special case of regular patterns for it, for instance [s/ "Hello " a* /] would be equal to [/ 'H' 'e' 'l' 'l' 'o' ' ' a* /], but this is not yet implemented. Of course, unfortunately, there is also a downside. Our preprocessor is implemented by translating regular patterns into code in a parser monad. Due to the way that matching is done, matching will always be "strict" in the sense that if you apply the function foo [/ a* /] = a to an infinite list, the call will loop forever. At this point we see no reasonable way around this, there may be some special cases we can catch but we see no overall solution to the problem. Another drawback, at least in our implementation, is efficiency. Using an external C engine for matching regular expression would far outperform our system, no matter how efficient we make our backend. Thus this is not intended to replace any existing functionality, rather we envision it as a very high-level interface to matching regular expressions in the spirit of String being [Char], where Text.Regex can be compared to using PackedString for critical programs. Perhaps by integrating regular patterns directly into a compiler like ghc we could use ugly low-level behind-the-scenes tricks for doing the actual matching in an external engine, thus greatly increasing efficiency. Any thoughts? =) We will supply the preprocessor for public scrutiny some time next week, we just need to do some more alpha-testing first... Comment away! regards, Niklas Broberg, d00nibro[at]dtek.chalmers.se Andreas Farre, d00farre[at]dtek.chalmers.se Chalmers University of Technology [1] Feel free to also visit the project that lead to this spin-off, Haskell Server Pages http://www.dtek.chalmers.se/~d00nibro/hsp/ _________________________________________________________________ Take off on a romantic weekend or a family adventure to these great U.S. locations. http://special.msn.com/local/hotdestinations.armx

2 1

RE: [Haskell] Per-type function namespaces (was: Data.Set whishes)
by Graham Klyne 27 Feb '04

27 Feb '04

At 09:28 27/02/04 +0000, Simon Peyton-Jones wrote: >Which 'add' function is chosen depends on type type of 'fm'. But the >add function that is chosen in turn influences the type of the other >arguments. For example, in the call (fm.add foo), the type of 'foo' is >influenced by the choice of 'add'. But the type of 'foo' might (by the >magic of type inference) affect the type of 'fm'.... > >In Haskell today, you can at least tell what value is bound to each >identifier in the program, *without* first doing type checking. [...] Nicely explained. Until this, I had a feeling that the proposed type-directed value-binding resolution was potentially problematic for Haskell, but couldn't say why. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0