March 2002 - Haskell - Haskell.org

tuple component functions
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

S.D.Mechveliani writes: > As Haskell has the standard functions fst, snd to decompose (a,b), > maybe, it worths to provide also > tuple31, tuple31, tuple31, > ... > tuple51, tuple52, tuple53, tuple54, tuple55 > > for the tuples of n = 3,4,5 ? I've found some of these useful, except I named them differently: > fst3 :: (a,b,c) -> a > fst3 (x,_,_) = x > snd3 :: (a,b,c) -> b > snd3 (_,x,_) = x > thd3 :: (a,b,c) -> c > thd3 (_,_,x) = x .... never got around to quadruples etc. I also defined (some of these may be untested): > tripl :: a -> (a,a,a) > tripl x = (x,x,x) > curry3 :: ((a, b, c) -> d) -> a -> b -> c -> d > curry3 f x y z = f (x, y, z) > uncurry3 :: (a -> b -> c -> d) -> ((a, b, c) -> d) > uncurry3 f t = f (fst3 t) (snd3 t) (thd3 t) > applyTriple :: (a -> b, a -> c, a -> d) -> a -> (b,c,d) > applyTriple (f,g,h) x = (f x, g x, h x) > cross3 :: (a -> b, c -> d, e -> f) -> (a,c,e) -> (b,d,f) > cross3 (f,g,h) (x,y,z) = (f x, g y, h z) > mapTriple :: (a -> b) -> (a, a, a) -> (b, b, b) > mapTriple = cross3 . tripl > applyFst3 :: (a -> b) -> (a, c, d) -> (b, c, d) > applyFst3 f = applyTriple (f . fst3, snd3, thd3) > applySnd3 :: (a -> b) -> (c, a, d) -> (c, b, d) > applySnd3 f = applyTriple (fst3, f . snd3, thd3) > applyThd3 :: (a -> b) -> (c, d, a) -> (c, d, b) > applyThd3 f = applyTriple (fst3, snd3, f . thd3) > applyArgs3 :: (a -> b) -> (c -> d) -> (e -> f) -> (b -> d -> f -> g) -> (a -> c -> e -> g) > applyArgs3 af1 af2 af3 f = \x y z -> f (af1 x) (af2 y) (af3 z) > rotl :: (a -> b -> c -> d) -> (b -> c -> a -> d) > rotl f y z x = f x y z > rotr :: (a -> b -> c -> d) -> (c -> a -> b -> d) > rotr f z x y = f x y z > rotl4 :: (a -> b -> c -> d -> e) -> (b -> c -> d -> a -> e) > rotl4 f y z t x = f x y z t > rotr4 :: (a -> b -> c -> d -> e) -> (d -> a -> b -> c -> e) > rotr4 f t x y z = f x y z t Some more combinators (only for pairs so far): > twin :: a -> (a,a) > twin x = (x,x) > swap :: (a,b) -> (b,a) > swap (x,y) = (y,x) -- apply a pair of functions to one argument > applyPair :: (a -> b, a -> c) -> a -> (b, c) > applyPair (f, g) x = (f x, g x) -- apply a pair of functions to a pair > cross :: (a -> b, c -> d) -> (a, c) -> (b, d) > cross (f, g) = applyPair (f . fst, g . snd) -- compose a pair of functions onto one function > dotPair :: (a -> b, a -> c) -> (d -> a) -> (d -> b, d -> c) > dotPair (f, g) h = (f . h, g . h) -- compose a pair of functions onto a pair of functions > dotCross :: (a -> b, c -> d) -> (e -> a, f -> c) -> (e -> b, f -> d) > dotCross (f, g) (h, i) = (f . h, g . i) > mapPair :: (a -> b) -> (a, a) -> (b, b) > mapPair = cross . twin > applyFst :: (a -> b) -> (a, c) -> (b, c) > applyFst f = applyPair (f . fst, snd) > applySnd :: (a -> b) -> (c, a) -> (c, b) > applySnd f = applyPair (fst, f . snd) > applyArgs :: (a -> b) -> (c -> d) -> (b -> d -> e) -> (a -> c -> e) > applyArgs af1 af2 f = \x y -> f (af1 x) (af2 y) > betweenFst :: (a -> b -> c) -> (a, d) -> (b, e) -> c > betweenFst = applyArgs fst fst > betweenSnd :: (a -> b -> c) -> (d, a) -> (e, b) -> c > betweenSnd = applyArgs snd snd I find these combinators useful, and probably other people have their own versions - it would be nice to get them standardised, so we all speak the same language. By standardised, I mean a prominent version that will be adopted by users, not necessarily a committee process. Tim

3 2

ICFP programming contest
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

Michael Hobbs writes: > Just took a look at the results for the ICFP contest. Am I correct in > assuming that "LA" stands for Lennart Augustsson and that "Si^3" stands > for Simon Marlow, Simon Peyton-Jones, Sigbjorn Finne? Is there a URL for the results ? Tim

2 1

Type extensions
by Ronald Legere 04 Jun '02

04 Jun '02

Greetings. I have decided to try and understand the type system of haskell with extensions. As far as I can tell, the following set of extensions has been included, for example in ghc: multiparameter type classes constructor classes existential types explicit universal quantification scoped type signatures funtional dep?? Etc There is probably some overlap, and probably missed a few, as i do not understand what all these things do! ! My question: How do you get started learning all this? which of these is the most important? Is there a paper out there that explains most or all of these extensions and why you would want them and HOW the heck they work together? Ron Legere __________________________________________________ Do You Yahoo!? Yahoo! Greetings - send holiday greetings for Easter, Passover http://greetings.yahoo.com/

2 2

MPC 2002: Deadline extended until 11 February
by mpc02 15 May '02

15 May '02

[Apologies for multiple copies] The deadline for MPC 2002, 6th International Conference on MATHEMATICS OF PROGRAM CONSTRUCTION, 8-10 July, Dagstuhl, Germany (see http://www.cs.ukc.ac.uk/conf/mpc2002/ for a full CFP) has been extended until 11 February 2002. Full papers should be submitted in Postscript or pdf format by e-mail to mpc02(a)ukc.ac.uk. -- Mathematics of Program Construction '02 at Dagstuhl Eerke Boiten, Computing Laboratory, University of Kent at Canterbury, UK +44.1227.827615 (fax 762811)

1 1

Re: Lambda over types.
by oleg＠pobox.com 02 Apr '02

02 Apr '02

anatoli <anatoli at yahoo> wrote: > Attached are two interpreters: one for untyped lambda calculus, I'm afraid the attached interpreter can't be an implementation of the lambda calculus. For one thing, it lacks the hygiene of substitutions: Lambda> :t lambdaEval (A (L X (L Y (A X Y))) T) lambdaEval (A (L X (L Y (A X Y))) T) :: L Y (A T Y) That's OK. However, Lambda> :t lambdaEval (A (L X (L Y (A X Y))) Y) lambdaEval (A (L X (L Y (A X Y))) Y) :: L Y (A Y Y) That is wrong! The correct answer is: L Yfresh (A Y Yfresh) The interpreter in question doesn't appear to be able to manufacture fresh identifiers (i.e., fresh types). Without an ability to expand the set of available identifiers, the capture-free substitution is impossible. Furthermore, some terms fail to evaluate: Lambda> :t lambdaEval (A (L X (A X X)) T) lambdaEval (A (L X (A X X)) T) :: Eval (A (L X (A X X)) T) a => a Lambda> :t lambdaEval (A (A (L X X) T) Y) lambdaEval (A (A (L X X) T) Y) :: Eval (A (A (L X X) T) Y) a => a which is not the result one would've expected. Finally, the interpreter doesn't actually find the normal form. The rule > instance Eval (L v e) (L v e) prevents any reductions under lambda. True, call-by-name or call-by-value interpreters stop short of reducing the body of a lambda form. Normal or applicative order interpreters however -- in order to find the beta-eta-normal form -- should seek and attempt any reduction. The hygienic substitution (with alpha-conversion if necessary) and the repeated identification of the leftmost outermost redex are actually quite challenging. We can guarantee the hygienic substitution if we implement the de Bruijin notation for lambda terms. Another, related technique is coloring of existing identifiers. A macro-expander of R5RS Scheme macros implements the coloring to ensure the hygiene of macro expansions. The macro-expander can be cajoled into painting identifiers on our demand, which has been used in a macro-expand-time lambda calculator. In Haskell, we have to paint manually. A variable in a typechecker-time lambda-calculator has to be represented by a type like Vr (Succ (Succ (Succ Zero))) X. The latter component is the "name" and the former is the color. The Eval and Subst relations should be extended with color_in and color_out type parameters (perhaps with a dependency: term color_in -> color_out). The only non-trivial use of colors is in doing a substitution (L var body)[exp/var']. The bound variable has to be repainted before the substitution in the body. The beta-substitutor itself can do the repainting.

2 2

Re: using less stack
by C.Reinke 02 Apr '02

02 Apr '02

> > > cpsfold f a [] ú > > > cpsfold f a (x:xs) ÿ x a (\y -> cpsfold f y xs) > > > > and f takes a continuation, Bob's my uncle, and I have a program that > > runs quickly in constant space! > > Good. I'm curious to know from other readers whether > continuations like this are the only way of solving it, > though. Actually, and quite apart from it being cumbersome to use, I've got my doubts about whether this cpsfold really does the job (is that just me missing some point?-). Also, I'm curious to know why the usual strict variant of foldl doesn't help in this case? foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs or, with the recently suggested idiom for strictness, tracing and other annotations:-) annotation = undefined strict a = seq a False foldl' f a l | strict a = annotation foldl' f a [] = a foldl' f a (x:xs) = foldl' f (f a x) xs Claus

8 10

Re: ">>" and "do" notation
by Wolfgang Jeltsch 01 Apr '02

01 Apr '02

On Thursday, March 28, 2002, 16:37 CET James B. White III wrote: > [...] > I think the default definition of ">>" is just that, a default, and not a > law. I suppose, a >> b = a >>= \_ -> b is intended to be a law. This would mean that every redefined (>>) would have to obey this law. > [...] > If it is a law, why are users given the power to change it! For performance reasons, I would suppose. > Also, I think that the Report *specifies* the translation of "do" to ">>", > not merely suggests it. The report specifies certain identities and suggests to use these identities for translations into the kernel. If it is also a law that a >> b and a >>= \_ -> b are identical even with respect to laziness then, I think, a conforming Haskell implementation could use the latter instead of the former to realize do expressions. But I would prefer implementations using (>>). > [...] > ">>" should no longer be a class function with a default value that can be > changed; it should be syntactic sugar built into Haskell, like "do" > notation. It shouldn't be syntactic suger but at most an operator which does not belong to the monad class. One could define (>>) just as an ordinary function instead of a class member. > [...] By the way, why uses the report the complicated looking \_ -> b instead of just const b. Wolfgang

4 3

PLAN-X: Programming Language Technologies for XML
by Shriram Krishnamurthi 31 Mar '02

31 Mar '02

PLAN-X: PROGRAMMING LANGUAGE TECHNOLOGIES FOR XML Oct 3, 2002 Pittsburgh, PA (Co-located with PLI) CALL FOR PAPERS Submission deadline: May 1, 2002 XML has emerged as the de facto standard for data interchange on the web. The use of XML as a common format for representation, interchange, and transformation of data poses new challenges to programming languages, applications, and database systems. During the last few years, the database research community has devoted a lot of attention to XML's data representation challenges, as evidenced by the number of XML-related publications in premier database conferences and journals. In contrast, the attention devoted to XML by the programming language research community has been minimal. This is unfortunate, since the robustness of current and future programming standards and tools for XML will depend on the strength of their foundations in core programming technologies e.g., XML parsing (parsing theory and incremental parsing), XML schemas (type systems), XPATH expressions and XSLT programs (pattern-matching languages and their optimization), XSLT debuggers (dynamic program analysis and slicing). Since XML is a new domain, core programming technologies developed in past research cannot be used unchanged; instead, novel research is required to address the unique challenges posed by XML and its use in web applications and standalone applications. This workshop aims to bring together researchers from the programming languages and XML communities, a) to foster novel research to address unique challenges being posed by XML on current and future programming technologies; b) to exchange information on early research experiences with XML-related programming systems, tools, and languages; and c) to expose the PLI community to XML technologies and the potential impact of these technologies on future software. SUBMISSION PROCEDURE We solicit submissions on original research not previously published or currently submitted for publication elsewhere, in the form of extended abstracts. These extended abstracts should not exceed 5000 words (approximately 10 pages). Detailed submission instructions will be posted at http://www.research.avayalabs.com/user/wadler/planx by early April. PROCEEDINGS There will be no formal proceedings. An informal proceedings will be distributed at the workshop. IMPORTANT DATES Paper submission deadline May 1 Notification of acceptance June 21 Final papers due for informal proceedings Sep 4 WEB PAGE: http://www.research.avayalabs.com/user/wadler/planx/ GENERAL CHAIR: Vivek Sarkar, IBM PROGRAM COMMITTEE: Allen Brown (Microsoft) Peter Buneman (Edinburgh) Sophie Cluet (Xyleme / INRIA) Mary Fernandez (AT&T Labs) Shriram Krishnamurthi (Brown) Makoto Murata (IBM Japan) Benjamin Pierce (University of Pennsylvania), co-chair Michael Schwartzbach (Aarhus) Dan Suciu (University of Washington) Philip Wadler (Avaya Labs), co-chair INVITED SPEAKER: James Clark

1 0

Ѱ��
by tony 31 Mar '02

31 Mar '02

�װ��ѣ� ��ã� ��磨��ţ��޹�˾��ʺ��л��տ��ʼ��ϵ�ϣ��ܳ�Ϊ��ڹ� ��Ҫ��顣��һ�Ҳ��¼��ᾧ��о��ƹ�ͷ�չ�¼��ڻ��Ϣ��񡢵� ��ҵӦ�÷��ĸ��¼��ҵ��:http://www.raeline.net email:webmaster@raeline.net лл�� ˾��2000��ȫ��ʻ��Ƴ��²�Ʒ��ȫ��⽫�� ֵ��ѡ�� 1.30M�ռ䣫50M��ҵ��䣫1��ȫ�棬��198Ԫ/�ꡣ ��2.50M�ռ䣫100M��ҵ��䣫1��ȫ�棬��248Ԫ/�ꡣ ��3.100M�ռ䣫100M��ҵ��䣫1��ȫ�棬��318Ԫ/�ꡣ ��4.100M�ռ�+100M��䣫1��+��ַ��ģ��վ+��վ��ҵ��Ϣ ��1000Ԫ �� Ǿ��Ϊ��ṩ��õķ��񡣣��ų��ʧ��Ը��˿Ҳ��Ϊ ��һ��Ĳ��ġ��ǳ�ŵ��ⰴʵ��˿ ��ף��ģ�˳�� webmaster of raeline.net webmaster(a)raeline.net ��磨��ţ��޹�˾�� --------------------------------------------------------------- �е�Ⱥ��ʼ�,��ר��(http://www.21cmm.com) ��CMM��У(http://www.21cmm.com)��Ŀ��ר��

1 0

Unbind ">>"! (was Do-notation)
by James B. White III (Trey) 30 Mar '02

30 Mar '02

Here's my short manifesto on ">>" and "do" notation. It is based on the precedent set with "negate", a precedent that I also support. ">>" should be a member of the "Monad" class, just as "negate" is a member of the "Num" class! Users should have the power to override the default definition of ">>", just as they have the power to override the default definition of "negate"! Haskell compilers should honor user definitions for ">>" and not hard-wire ">>= \_ ->", just as they should honor user definitions for "negate" and do not hardwire "0 - x"! I have fixed the December 2001 release of Hugs to follow these principles for ">>". (I haven't tested the fix exhaustively. It works on my programs. Corrections appreciated!) Here are the "diffs", before the fix followed by after: connect.h: 74c74 < extern Name nameReturn, nameBind; /* for translating monad comps */ --- > extern Name nameReturn, nameBind, nameSequence; /* for translating monad comps */ type.c: 85c85 < Name nameReturn, nameBind; /* for translating monad comps */ --- > Name nameReturn, nameBind, nameSequence; /* for translating monad comps */ 3267a3268 > nameSequence = linkName(">>"); compiler.c: 397c397 < * do { e; qs } => LETREC _h _ = [ e | qs ] in bind m exp _h --- > * do { e; qs } => sequence m e qs 433,442c433,436 < case DOQUAL : { Cell hVar = inventVar(); < Cell ld = cons(pair(singleton(WILDCARD), < transDo(m,e,qs1)), < NIL); < return ap(LETREC, < pair(singleton(pair(hVar,ld)), < ap(ap(ap(nameBind, < m), < translate(snd(q))), < hVar))); --- > case DOQUAL : { > return ap(ap(ap(nameSequence, m), > translate(snd(q))), > transDo(m,e,qs1)); --- James B. White III (Trey) Center for Computational Sciences Oak Ridge National Laboratory whitejbiii(a)ornl.gov

1 0