January 2002 - Haskell

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

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

CFP : ASIA-PEPM 2002
by Chin Wei Ngan 20 Feb '02

20 Feb '02

CALL FOR PAPERS ACM SIGPLAN ASIAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (ASIA-PEPM'02) Aizu, JAPAN, September 12-14 2002 (co-located with FLOPS2002) http://www.comp.nus.edu.sg/asia-pepm02 Submission deadline: 1st March 2002 The ASIA-PEPM'02 symposium will bring together researchers working in the areas of semantics-based program manipulation, partial evaluation, and program analysis. The symposium focuses on techniques, supporting theory, and applications for the analysis and manipulation of programs. Technical topics include, but are not limited to: * Program manipulation techniques: transformation, specialization, normalization, reflection, rewriting, run-time code generation, multi-level programming. * Program analysis techniques: abstract interpretation, static analysis, binding-time analysis, type-based analysis. * Related issues in language design and models of computation: imperative, functional, logical, constraint-based, object-oriented, parallel, concurrent, secure, domain-specific. * Programs as data objects: staging, meta-programming, incremental computation, mobility, tools and techniques, prototyping and debugging. * Applications: systems programming, scientific computing, embedded systems, graphics, security, model checking, compiler generation, compiler optimization, decompilation. Original results that bear on these and related topics are solicited. Papers investigating novel uses and applications of program manipulation are especially encouraged. Authors concerned about the appropriateness of a topic are welcome to consult with the program chair prior to submission. SUBMISSION INFORMATION Papers should be submitted electronically via the workshop's Web page. Exceptionally, submissions may be emailed to the program chair: asiapepm(a)comp.nus.edu.sg. Acceptable formats are PostScript or PDF, viewable by gv. Submissions should not exceed 5000 words, excluding bibliography and figures. Submitted papers will be judged on the basis of significance, relevance, correctness, originality, and clarity. They should clearly identify what has been accomplished and why it is significant. The work described should not have been previously published in a major forum. Authors must indicate if a closely related paper is also being considered for another conference or journal. The proceeding of the symposium will be published by ACM Press. A special issue of Higher-Order Symbolic Computation is also planned. LOCAL ARRANGEMENT Mizuhito Ogawa (NTT, Japan) GENERAL CHAIR Kenichi Asai (Ochanomizu University, Japan) PROGRAM CHAIR Wei-Ngan Chin (National University of Singapore, Singapore) PROGRAM COMMITTEE Manuel Chakravarty (University of New South Wales, Australia) Tyng-Ruey Chuang (Academia Sinica, Taiwan) Charles Consel (ENSEIRB, France) Oege de Moor (University of Oxford, UK) Masami Hagiya (University of Tokyo, Japan) Nevin Heintze (Agere Systems, USA) Neil Jones (Univ of Copenhagen, Denmark) Yanhong Annie Liu (SUNY at Stony Brook, USA) Atsushi Ohori (JAIST, Japan) Alberto Pettorossi (University of Roma, Italy) Simon Peyton Jones (Microsoft, UK) Carolyn Talcott (Stanford University, USA) Zhe Yang (University of Pennsylvania, USA)

2 1

RE: ideas for compiler project
by Simon Peyton-Jones 17 Feb '02

17 Feb '02

Lots of people have observed that Haskell might be a good "scripting language" for numerical computation. In complicated numerical applications, the program may spend most of its time in (say) matrix multiply, which constitutes a tiny fraction of the code for the application. So write the bulk of the application in Haskell (where the logic is complex but the performance doesn't matter) and then link to a C or Fortran library to do the small part that is really compute intensive. More concretly, suppose you built an FFI interface to BLAS or some readily available numerical library, and then demonstrated the utility of the resulting beast by writing some non-trivial numerical application in it. You'd need to find a "real" application though. The classical "kernels" (matrix multiply, inversion etc) are precisely the things you may not want to do in Haskell. Simon | -----Original Message----- | From: Hal Daume III [mailto:hdaume@ISI.EDU] | Sent: 22 January 2002 22:00 | To: Haskell Mailing List | Subject: ideas for compiler project | | | Hi All, | | I'm currently taking a class in compiler optimization for | high performance computing (i.e., parallel architectures, | including VLIW, FPGA, multimedia extension architectures, | systems-on-a-chip, etc). It's the second of two graduate | level compiler courses, and it purely project based. And the | project is of our choosing. | | The professor has made some suggested projects, which I could | do, but none of them are really FP specific. I'm curious if | anyone has any ideas of a project I could do. I'm looking | for something that's open, yet | constrained, etc (standard semester-long-project-course | stuff), hopefully having to do with optimizations | specifically for FPLs, or at least ones that would benefit them. | | I'm open to all ideas... | | - Hal | | -- | Hal Daume III | | "Computer science is no more about computers | hdaume(a)isi.edu | than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume | | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

6 5

Re: (no subject)
by John Hughes 25 Jan '02

25 Jan '02

> Those two constructs are not the same > Compare > newtype T1 = C1 Bool > data T2 = C2 !Bool As for as I can tell, the only difference in the Report between a newtype and a tuple type with a completely strict constructor is in the rules for pattern matching. So I am trying to find someone who can explain the reason for the difference in the rules! Right. case x of C2 b -> ... forces x, of course: matching on a datatype is always strict, and a strictness annotation on a component certainly shouldn't change that. case x of b -> ... does NOT force x: binding something to a variable is lazy. case x of C1 b -> ... does not force x either: the point of newtype is JUST to introduce a new type isomorphic to, but different from, the old, and therefore the presence or absence of the newtype constructor should have no effect at all on the evaluation of the program. Otherwise you couldn't refactor a program to distinguish between two types previously identified, without potentially changing its semantics. Of course this was a design choice, but you can't get away from the fact that the "natural" matching on T1 is lazy, and on T2 is strict. Given that, I think it's a cleaner design to have two constructs, than to make do with just data and settle for "nearly" preserving semantics when making a new type distinction. John Hughes

1 0

RE: Explicit Universal Quantification Bug?
by John Hughes 25 Jan '02

25 Jan '02

| I'm trying to learn more about Explicit Universal | Quantification so I decide to run the following supposedly | correct code from the ghc user | guide: | | >module Dummy where | > | >import ST | > | >newtype TIM s a = TIM (ST s (Maybe a)) | > | >runTIM :: (forall s. TIM s a) -> Maybe a | >runTIM t = case t of {TIM l -> runST l} Just to explain this a little more, the problem with the above is not the type of t (which is generic, as the type signature says), it's the type of l. The type of t is instantiated at the "case t of ...", let's say to TIM s' a, and the type of l is thus ST s' (Maybe a), which is NOT generic. Hence l cannot be passed to runST. The type of l cannot be generalised at the occurrence in runST l, because the type variable s' appears in the environment at that point (in the type of l itself). As you discovered, the correct way to say it is runTIM t = runST (case t of {TIM l -> l}) In this case, the (generic) type of t is instantiated as before, and the entire case expression has type ST s' (Maybe a). But this time l is not in scope (outside the case), and so the type variable s' can be generalised. Hence the case can be passed to runST. Here's another variation for you: runTIM :: (forall s. TIM s a) -> Maybe a runTIM t = let TIM l = t in runST l This one is OK, because a let binding generalises the type of the bound variable. Thus l is given the type forall s'. ST s' (Maybe a), and the call of runST types. Thus the problem with the first form above is just that a case binding doesn't generalise the types of the bound variables. As far as I know, there's no reason why it shouldn't, but that's just the way Haskell is. It's a pain, but there we are. John Hughes

1 0

RE: Explicit Universal Quantification Bug?
by Simon Peyton-Jones 25 Jan '02

25 Jan '02

| I'm trying to learn more about Explicit Universal | Quantification so I decide to run the following supposedly | correct code from the ghc user | guide: | | >module Dummy where | > | >import ST | > | >newtype TIM s a = TIM (ST s (Maybe a)) | > | >runTIM :: (forall s. TIM s a) -> Maybe a | >runTIM t = case t of {TIM l -> runST l} This is a hopeless bug in the user manual. Sorry about that. It's not there any more in any case. As you discovered, the correct way to say it is runTIM t = runST (case t of {TIM l -> l}) Simon

1 0

Re: Explicit Universal Quantification Bug?
by Rijk-Jan van Haaften 25 Jan '02

25 Jan '02

Jay Cox wrote: >I'm trying to learn more about Explicit Universal Quantification so I >decide to run the following supposedly correct code from the ghc user >guide: > > >module Dummy where > > > >import ST > > > >newtype TIM s a = TIM (ST s (Maybe a)) > > > >runTIM :: (forall s. TIM s a) -> Maybe a > >runTIM t = case t of {TIM l -> runST l} <...> >so, is this a bug? No, it is correct and expected behaviour, as I will explain below. >I noticed also the following code compiles fine. (slightly modified >from a message on this list titled "Re: Type problem with ST monad" >dating April 23, 1999 > > >module Dummy where > > > >import ST > > > >newtype TIM s a = TIM (ST s (Maybe a)) > > > >runTIM :: (forall s. TIM s a) -> Maybe a > >runTIM t = runST (deTIM t) > > > >deTIM (TIM t) = t Perfect example for explanation of the problem. The difference is between > >runTIM t = case t of {TIM l -> runST l} and > >runTIM t = runST (deTIM t) > >deTIM (TIM t) = t In the last one, after the type checker has verified that deTIM is type-correct, it can safely generalize the type of deTIM, because it is a top-level function. This means that if we have f :: a -> String f x = "Hello, world" we are allowed to apply f to an Int in one place, and to an Char in another place: g :: (String, String) g = (f 3, f 'a') This is common and well-known behaviour, and it's possible to prove that this never gives problems. However, in > >runTIM t = case t of {TIM l -> runST l} the argument 't' is non-generic. If we have the function g :: (a -> String) -> (String, String) g f = (f 3, f 'a') a problem appears. 'f' is used in a generic way, being applied to arguments of different types, which is not allowed because if we have h = f (\x -> show (x + 1)) the second part of the tupel is undefined, though this would be type-correct. This is clearly undesirable. So we have to restrict f to be non-generic. Consequently, types of variables which are derived from it must be non-generic as well. In particular this applies to 'l'. Thus, 'l' can't be generalized to fit in the type of runST. With this burden of information about generic and non-generic, we can say in short: > >runTIM t = case t of {TIM l -> runST l} is wrong because l CANNOT be generalized to fit the type of runST. > >runTIM t = runST (deTIM t) > >deTIM (TIM t) = t is correct because deTIM CAN be generalized, so it fits the type of runST Rijk-Jan van Haaften

2 1

ANNOUNCE: popenhs-1.00.0 released
by Jens Petersen 25 Jan '02

25 Jan '02

Version 1.00.0 of popenhs is out. You can get it from: http://www.01.246.ne.jp/~juhp/haskell/popenhs/ popenhs is a small library providing lazy string output from and input to a subprocess. The interface provided by "popen" now differs from the "popen3" offered in 0.00 by taking an input string argument instead of returning an input handle. Thanks to Uwe Schmidt for reporting the problem in the previous release of popen3 hanging on a closed input pipe, that led to this new implmentation, which I believe fixes the problem. Jens

1 0