July 2004 - Haskell - Haskell.org

Any way to change state type in a monad?
by Ben.Yu＠combined.com 13 Jul '04

13 Jul '04

Hi, I'm trying to implement some rule combinators. I'm hoping my combinators can change the state type implicitly passed around. Basically, a rule should be something like: newtype Rule m u u' = ... where it takes an input u and returns type u' as the result. m represents an inner monad. For the supported operations, I'd like to bind my rules with compatible output and input types; `mplus` rules with same input and output types; 'try' a rule without changing state in m; tell if a rule succeeded or failed and take action accordingly. For the latter two, it has been pretty tricky to me. Looks like many monads don't support such functionality. It does not seem like possible to do this in a monad because Monad is for type constructors with only one parameter while Rule m u u' and Rule m u' u'' obviously cannot be in the same monad type. So, is this design inherently flawed or there's just no such implementation yet? Thanks. Ben. This message is intended only for the addressee and may contain information that is confidential or privileged. Unauthorized use is strictly prohibited and may be unlawful. If you are not the intended recipient, or the person responsible for delivering to the intended recipient, you should not read, copy, disclose or otherwise use this message, except for the purpose of delivery to the addressee. If you have received this email in error, please delete and advise us immediately.

2 1

Re: [Haskell] for large x, log (x::Integer) :: Double
by Edmund GRIMLEY EVANS 13 Jul '04

13 Jul '04

Dylan Thurston: > For those who aren't aware: working with logs base 2 internally will > be very much faster than logs base 10, since the numbers are stored > internally in a base-2 representation. (Note that 'show' converts to > base 10, which involves a large number of divisions in the easy > algorithm.) Does Haskell provide any means of determining the number of binary digits in an Integer other than by repeated division? In the absence of an appropriate built-in or library function it may be that the fastest way is to use (length (show x)), multiply by some fiddle factor, add some fiddle term to get n, then check whether x < 2 ** n. Could "log2 :: Integer -> Integer" be added to some wish list?

3 4

Re: [Haskell] type class does not compile
by Graham Klyne 13 Jul '04

13 Jul '04

At 19:24 12/07/04 -0500, Ben.Yu(a)combined.com wrote: >Hi, >please bear with me if my question turns out to be a stupid mistake. It has >taken me hours to figure this out. > >class Rule r u u' m where > apply :: r -> u -> m u' > >data And = And > >data Bin a b o = Bin a b o > >instance (Monad m, Rule r1 u u' m, Rule r2 u' u'' m) => Rule (Bin r1 r2 >And) u u'' m where > apply (Bin r1 r2 _) u = apply r1 u >>= apply r2 > >Ghc complains about "Could not deduce (Rule r1 u u'1 m, Rule r2 u'1 u'' >m)", but it is obviously same as the constraint I gave in the instance >declaration. > >What am I doing wrong here? There's no information in the instance type for the compiler to figure out what u' (in the constraint expressions) might be. (See other responses.) ... I would question whether or not you really should be using a type class here -- that depends on your application, but I've done some work involving simple inference rules and found that a polymorphic algebraic datatype (with function-valued members) served my purposes better than a type class. #g -- >Thank you very much! > > >This message is intended only for the addressee and may contain information >that is confidential or privileged. Unauthorized use is strictly prohibited >and may be unlawful. If you are not the intended recipient, or the person >responsible for delivering to the intended recipient, you should not read, >copy, disclose or otherwise use this message, except for the purpose of >delivery to the addressee. If you have received this email in error, please >delete and advise us immediately. > >_______________________________________________ >Haskell mailing list >Haskell(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Re: type class does not compile
by oleg＠pobox.com 13 Jul '04

13 Jul '04

Ben Yu wrote: > class Rule r u u' m where > apply :: r -> u -> m u' > > data And = And > > data Bin a b o = Bin a b o > > instance (Monad m, Rule r1 u u' m, Rule r2 u' u'' m) => > Rule (Bin r1 r2 And) u u'' m where > apply (Bin r1 r2 _) u = apply r1 u >>= apply r2 > > Ghc complains about "Could not deduce (Rule r1 u u'1 m, Rule r2 u'1 u'' > m)", but it is obviously same as the constraint I gave in the instance > declaration. This is like the famous show . read problem. Here, 'apply r1 u' produces the value of a type `m v' for _some_ v. and 'apply r2' consumes this value. There is no way for the compiler to figure out what this 'v' is. You specified 'Rule r1 u u' m' as a constraint. However, there is nothing that guarantees that your u' in the constraint is the same as v that is needed to resolve the overloading. So, we need either a functional dependency, or a resort to nifty local type variables. The example of the latter is > instance (Monad m, Rule r1 u u' m, Rule r2 u' u'' m) => > Rule (Bin r1 r2 And) u u'' m where > apply (Bin r1 r2 _) u = ((apply r1 u)::m u') >>= apply r2 which makes your code compile. For more detail, please see: http://www.haskell.org/pipermail/haskell/2003-September/012782.html http://www.haskell.org/pipermail/haskell/2003-October/012783.html

1 0

type class does not compile
by Ben.Yu＠combined.com 13 Jul '04

13 Jul '04

Hi, please bear with me if my question turns out to be a stupid mistake. It has taken me hours to figure this out. class Rule r u u' m where apply :: r -> u -> m u' data And = And data Bin a b o = Bin a b o instance (Monad m, Rule r1 u u' m, Rule r2 u' u'' m) => Rule (Bin r1 r2 And) u u'' m where apply (Bin r1 r2 _) u = apply r1 u >>= apply r2 Ghc complains about "Could not deduce (Rule r1 u u'1 m, Rule r2 u'1 u'' m)", but it is obviously same as the constraint I gave in the instance declaration. What am I doing wrong here? Thank you very much! This message is intended only for the addressee and may contain information that is confidential or privileged. Unauthorized use is strictly prohibited and may be unlawful. If you are not the intended recipient, or the person responsible for delivering to the intended recipient, you should not read, copy, disclose or otherwise use this message, except for the purpose of delivery to the addressee. If you have received this email in error, please delete and advise us immediately.

2 2

RTA'05: call for papers
by femke＠few.vu.nl 11 Jul '04

11 Jul '04

****************************** * * * RTA'05 CALL FOR PAPERS * * * ****************************** http://www-i2.informatik.rwth-aachen.de/RTA05/ April 19--21, 2005 Nara, Japan The 16th Int. Conf. on Rewriting Techniques and Applications (RTA'05) will collocate with the 7th International Conference on Typed Lambda Calculi and Applications (TLCA'05) as part of the Federated Conference on Rewriting, Deduction and Programming (RDP'05). IMPORTANT DATES: Nov 12, 2004: Deadline for electronic submission of title and abstract Nov 19, 2004: Deadline for electronic submission of papers Jan 14, 2005: Notification of acceptance of papers Feb 4, 2005: Deadline for final versions of accepted papers Apr 19-21, 2005: Conference RTA is the major forum for the presentation of research on all aspects of rewriting. Typical areas of interest include (but are not limited to): * APPLICATIONS: case studies; rule-based (functional and logic) programming; symbolic and algebraic computation; theorem proving; system synthesis and verification; proof checking. * FOUNDATIONS: matching and unification; narrowing; completion techniques; strategies; constraint solving; explicit substitutions; tree automata. * FRAMEWORKS: string, term, and graph rewriting; lambda-calculus and higher-order rewriting; proof nets; constrained rewriting/deduction; categorical and infinitary rewriting. * IMPLEMENTATION: compilation techniques; parallel execution; rewriting tools. * SEMANTICS: equational logic; rewriting logic. INVITED TALKS will be given at RTA'05 by: * Amy Felty (Ottawa) * Yoshihito Toyama (Sendai) * Philip Wadler (Edinburgh) BEST PAPER AWARDS: An award of 100,000 Yen will be given to the best paper or papers as decided by the PC. RTA'04 PROGRAM COMMITEE: * Franz Baader (Dresden) * Mariangiola Dezani (Torino) * Juergen Giesl (Aachen, Chair) * Bernhard Gramlich (Vienna) * Florent Jacquemard (Cachan) * Claude Kirchner (Nancy) * Pierre Lescanne (Lyon) * Aart Middeldorp (Innsbruck) * Hitoshi Ohsaki (Amagasaki) * Vincent van Oostrom (Utrecht) * Christine Paulin-Mohring (Orsay) * Frank Pfenning (Pittsburgh) * Femke van Raamsdonk (Amsterdam) * Mark-Oliver Stehr (Urbana) * Rakesh Verma (Houston) * Andrei Voronkov (Manchester) RTA'05 SUBMISSIONS: Submissions must be original and not submitted for publication elsewhere. Submission categories include regular research papers and system descriptions. Also problem sets and submissions describing interesting applications of rewriting techniques will be very welcome. The page limit is 15 pages (10 pages for system descriptions). As usual, accepted papers will appear in the Springer-Verlag Lecture Notes in Computer Science series. More information about paper submission is available at the RTA'05 web page. http://www-i2.informatik.rwth-aachen.de/RTA05/ LOCATION, TRAVEL, ACCOMODATION, AND REGISTRATION The conference takes place in Nara park, which is one of the most important cultural sights of Japan with some of the oldest and most impressive temples and shrines. Airfares from Europe or the US to Japan are not expensive in mid-April and the conference will offer reasonably priced accommodation and low registration fees. RTA'05 PROGRAM CHAIR: Juergen Giesl LuFG Informatik II RWTH Aachen Ahornstr. 55 52074 Aachen Germany giesl(a)informatik.rwth-aachen.de RTA'05 CONFERENCE CHAIR: Hitoshi Ohsaki AIST Japan ohsaki(a)ni.aist.go.jp

1 0

ANN: "An Introduction to Computing with Haskell" in German
by Manuel M T Chakravarty 09 Jul '04

09 Jul '04

The book "An Introduction to Computing with Haskell" is now available in German from Pearson Education Germany http://www.pearson-studium.de/main/main.asp?page=bookdetails&ProductID=81781 The original English version has been reviewed in the Journal of Functional Programming, 14(2), March 2004, http://dx.doi.org/10.1017/S0956796803215033 The approach of the book was discussed in an Educational Pearl in the Journal of Functional Programming, 14(1), January 2004, http://dx.doi.org/10.1017/S0956796803004805 Manuel

1 0

Do the libraries define S' ?
by Graham Klyne 09 Jul '04

09 Jul '04

There's a pattern of higher-order function usage I find myself repeatedly wanting to use, exemplified by the following: [[ -- combineTest :: (Bool->Bool->Bool) -> (a->Bool) -> (a->Bool) -> (a->Bool) combineTest :: (b->c->d) -> (a->b) -> (a->c) -> a -> d combineTest c t1 t2 = \a -> c (t1 a) (t2 a) (.&.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.&.) = combineTest (&&) (.|.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.|.) = combineTest (||) t1 = (>0) .&. (<=4) $ 2 -- True t2 = (>0) .&. (<=4) $ 5 -- False t3 = (>0) .&. (<=4) $ 0 -- False t4 = (>0) .|. (<=4) $ 5 -- True t5 = (>0) .|. (<=4) $ 0 -- True tall = and [t1,not t2,not t3,t4,t5] ]] Looking at the fully-generalized type of 'combineTest', and digging around in SPJ's book on implementation of FP languages, I notice that my combineTest function has the same reduction pattern as the S' combinator used as an optimization of SK combinator compilation. All this (the recurring requirement, and the fact that S' is a very well-known combinator) leads me to think that maybe there is a version of S' somewhere in the standard Haskell libraries. If there is, where is it please? If not, should it be in there somewhere? #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

8 8

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

Separate Namespaces and Type Classes
by Stephan Herhut 08 Jul '04

08 Jul '04

Hi all, I am pretty new to haskell, but while exploring the haskell module system, I came along some questions. As far as I found out, haskell supports separated namespaces, i.e. every module has its own symbol space. Thus, when defining a class in one module like module A(Foo(f)) where class Foo a where f :: a -> Integer one should be able to define two instances having the same signature, as long as they are in different namespaces module B(bar) where import A(Foo(f)) instance Foo Integer where f x = x bar x = f x module C(tango) import A(Foo(f)) instance Foo Integer where f x = x + 1 tango x = f x As the integer instances of Foo are in separate modules and thus namespaces, one should be able to just import bar and tango module Main(main) import B(bar) import C(tango) main = print( (bar 5) + (tango 4) ) But now, ghc complains about two instances of Foo Integer, although there should be none in the namespace main. I have not found any documentation on why ghc behaves like this and whether this conforms to the haskell language specification. Is there any haskell compiler out there that is able to compile the above example? Thanks for your help Stephan

3 2