January 2005 - Haskell

Haskell-mode 2.0
by Stefan Monnier 02 Feb '09

02 Feb '09

I have recently taken over maintainership of Haskell-mode, and after making a bunch of changes, I figured it would be a good idea to make a new release. You can find this new release at: http://www-perso.iro.umontreal.ca/~monnier/elisp/ If you think it should also be found at http://www.haskell.org/haskell-mode/, then please tell John Peterson to get back to me (my email to him seem to go straight to the bitbucket. John?). This release has several changes that have all been only lightly tested, especially w.r.t compatibility with various Emacsen. See appended the NEWS file that describes some of the notewirthy changes. Stefan Changes since 1.45: * keybindings C-c <char> have been replaced by C-c C-<char> so as not to collide with minor modes. * The following modules are now automatically activated without having to add anything to haskell-mode-hook: haskell-font-lock (just turn on global-font-lock-mode). haskell-decl-scan (just bind `imenu' to some key). * In recent Emacsen, haskell-doc hooks into eldoc-mode. * haskell-hugs and haskell-ghci are superceded by inf-haskell. * Indentation rules have been improved when using layout inside parens/braces. * Symbols like -> and \ can be displayed as actual arrows and lambdas. See haskell-font-lock-symbols. * Tweaks to the font-lock settings. Among other things paren-matching with things like \(x,y) should work correctly now. * New maintainer <monnier(a)gnu.org>.

3 6

Mixing monadic and non-monadic functions
by Sean E. Russell 17 Sep '05

17 Sep '05

Hello, I posted this question to comp.lang.functional, and someone suggested that I try this group instead. I'm struggling with monads. Well, not monads themselves, but mixing them with non-monadic functions. Here's my base case: someFunc :: String -> IO [a] ... ax <- someFunc a bx <- someFunc b assertBool "fail" $ length ax == length bx I don't like the assignments; the typing is redundant, if I have a lot of asserts like this, and the "variables" are temporary. What I'd much rather have is: ... assertBool "fail" $ (length $ someFunc a) == (length $ someFunc b) which is more readable, to my eye. The only solution which has been suggested that may work is liberal use of the liftM variants, but this gets *really* tedious and obtuse. Is there an elegant way to do what I want to do, or am I stuck with procedural-style assignments and bunches of temp vars? Thanks! -- ### SER ### Deutsch|Esperanto|Francaise|Linux|XML|Java|Ruby|Aikido ### http://www.germane-software.com/~ser jabber.com:ser ICQ:83578737 ### GPG: http://www.germane-software.com/~ser/Security/ser_public.gpg

23 37

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

ICALP'05: Call for Papers
by Luis Caires 13 May '05

13 May '05

___________________________________________________________________ CALL FOR PAPERS - ICALP'05 32nd International Colloquium on Automata, Languages and Programming July 11-15, 2005, Lisboa, Portugal http://icalp05.di.fct.unl.pt/ ___________________________________________________________________ The 32nd International Colloquium on Automata, Languages and Programming, the main conference and annual meeting of the European Association for Theoretical Computer Science EATCS will take place from the 11th to the 15th of July 2005 in Lisboa, Portugal. As a complement to the established Tracks on Algorithms, Automata, Complexity and Games (A), and on Logic, Semantics, and Theory of Programming (B), corresponding to the two main streams of the journal Theoretical Computer Science, ICALP'05 innovates on the structure of its traditional scientific program with the inauguration of a new special Track (C). The aim of Track C is to allow a deeper coverage of a particular topic, to be specifically selected for each year's edition of ICALP on the basis of its timeliness and relevance for the theoretical computer science community. Papers presenting original research on all aspects of theoretical computer science are sought. Typical but not exclusive topics of interest are: Track A (Algorithms, Automata, Complexity and Games): Giuseppe F. Italiano Università di Roma "Tor Vergata", Italy (PC Chair) * Algorithmic Aspects of Networks * Algorithms and Data Structures * Automata Theory and Formal Languages * Combinatorics in Computer Science * Computational Biology * Computational Complexity * Computational Geometry * Internet Algorithmics * Machine Learning * Parallel and Distributed Computing * Quantum Computing Track B (Logic, Semantics, and Theory of Programming): Catuscia Palamidessi INRIA Futurs and LIX, France (PC Chair) * Algebraic and Categorical Models * Databases, Semi-Structured Data and Finite Model Theory * Principles of Programming Languages * Logics, Formal Methods and Model Checking * Models of Concurrent, Distributed, and Mobile Systems * Models of Reactive, Hybrid and Stochastic Systems * Program Analysis and Transformation * Specification, Refinement and Verification * Type Systems and Typed Calculi Track C (Security and Cryptography Foundations): Moti Yung Columbia University, USA (PC Chair) * Cryptographic Notions, Mechanisms, Systems and Protocols * Cryptographic Proof Techniques, Lower bounds, Impossibilities * Foundations of Secure Systems and Architectures * Logic and Semantics of Security Protocols * Number Theory and Algebraic Algorithms in Cryptography * Pseudorandomness, Randomness, and Complexity Issues * Secure Data Structures, Storage, Databases and Content * Security Modeling: Combinatorics, Graphs, Games, Economics * Specifications, Verifications and Secure Programming * Theory of Privacy and Anonymity * Theory of Security in Networks and Distributed Computing * Quantum Cryptography and Information Theory SUBMISSIONS: ************ Authors are invited to submit an extended abstract of no more than 12 pages in LNCS style presenting original research on the theory of Computer Science. Submissions should indicate to which track (A, B, or C) the paper is submitted. No simultaneous submission to other publication outlets (either a conference or a journal) is allowed. The proceedings will be published in the Lecture Notes in Computer Science Series by Springer-Verlag. IMPORTANT DATES: **************** Workshop proposals due: November 28, 2004 Submissions: February 13, 2005 Notification: April 8, 2005 Final version due: April 30, 2005 PROGRAM COMMITTEE: ****************** Track A (Algorithms, Automata, Complexity and Games) * Lars Arge, Duke University, USA * Giorgio Ausiello, University of Rome "La Sapienza", Italy * Surender Baswana, Max-Planck-Institut fur Informatik, Saarbrucken, Germany * Hans Bodlaender, University of Utrecht, The Netherlands * Véronique Bruyère, University of Mons-Hainaut, Belgium * Adam Buchsbaum, AT&T Labs - Research, USA * Josep Diaz, Universitat Politecnica de Catalunya, Spain * David Eppstein, University of Irvine, USA * Andrew Goldberg, Microsoft, USA * Monika Henzinger, ETH Lausanne, Switzerland * Giuseppe F. Italiano, University of Rome "Tor Vergata", Italy (Chair) * Marios Mavronicolas, University of Cyprus, Cyprus * Peter Bro Miltersen, University of Aarhus, Denmark * Mike Paterson, University of Warwick, United Kingdom * Dominique Perrin, Université de Marne la Vallée, France * Seth Pettie, Max-Planck-Institut fur Informatik, Saarbrucken, Germany * Yuval Rabani, Technion, Israel * Antonio Restivo, University of Palermo, Italy * José Rolim, University of Geneva, Switzerland * Dorothea Wagner, University Karlsruhe, Germany * Tandy Warnow, University of Texas at Austin, USA * Christos Zaroliagis, CTI and University of Patras, Greece Track B (Logic, Semantics, and Theory of Programming) * Kenichi Asai, University of Ochanomizu, Japan * Joos Baeten, University of Eindhoven, NL * Peter Buneman, University of Edinburgh, UK * Zoltan Esik, University of Szeged, Hungary * Javier Esparza, University of Stuttgart, Germany * Marcelo Fiore, Christ's College and University of Cambridge, UK * Manuel Hermenegildo, Universidade de Madrid, Spain * Delia Kesner, Universite Paris VII, France * Kim Guldstrand Larsen, University of Aalborg , Denmark * Gopalan Nadathur, University of Minnesota, USA * Uwe Nestmann, EPFL, Switzerland * Catuscia Palamidessi, INRIA, France (Chair) * Amr Sabry, University of Indiana, USA * Davide Sangiorgi, Universita di Bologna, Italy * Roberto Segala, Universita di Verona, Italy * Harald Sondergaard, University of Melbourne, Australia Track C (Security and Cryptography Foundations) * David Basin, ETH Zurich, Switzerland * Christian Cachin, IBM Research, Switzerland * Alfredo De Santis, Universita di Salerno, Italy * Cynthia Dwork, Microsoft Research, USA * Matt Franklin, U.C. Davis, USA * Michael Goodrich, U.C. Irvine, USA * Andrew D. Gordon, Microsoft Research, UK * Roberto Gorrieri, Universita di Bologna, Italy * Yuval Ishai, Technion, Israel * Phil McKenzie, DoCoMo Labs., USA * Tatsuaki Okamoto, NTT Labs., Japan * David Pointcheval, ENS Paris, France * Tal Rabin, IBM Research, USA * Omer Reingold, IAS Princeton, USA * Adi Rosen, Technion, Israel * Amit Sahai, UCLA, USA * Andre Scedrov, University of Pennsylvania, USA * Igor Shparlinsky, Macquarie University, Australia * Nigel Smart, University of Bristol, UK * Moti Yung, Columbia University, USA (Chair) ORGANIZING COMMITTEE: ********************* Luis Monteiro Luis Caires Antonio Ravara Vasco Vasconcelos CONTACT ADDRESSES: ****************** For further information see: http://icalp05.di.fct.unl.pt/

1 2

Hierarchical module namespace extension not sufficiently flexible
by Duncan Coutts 07 Mar '05

07 Mar '05

All, So here's the problem: we have a binding to a large foreign library (GTK) which we are trying to fit nicely into hierarchical module name space. It would live under Graphics.UI.Gtk Graphics.UI.Gtk.Button Graphics.UI.Gtk.Frame ... etc Now there are over 100 modules directly under Graphics.UI.Gtk and you don't want to have to import each one of them separately. Of course you will not use all of them in one module but you might reasonably use 20+ of them. So it'd be nice to be able to say: > import Graphics.UI.Gtk or > import qualified Graphics.UI.Gtk as Gtk But now we have a problem. These import directives import a flat namespace, or a flat namespace qualified by a single module alias (ie Gtk in the second example). But the Gtk modules are deliberatly designed to have hierarchical names. You cannot simply combine them all together into a flat namespace without falling back to the trick of prefixing each function name with the module name. So while we would like to be able for users to do this: > import Graphics.UI.Gtk > > ... Button.setLabel ... They will instead have to say: > import Graphics.UI.Gtk > > ... buttonSetLabel ... Which is one of the things that the hierarchical module namespace extension was trying to get rid of! All the other language bindings for Gtk (apart from C) use the former import and useage style. It doesn't make us look good! :-) So my question is: have I overlooked something or is this really not possible at the moment. And secondly, if it is currently not possible is there a 'nice' extension that would allow this sort of thing. (Where nice probably means Haskell98 compatible / 'doesn't' break existing programs) How about: > module Graphics.UI.Gtk ( > > module qualified Graphics.UI.Gtk.Button as Button > ... > ) where > > import Graphics.UI.Gtk.Button or equivalently(?): > module Graphics.UI.Gtk ( > > module qualified Button > ... > ) where > > import Graphics.UI.Gtk.Button as Button Duncan Ps there's a oddity I found where if you say: > module Foo ( > module Bar > ) > > import qualified Bar then module Foo exports precisely nothing. But there's no error or warning.

8 12

Implicit parallel functional programming
by Satnam Singh 10 Feb '05

10 Feb '05

I'm trying to find out about existing work on implicit parallel functional programming. I see that the Glasgow Haskell compiler has a parallel mode which can be used with PVM and there is interesting work with pH at MIT. Does anyone know of any other work on implicitly parallelizing functional programs for fine grain parallel execution? The emergence of multi-core processors makes me think that we should look at implicit parallel functional programming in a new light. Cheers, Satnam ________________________________________ Satnam Singh Microsoft One Microsoft Way Redmond Washington 98052-6399 USA Email: satnams(a)microsoft.com Telephone: +1 425 705 8208 Cell: +1 408 718 2588 Pager: 4087182588(a)mobile.att.com

22 28

Re: [Haskell] Typing in haskell and mathematics
by Cale Gibbard 01 Feb '05

01 Feb '05

I agree, as an undergraduate student of pure mathematics, I have been finding fairly large parts of the discussion about mathematical notation to be somewhat silly and uninformed. (Really it was more the previous thread, but it seems to have been continued here). One thing to keep in mind about mathematical notation is that it is usually not intended to be read by machines, rather it is a human language, albeit a very precise one. Statements like "a < b < c" are perfectly clear to everyone present, and if anyone has a type error in their head when reading that which they can't get past, they are most likely just being stubborn. Another common thing which is done whenever convenient is to treat Cartesian product as associative, and naturally identify the spaces (A x A) x A and A x (A x A), along with perhaps A^3 which might be functions f: {0,1,2} -> A, or might be treated as one of the preceding. In any given context, it should be easy to determine the author or lecturer's intent as to whether these are distinct or the same. Bookkeeping is left as an exercise to the bored reader or to logicians. (With the recent comment that functional programmers are applied logicians, perhaps it is no surprise that they would be upset with such fuzziness in the language!) The notational confusion between f and f(x) tends not to happen beyond the level of highschool, at least not where I am. The former refers to the function f, and the latter refers to a point in its codomain. In fact, I currently am dealing with the opposite problem in trying to learn differential geometry - people and books using just f to refer to a particular point in the codomain of f. All functions are automatically evaluated at a given point of concern. This seems to be common among physicists for some reason (most likely because they'd like to think of the function as a quantity, and are used to quantities having implicit relationships). Another thing to keep in mind is that mathematics is written in what is usually another human language. If I write a proof in English, I can provide enough context that any natural transformations I implicitly apply to things will be made obvious to the reader. The goal is not usually a machine-checkable proof, rather it's to convey enough information that anyone paying attention could produce one. A professor of mine used the term "rigourisable", halfway joking about the process. Basically, enough logical steps are provided so that the ideas are clear, and everyone is completely convinced that they could fill in the details -- mathematicians are usually pretty good at making sure that the details that they're providing for themselves are consistent. The reasons that such bookkeeping details are not generally provided is that for one, if someone is unable to fill some detail in, they are expected to think about it and then ask a question, and two, providing all of the details only serves to obscure the actual reasoning. Getting caught up in explicitly applying natural transformations that people would apply in their head without much thought anyway is a waste of time and creates a lot of junk to have to sift through to find the key ideas. In any case, it is important to keep the audience in mind while writing anything, including symbols. - Cale p.s. There are other good philosophical reasons not to take everything down to the level of formal logic and set theory all the time, stemming from Goedel's result that a formal system for mathematics cannot be proven consistent within itself. If we ever discover our system is broken it will likely have to be replaced by a similar one which corrects the problem. The fuzziness serves as good protection in the case of such an earthquake. It's easier to map slightly fuzzy notions with a given semantic interpretation onto a new system and find the analogues of theorems that you had before than it is to map direct low-level syntactical statements across and be able to say that they mean anything at all similar. On Mon, 31 Jan 2005 13:59:58 +0100, Benjamin Franksen <benjamin.franksen(a)bessy.de> wrote: > On Monday 31 January 2005 04:24, Jeremy Gibbons wrote: > > Despite being a fan of generic programming, I have my doubts about > > this kind of automatic lifting. It works fine in "ordinary > > mathematics", because there is no fear of confusion - one hardly ever > > deals with functions as entities in their own right. > > May I please beg to differ? When I studied math, things were quite > different, at least. I remember whole branches of mathematics > completely dedicated to dealing with "functions as entities in their > own right". One notable example is Functional Analysis, of which I > happen to know a little. And, as far as I remember, we used notation > which reflected this, i.e. nobody wrote 'f(x)' when actually they meant > just 'f', which is the same as '\x -> f x', which in math is usually > written 'x |-> f(x)'. > > > (Witness "sigma > > sin(x) dx", involving a term sin(x) and a dummy variable x, rather > > than the more logical "sigma sin", involving the function.) > > The notations for 'integral' and 'differential quotient' stem from a > time when dealing with functions as entities in their own right was > indeed not yet a common concept in mathematics, i.e. earlier than 1900. > > BTW, 'sigma sin' is not a function. > > Ben > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell >

5 4

CFP: WRS'05 *** extended deadline ***
by roberto＠dicosmo.org 31 Jan '05

31 Jan '05

********************************************************************** 5th Int'l Workshop on Reduction Strategies in Rewriting and Programming WRS'05 Nara, Japan, April 22nd, 2005 Call For Submissions *** EXTENDED DEADLINE: February 14th *** ********************************************************************** Reduction strategies in rewriting and programming have attracted an increasing attention within the last years. New types of reduction strategies have been invented and investigated, and new results on rewriting / computation under particular strategies have been obtained. Research in this field ranges from primarily theoretical questions about reduction strategies to very practical application and implementation issues. The need for a deeper understanding of reduction strategies in rewriting and programming, both in theory and practice, is obvious, since they bridge the gap between unrestricted general rewriting (computation) and (more deterministic) rewriting with particular strategies (programming). Moreover, reduction strategies provide a natural way to go from operational principles (e.g., graph and term rewriting, narrowing, lambda-calculus) and semantics (e.g., normalization, computation of values, infinitary normalization, head-normalization) to implementations of programming languages. Therefore any progress in this area is likely to be of interest not only to the rewriting community, but also to neighbouring fields like functional programming, functional-logic programming, and termination proofs of algorithms. The workshop wants to provide a forum for the presentation and discussion of new ideas and results, recent developments, new research directions, as well as of surveys on existing knowledge in this area. Furthermore we aim at fostering interaction and exchange between researchers and students actively working on such topics. Information on the previous, and forthcoming, WRS editions is available from the WRS permanent homepage. TOPICS Topics of interest 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 and explicit substitutions, 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., 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 * data structures and implementation techniques for reduction strategies 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). Please, send a message containing your submission in postscript or PDF format to the PC co-chairs at wrs05(a)pps.jussieu.fr before February 14th, 2005. 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 March 18, 2005. PUBLICATION Accepted papers will be included in the preliminary workshop proceedings that will be available at the workshop. Selected papers will be published in the Electronic Notes in Theoretical Computer Science (ENTCS) series of Elsevier. IMPORTANT DATES February 14, 2005 Deadline for electronic submission of papers February 28, 2005 Notification of acceptance of papers March 18, 2005 Deadline for final versions of accepted papers April 22, 2005 Workshop INVITED SPEAKERS * Kokichi Futatsugi (JAIST, Japan) * Hongwei Xi (Boston University, USA) PROGRAM COMMITTEE * Sergio Antoy (Portland) * Eduardo Bonelli (Stevens) * Roberto Di Cosmo (Paris VII, Co-Chair) * Bernhard Gramlich (Wien) * Stefano Guerrini (Roma) * Salvador Lucas (Valencia) * Aart Middeldorp (Innsbruck) * Yoshihito Toyama (Tohoku, Co-Chair) PROGRAM CO-CHAIRS Roberto Di Cosmo Laboratoire PPS - Universite Paris 7, France Email: roberto(a)dicosmo.org Yoshihito Toyama Tohoku University, Japan Email: toyama(a)nue.riec.tohoku.ac.jp FURTHER INFORMATION * Call for papers in Text, PostScript and PDF format * WRS permanent website: http://www.dsic.upv.es/~wrs * WRS 2005 e-mail address: wrs05(a)pps.jussieu.fr * RDP 2005 website: http://www.kurims.kyoto-u.ac.jp/rdp05/

1 0

monad transformers
by John Meacham 31 Jan '05

31 Jan '05

So, I create my own monad transformers quite often, It is great to be able to compose 5 or 6 transformers to get the perfect one for a given task. for example here is one for collecting statistics: -- The stats newtype Stat = Stat (Map.Map Atom Int) instance Monoid Stat where mempty = Stat Map.empty mappend (Stat a) (Stat b) = Stat $ Map.unionWith (+) a b -- The Monad transformer. newtype StatT m a = StatT (WriterT Stat m a) deriving(MonadIO, Functor, MonadTrans, Monad) runStatT (StatT m) = runWriterT m -- The operations on this type of monad class Monad m => MonadStats m where mticks' :: Int -> Atom -> m () instance Monad m => MonadStats (StatT m) where mticks' n k = StatT $ tell (Stat $ Map.single k n) Now all is well and good, I was able to use newtype deriving for most every interesting property I wanted from the WriterT monad. (note I specifically did not derive MonadWriter, as the point of my own transformer is to hide this). However, now we come to the crux, I want the various interesting monad operations (MonadReader, MonadWriter, etc.. ) to be able to pass through StatT as well as let MonadStats pass through other monad transformers. the second is easy and elegant: instance (Monad m, Monad (t m), MonadTrans t, MonadStats m) => MonadStats (t m) where mticks' n k = lift $ mticks' n k the first, however, is tricky. Right now, it appears that every Monad type in the libraries defines a rule for commuting with every other monad type, this seems impracticle for many monads (n^2 rules!) so, my question is, why arn't the standard monad transformers declared with an instance like above? as in: instance (Monad m, Monad (t m), MonadTrans t, MonadWriter w m) => MonadWriter w (t m) where ... Then, all that is needed is for everyone to declare theire monads as MonadTrans providing an appropriate lift and every monad property should compose nicely.* Another semi-solution would be to allow newtype-deriving of these monad properties somehow.. newtype StatT m a = StatT (WriterT Stat m a) deriving(MonadIO, Functor, MonadTrans, Monad, MonadReader) doesn't work, how bout something like newtype StatT m a = StatT (WriterT Stat m a) deriving(MonadIO, Functor, MonadTrans, Monad, MonadReader r m => MonadReader r ) which should give the newtype-deriving rule enough to figure out how to derivie the MonadReader rule properly. * We might need to come up with a more advanced MonadTrans class for certain monads, as 'lift' has been shown to not be fully capable for some situtations such as catching exceptions in an arbitrary MonadIO. ** The monad transformer libraries appear to have moved somewhere in the most recent cvs fptools tree, anyone know where they moved too? *** Monad transformers rock. -- John Meacham - ⑆repetae.net⑆john⑈

3 2

Typing in haskell and mathematics
by Jacques Carette 31 Jan '05

31 Jan '05

The previous post on record syntax reminded me of some 'problems' I had noticed where Haskell and mathematics have a (deep) usage mismatch. First, consider a syntax for other component-wise function application? For example, it would be convenient to have (f,g) @ (x,y) be (f x, g y). In some languages [with dynamic typing], one can even do (f,g) (x,y) :-) Yes, I am aware that this untypeable in Haskell, because polymorphism is straight-jacketed by structural rules. But in mathematics, it is convenient and extremely common to: 1) look at the type a -> b as being a *subtype* of b (though I have never seen it phrased that way in print) 2) to consider every 'natural transformation' available and use it (tuples of functions <-> obvious function on tuples) Seeing a -> b as a subtype of b allows one to take any function f : b -> b -> c (like + ) and 'lift' it to ff : (a -> b) -> (a -> b) -> (a -> c) via the obvious definition ff g h = \x -> f (g x) (h x) This is done routinely in mathematics. The meaning of the expression (sin + cos) should be immediately obvious. Such 'lifting' is used even in first-year calculus courses, but not in Haskell. The "same" phenomenon is what allows one to 'see' that there is an obvious function apply_tuple:: (a->b,c->d) -> (a,c) -> (b,d) so that (f,g) (a,b) only has one possible meaning, if the built-in apply function were to be overloaded. Similarly, there are "obvious" maps apply_T :: T (a->b) -> a -> T b for any datatype constructor T (as has been noticed by all who do 'generic' programming). This means that [f, g, h] x == [f x, g x, h x] but also (in mathematics at least) {f, g, h} x == {f x, g x, h x} where {} denotes a set, and the equality above is extensional equality, and so on. Note that some computer algebra systems use #1 and #2 above all the time to define the operational meaning of a lot of syntactic constructs [where I personally extended the use of such rules in the implementation & operational semantics of Maple]. What hope is there to be able to do something 'similar' in a Haskell-like language? Jacques

6 6