February 2003 - Haskell

Enum on Float/Double
by George Russell 23 Oct '03

23 Oct '03

The situation with Enum on Ratio is pretty bad but at least it's not hopeless, since rational numbers are at least exact. But for Float/Double it seems to be a total disaster area. Since it seems to be impossible to abolish Enum Float/Double altogether, would it at least be possible to make it rather more useful, by making succ x return the next representable float after x (or x if x is non-finite) and pred x the previous representable float. This would (a) be useful; (b) make mathematical sense; (c) is tricky to implement with the existing primitives. Before someone else points it out, this is of course unimplementable should someone in the future implement infinite-precision reals in Haskell, but as (barring a solution to the halting problem) Eq would be as well, that does not bother me. My preference would be for succ (+-0) to return the smallest positive real, since then you could define succ x to be the unique y with x < y and forall z . z < y => not (x < z), where such a y exists, and I'm not sure if the Haskell standard knows about signed zeros. Feri wrote > Everybody working with floats should know their quirks While in an ideal world, everyone who represented a mouse position or anything else as a float should have a PhD in numerical analysis, in practice they do not. Indeed I think the Haskell Library Report contains quite a few examples of floating point code which a numerical analyst would have written rather better. So I don't think it's good enough to treat every Float/Double operation as if it had an implicit "UNSAFE" flag indicating that the compiler was entitled to wierd behaviour only comprehensible to experts, as seems to be the case with floating enumerations now.

8 11

RE: fundeps for extended Monad definition
by Simon Peyton-Jones 05 Mar '03

05 Mar '03

Interesting example | class Monad2 m a ma | m a -> ma, ma -> m a where | return2 :: a -> ma | bind2 :: Monad2 m b mb => ma -> (a -> mb) -> mb | _unused :: m a -> () | _unused = \_ -> () | instance Monad2 [] a [a] where | bind2 = error "urk" The functional dependencies say m a -> ma Instantiating this with the instance declaration instance Monad2 [] a [a] we can deduce that given any constraint (Monad2 t1 t2 t3), if t1 = [], then t3 must be [t2] In the instance declaration, we instantiate the type of bind2 to get the type of bind2 needed for this particular instance declaration: bind2 :: forall b mb. Monad2 [] b mb => ma -> (a -> mb) -> mb Now the rule above says "that means mb must be [b]" and that gives rise to the error. GHC is consistent about this --- if you don't supply an defn for bind2, it makes one up, and complains in more or less the same way. Here's a less complicated variant of the same problem: class C a b | a -> b where {} instance C Int Int where {} f :: (C Int b) => Int -> b f x = x Is the defn of f legal? Both GHC and Hugs reject it because the inferred type of f is more like C Int Int => Int -> Int Functional dependencies tell us that 'b' must be Int, so in fact the two types are equivalent. In this example the programmer could write the 'correct' type, but in your case you can't because the type signature arises by instantiating the one in the class declaration. I'm really not sure what to do about this. GHC has an excellent way of keeping me honest in type-checking: the type checker has to produce a translation of the program into the (typed) core language. What could f's translation look like. It must presumably be f (d::C Int Int) (x::Int) = x giving f the type f :: C Int Int -> Int -> Int Another translation could be f b (d::C Int b) (x::Int) = x (the 'b' is a type variable, a big-lambda binding) giving f the type f :: forall b. C Int b -> Int -> Int But what I *cannot* get is the type f : forall b. C Int b -> Int -> b how could I write the term? f b (d:: C Int b) (x::Int) = ????? I suppose I could use (unsafeCoerce x) as the RHS, which amounts to saying "in every call to f, b will be Int, so we know that the coercion is safe". But that is a scarily global property. For example, if a call site of f does not "see" the instance declaration, it might call f with an argument of type (C Int Bool) or something. Nor can I see an easy way to insert the 'right' coercions in general. Bottom line: excellent point, but I can't see how to fix it. Maybe there are some fundep experts out there who can guide us through the swamp? Simon

3 3

int to float problem
by Mike T. Machenry 03 Mar '03

03 Mar '03

Hello, I am having a problem. I recently desided I wanted a bunch function to return float instead of Int. I changed their type and wrote a new function that returned a float. I figured it'd be okay if all the others still returned Int since it's trivial to convert Int to Float. Sadly Haskell won't let me do this. What should I do? I attempted to cast all of the values in the functions that returned Int to Float, but I found no way to do this. I found fromInteger but it didn't seem to work on the return value of the cardinality function for instance. I guess cardinality much return Int. This is one of my functions. smallestSet :: GameState -> Float smallestSet s = (-1 * cardinality (fLocations s)) This function is an error because it infer's an Int. Thanks, -mike

6 6

RE: fundeps for extended Monad definition
by oleg＠pobox.com 28 Feb '03

28 Feb '03

Hello! Simon Peyton-Jones wrote: > class C a b | a -> b where {} > instance C Int Int where {} > f1 :: (forall b. (C Int b) => Int -> b) > f1 x = undefined Indeed, this gives an error message Cannot unify the type-signature variable `b' with the type `Int' Expected type: Int Inferred type: b The reason, which is thoroughly explained in Simon Peyton-Jones' message, is that the given type signature is wrong: it should read f1 :: (exists b. (C Int b) => Int -> b) Alas, 'exists' is not an allowed type quantifier. Not explicitly that is. We can get 'exists' if we use the permitted 'forall' in a negative position (aka in an existential type). The following code > class C a b | a -> b where {} > instance C Int Int where {} > newtype M a = M (forall b.(C a b) => b) > f :: Int -> M Int > f x = M undefined typechecks in both Haskell compilers. Hal Daume's original example works as well: > newtype MM2 m a = MM2 (forall mb.(Monad2 m a mb) => mb) > class Monad2 m a ma | m a -> ma, ma -> m a where > return2 :: a -> ma > bind2 :: ma -> (a -> (MM2 m a)) -> (MM2 m a) > unused :: m a -> () > unused = \_ -> () > instance Monad2 [] a [a] where > bind2 = error "urk" Again, it typechecks both in Hugs and GHC.

2 3

One-month alert to ICFP submission deadline
by Olin Shivers 28 Feb '03

28 Feb '03

The submission deadline for ICFP -- the International Conference on Functional Programming -- is coming up soon: Saturday, March 29, which is four weeks away. The 2003 ICFP will be in Uppsala, Sweden on August 25-29, in conjunction with PPDP (Principles and Practice of Declarative Programming). Please take a moment to read the "call for papers" I've appended below, and see if you have a topic or result you would like to submit to the program committee. Please forward this notice to any relevant internal mailing lists, as well. See you in Sweden. -Olin Shivers program chairman =============================================================================== Eighth Annual ACM SIGPLAN International Conference on Functional Programming ICFP 2003 Call for Papers (Revised 2003/2/5) Affiliated with PLI 2003 August 25-29, 2003 Uppsala, Sweden http://www-users.cs.york.ac.uk/~colin/icfp2003.html http://www.cc.gatech.edu/icfp03/cfp.html ------------------------------------------------------------------------------- * Important dates ----------------- Submission deadline 18:00 EST 29 March, 2003 (Saturday) Notification of acceptance rejection 19 May, 2003 Final paper due 16 June, 2003 Conference 25-29 August, 2003 * Scope ------- ICFP 2003 seeks original papers on the full spectrum of the art, science, and practice of functional programming. The conference invites submissions on all topics ranging from principles to practice, from foundations to features, and from abstraction to application. The scope covers all languages that encourage programming with functions, including both purely applicative and imperative languages, as well as languages that support objects and concurrency. Topics of interest include, but are not limited to, the following: Foundations formal semantics, lambda calculus, type theory, monads, continuations, control, state, effects. Design Algorithms and data structures, modules and type systems, concurrency and distribution, components and composition, relations to object-oriented and logic programming, multiparadigm programming. Implementation abstract machines, compile-time and run-time optimization, just-in-time compilers, memory management. Interfaces to foreign functions, services, components and low-level machine resources. Transformation and analysis abstract interpretation, partial evaluation, program transformation, theorem proving, specification and verification. Software development techniques for functional programming design patterns, specification, verification and validation, debugging, test generation, tracing and profiling. Applications and domain-specific languages systems programming, scientific and numerical computing, symbolic computing and artificial intelligence, systems programming, databases, graphical user interfaces, multimedia programming, application scripting, system administration, distributed-systems construction, web programming. Practice and experience functional programming in education and industry, ramifications on other paradigms and computing disciplines. Functional pearls elegant, instructive examples of functional programming. Papers in the latter three categories need not necessarily report original research results; they may instead, for example, report practical experience that will be useful to others, re-usable programming idioms, or elegant new ways of approaching a problem. The key criterion for such a paper is that it makes a contribution from which other practitioners can benefit. It is not enough simply to describe a program! * Submission guidelines ----------------------- Due date & time: Submissions must be filed at the web site by 18:00 EST on Saturday 29 March. Some convenient equivalents to 18:00 EST are New York: 6:00 PM = 18h00 San Francisco: 3:00 PM = 15h00 Chicago: 5:00 PM = 17h00 Paris: Midnight Hong Kong: 7:00 AM (30 March) UTC: 2300 For other time-zones/locations, see http://www.timeanddate.com/worldclock/fixedtime.html Submission URL: http://www.cc.gatech.edu/icfp03/submit Authors should submit a 100-200 word abstract and a full paper by 23:00 Universal Coordinated Time on Saturday, 29 March, 2003. Submissions should be no more than 12 pages (including bibliography and appendices) in standard ACM conference format: two columns, nine-point font on a ten-point baseline, with pages 20pc (3.33in) wide and 54pc (9in) tall, with a column gutter of 2pc (0.33in). Detailed formatting guidelines are available at http://www.acm.org/sigs/pubs/proceed/template.html, along with formatting templates or style files for LaTeX, Word Perfect, and Word. You don't need to include categories, keywords, etc., though you are welcome to do so. Also, note that the ACM copyright notice is not required of submissions, only of accepted papers. Authors wishing to supply additional material to the reviewers beyond the 12-page limit can do so in clearly marked appendices, on the understanding that reviewers are not required to read the appendices. Submissions that do not meet these guidelines will not be considered. The submission deadline and length above are firm. Submissions will be carried out electronically via the Web, at the URL given above. Papers must be submitted in either PDF format, or as PostScript documents that are interpretable by Ghostscript, and they must be printable on US Letter sized paper. Individuals for which this requirement is a hardship should contact the program chair at least one week before the deadline. Submitted papers must have content that has not previously been published in other conferences or refereed venues; simultaneous submission to other conferences or refereed venues is unacceptable. Each paper should explain its contributions in both general and technical terms, clearly identifying what has been accomplished, saying why it is significant, and comparing it with previous work. Authors should strive to make the technical content of their papers understandable to a broad audience. Authors of accepted papers will be required to sign the ACM copyright form. Proceedings will be published by ACM Press. * Student Attendees ------------------- Students who have a paper accepted for the conference are offered student membership of SIGPLAN free for one year. As members of SIGPLAN they may apply for travel fellowships from the PAC fund. * Conference Chair ------------------ Colin Runciman University of York, UK * Program Chair --------------- Olin Shivers College of Computing Georgia Institute of Technology Atlanta, Ga. 30332-0280, USA shivers at cc.gatech.edu Phone: +1 404 385.00.91 Fax: +1 404 383.12.53 * Program Committee ------------------- Andrzej Filinski (DIKU, University of Copenhagen) Robby Findler (University of Chicago) Fritz Henglein (IT University of Copenhagen) Hugo Herbelin (INRIA) Ralf Hinze (Universität Bonn) Annie Liu (Stony Brook University) Benjamin Pierce (University of Pennsylvania) Todd Proebsting (Microsoft Corp.) Amr Sabry (University of Indiana) Zhong Shao (Yale University) Tim Sheard (OGI School of Science and Engineering) Eijiro Sumii (University of Tokyo) Andrew Wright (Cisco, Critical Infrastructure Assurance Group) * Accessing this document ------------------------- This document can be obtained in the following formats: HTML http://www.cc.gatech.edu/icfp03/cfp.html PostScript http://www.cc.gatech.edu/icfp03/cfp.ps PDF http://www.cc.gatech.edu/icfp03/cfp.pdf Plain text http://www.cc.gatech.edu/icfp03/cfp.txt * Change log ------------ 2003/2/5 Added program committee; revised submission deadline from 3/20 to 3/29; updated student travel-fellowship information. 2003/2/5 March 29 is Saturday, not Thursday. (March 20 is a Thursday.) 2003/2/7 Added Andrew Wright to PC list. 2003/2/9 Added URLs for accessing the CFP in various formats.

1 0

Anyone calculating Nash or Wardrop equilibria in Haskell?
by Steffen Mazanek 28 Feb '03

28 Feb '03

Hello. Haskells declarativity is really useful to transform mathematical models into data types and algorithms. In the context of a seminary I have dealt with equilibria concepts (especially Nash and Wardrop equilibrium) in loss networks. (based on "Non-cooperative routing in loss networks" by Altman et al.) Thereby I have noticed that some algorithms are very easy to implement in Haskell, e.g. the state space or the blocking probability. Surely these algorithms are not efficient, they should just do their jobs. On the other hand there are algorithms, too, which appear to be really hard and long winded to implement, e.g. the equilibria by itself. My question: Is there an elegant way of programming a numerical solver of problems like "given the conditions ... find a solution which minimizes/maximizes the following function ...". Presumably there is no such "way" in general, but maybe someone can give a hint, how to tackle these kinds of problems. Or maybe there are some libraries doing this job. Thanks in advance and best greetings. Steffen Mazanek

1 0

RE: Happy Alex
by Simon Marlow 28 Feb '03

28 Feb '03

> I have successfully used the the excellent haskell tools > Happy and Alex in a > couple of parsing projects, but I have failed when trying to > combine a > monadic Happy grammar (using the %monad and %lexer > directives) together with > an Alex generated okenizer, nor are there any such examples > in the Happy and > Alex distributions. Have anyone tried this combination and > can give me some > advice or a simple example? I've been doing some work on Alex recently, and getting it to work smoothly with Happy's monadic scheme is one of the goals. I'll post something when it's done, but if you want to have a look at the work-in-progress look in the CVS tree, under fptools/happy/alex on the branch simonm-hackery-branch. The other things I'm doing include making Alex's syntax more lex-like and Happy-like (mostly done), making the generated code more efficient in terms of both space and time (mostly done), and adding support for Unicode (not done, I'm still thinking about how best to do this - I have some ideas but suggestions are welcome). Cheers, Simon

1 0

Happy Alex
by Per Larsson 28 Feb '03

28 Feb '03

I have successfully used the the excellent haskell tools Happy and Alex in a couple of parsing projects, but I have failed when trying to combine a monadic Happy grammar (using the %monad and %lexer directives) together with an Alex generated okenizer, nor are there any such examples in the Happy and Alex distributions. Have anyone tried this combination and can give me some advice or a simple example? -- Per

1 0

RE: fundeps known beforehand (was RE: fundeps for extended Monad definition)
by Simon Peyton-Jones 28 Feb '03

28 Feb '03

| since this claims that it will take a Bool and produce a value of type b | for all types b. However, would it be all right to say (in | pseudo-Haskell): | | > f :: exists b . Bool -> b | > f x = x But this is a singularly useless function, because it produces a result of utterly unknown type, so you can't actually use it. For example you could not say f x + 4 Simon

1 0

Announce: Haskell Data Clustering
by Hal Daume III 27 Feb '03

27 Feb '03

Hi all, I've had some software which implements a variety of unsupervised learning (aka clustering) algorithms around for some time, but finally got around to making the source code available. I thought some people on this list might find it of interest, so I include a pointer which explains how it is used: http://www.isi.edu/~hdaume/GDC/ Happy clustering! - Hal -- Hal Daume III | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume

1 0