January 2007 - Haskell-Cafe

ICFP07 Call for Papers
by Matthew Fluet (ICFP Publicity Chair) 17 Jan '07

17 Jan '07

Call for Papers ICFP 2007: International Conference on Functional Programming Freiburg, Germany, 1-3 October 2007 ICFP 2007 seeks original papers on the art and science of functional programming. Submissions are invited on all topics from principles to practice, from foundations to features, from abstraction to application. The scope includes all languages that encourage functional programming, including both purely applicative and imperative languages, as well as languages with objects and concurrency. Particular topics of interest include * Applications and domain-specific languages: systems programming; scientific and numerical computing; symbolic computing; artificial intelligence; databases; graphical user interfaces; multimedia programming; scripting; system administration; distributed-systems and web programming; XML processing; security * Foundations: formal semantics; lambda calculus; type theory; monads; continuations; control; state; effects * Design: algorithms and data structures; modules; type systems; concurrency and distribution; components and composition; relations to object-oriented or logic programming * Implementation: abstract machines; compile-time and run-time optimization; just-in-time compilers; memory management; parallel hardware; interfaces to foreign functions, services, components or low-level machine resources * Transformation and analysis: abstract interpretation; partial evaluation; program transformation * Software-development techniques: design patterns; specification; verification; validation; debugging; test generation; tracing; profiling * Practice and experience: novel results drawn from experience in education or industry * Functional pearls: elegant, instructive examples of functional programming A functional pearl need not report original research results, but it must be instructive, elegant, and fun. ICFP 2007 also seeks Experience Reports. An Experience Report is a short paper (2-4 pages) which need not present novel results, but which should provide evidence that functional programming really works or should describe obstacles that prevented it from working. Detailed guidelines appear below. What's new this year? ~~~~~~~~~~~~~~~~~~~~~ Experienced ICFP authors may want to pay special attention to the points below, which are new this year. * Double-blind review * Author-date citations * Supplemental material in a separate document, not appended to the main text * Morning deadline (but equivalent to late afternoon or early evening in many time zones of interest) * Experience Reports Instructions for authors ~~~~~~~~~~~~~~~~~~~~~~~~ By 11:00 AM Friday, 6 April 2007, Samoan time, submit an abstract of at most 300 words and a full paper of at most 12 pages or an Experience Report of at most 4 pages. Submissions will be accepted electronically, at a URL to be named later. The deadline is set at Samoan time, so if your submission is in by 11:00 AM Friday according to your local time, wherever you are, the submission will be on time. The world clock at http://www.timeanddate.com/worldclock/fixedtime.html?month=4&day=6&year=200… can give you the equivalent in your local time, e.g., 3:00 PM Friday in Portland, 6:00 PM Friday in Boston, and midnight Friday in Freiburg. The deadline is firm. Your submission should explain its contributions in both general and technical terms, clearly identifying what has been accomplished, explaining why it is significant, and comparing it with previous work. Make the technical content understandable to a broad audience. Each submission must adhere to SIGPLAN's republication policy, which appears in full at http://www.acm.org/sigplan/republicationpolicy.htm. The policy means in part that your paper may not have already appeared in a journal, conference, or workshop with published proceedings; that you may not submit substantially the same work simultaneously to ICFP and to another venue; and that your submission must discuss any closely related material, including your own, that was previously accepted at a journal, conference, or workshop with or without published proceedings. Full details of the policy are available at the SIGPLAN site. If you are in any doubt about whether this policy applies to your paper, either consult the program chair in advance or notify the chair when you submit. To do otherwise risks summary rejection of your submission. If your submission is accepted, you must assign copyright to ACM. Proceedings will be published by the ACM Press. Double-blind review ~~~~~~~~~~~~~~~~~~~ To increase confidence in the fairness and objectivity of the reviewing process, reviewing will be double blind. Make it possible for reviewers to evaluate your paper without having to know who you are. It should suffice to omit your names from your submission and to avoid revealing your identity through citation; detailed guidelines are available at http://icfp07.eecs.harvard.edu/blind.html. Formatting ~~~~~~~~~~ Your submission must be printable on US Letter sized paper and be either PDF or PostScript that is interpretable by Ghostscript. If this requirement is a hardship, make contact with the program chair at least one week before the deadline. Your submission must be at most 12 pages (4 pages for an Experience Report), including bibliography and figures, in the 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). (A suitable LaTeX class file is available from SIGPLAN; see http://www.acm.org/sigs/sigplan/authorInformation.htm. Categories, keywords, and so on are optional.) If you wish to supply material beyond the 12-page limit, up to and including a full technical report, you may attach a separate document to your submission, on the understanding that reviewers are not expected to read it. (As a particular example, if you feel that your submission should be supported by a lengthy technical report, do not cite such a technical report on the web, since doing so would reveal your identity. Please instead attach that report to your submission.) Detailed instructions for attaching supplementary documents will be available on the submission web site. The length limit is firm; submissions that do not meet these guidelines will not be considered. Citation ~~~~~~~~ We recommend (but do not require) that you put your citations into author-date form. This procedure makes your paper easier to review. For example, if you cite a result on testing as ``(Claessen and Hughes 2000)'', many reviewers will recognize the result instantly. On the other hand, if you cite it as ``[4]'', even the best-informed reviewer has to page through your paper to find the reference. By using author-date form, you enable a knowledgeable reviewer to focus on content, not arbitrary numbering of references. LaTeX users can simply use the natbib package along with the plainnat bibliography style. Author response ~~~~~~~~~~~~~~~ You will have a 48-hour period (11:00 23 May to 11:00 25 May 2007 Samoa time) to read and respond to reviews. Details of the author-response process will be available as it approaches. Special categories of papers ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ In addition to research papers, ICFP solicits two kinds of papers that do not require original research contributions: functional pearls, which are full papers, and Experience Reports, which are limited to four pages. Authors submitting such papers may wish to consider the following advice. Functional pearls ~~~~~~~~~~~~~~~~~ To paraphrase both Jon Bentley and Richard Bird, the ideal pearl goes beyond solid engineering into the realm of insight and creativity. Just as a natural pearl grows from a grain of sand that has irritated an oyster, a topnotch functional pearl should grow from a real problem that has irritated a programmer. A pearl should be polished, elegant, instructive, and entertaining. Ideally it should teach important programming techniques and fundamental design principles. Past pearls have included instructive examples of program calculation or proof, nifty presentations of old or new data structures, and interesting applications and programming techniques. Papers submitted to ICFP as pearls often miss the mark, by being too trivial, too complicated, or somehow not quite the elegant solution one hopes for. The key to an accepted pearl is polishing. Your pearl is likely to be rejected if your readers get bored, if the material gets too complicated, if too much specialized knowledge is needed, or if the writing is distasteful. Richard Bird advises: * Throw away the rule book for writing research papers. * Get in quick; get out quick. * Be self-contained; don't go deep into related work, with lengthy references. * You are telling a story, so some element of surprise is welcome. * Above all, be engaging. * Give a talk on the pearl to non-specialists, your students, or your department. If you changed the order of presentation for the talk, consider using the new order in the next draft. * Put the pearl away for a while, then take it out and polish it again. Experience reports ~~~~~~~~~~~~~~~~~~ ICFP has long solicited submissions on the practice and experience of functional programming. But reports of experience are inherently different from research papers, and when judged by the criteria of scientific merit, novelty, or research contribution, they have not competed well against traditional ICFP submissions. Yet we believe that the functional- programming community would benefit from being able to draw on and cite the experience of others. For this reason, we have introduced the ICFP Experience Report. Unlike a normal ICFP paper, the purpose of an Experience Report is not to add to the body of knowledge of the functional-programming community. Rather, the purpose of an Experience Report is to help create a body of published, refereed, citable *evidence* that functional programming really works---or to describe obstacles that prevented it from working. An Experience Report is distinguished from a normal ICFP paper by its title, by its length, and by the criteria used to evaluate it. * Both in the proceedings and in any citations, the title of each accepted Experience Report must begin with the words "Experience Report", followed by a colon. * Experience Reports are limited in length: the suggested length is 2 pages and the maximum length is 4 pages. Each accepted Experience Report will be presented at the conference, but depending on the number of Experience Reports and regular papers accepted, authors of Experience Reports may be asked to give shorter talks. * Because the purpose of Experience Reports is to enable our community to accumulate a published, citable body of evidence about the efficacy of functional programming, an acceptable Experience Report need not present novel results or conclusions. It is sufficient if the Report states a clear thesis and provides supporting evidence. The thesis must be relevant to ICFP, but it need not be novel. The program committee will accept or reject Experience Reports based on whether they judge the evidence to be convincing. Anecdotal evidence will be acceptable provided it is well argued and the author explains what efforts were made to gather as much evidence as possible. The committee will be especially convinced by evidence that includes *comparisons* of situations before and after the introduction or discontinuation of functional programming. Evidence drawn from a single person's experience may be sufficient, but more weight will be given to evidence drawn from the experience of groups of people. Possible topics for an Experience Report include, but are not limited to * Insights gained from real-world projects using functional programming * Comparison of functional programming with conventional programming in the context of an industrial project or a university curriculum * Project-management, business, or legal issues encountered when using functional programming in a real-world project * Curricular issues encountered when using functional programming in education * Real-world constraints that created special challenges for an implementation of a functional language or for functional programming in general An Experience Report should be short and to the point: if functional programming worked for you in the same ways it has worked for others, you need only to summarize the results---the main part of your paper should discuss how well it worked and in what context. Most readers will not want to know all the details of your project and its implementation, but please characterize your project and its context well enough so that readers can judge to what degree your experience is relevant to their own projects. Be especially careful to highlight any unusual aspects of your project. Also keep in mind that specifics about your project are more valuable than generalities about functional programming; for example, it is more valuable to say that your team delivered its software a month ahead of schedule than it is to say that functional programming made your team more productive. If your paper not only describes experience but also presents new technical results, or if your experience refutes cherished beliefs of the functional-programming community, you may be better off submitting it as a full paper, which will be judged by the usual criteria of novelty, originality, and relevance. If you unsure in which category to submit, the program chair will be happy to help you decide. Other information ~~~~~~~~~~~~~~~~~ Conference Chair ~~~~~~~~~~~~~~~~ Ralf Hinze (Universität Bonn) Program Chair ~~~~~~~~~~~~~ Norman Ramsey Harvard University Cambridge, MA, 02148 USA Email: icfp07(a)eecs.harvard.edu Phone: +1 617 496 8615 Mail sent to the address above is filtered for spam. If you send mail and do not receive a prompt response, particularly if the deadline is looming, feel free to telephone and reverse the charges. Program Committee ~~~~~~~~~~~~~~~~~ Nick Benton (Microsoft Research) Matthew Fluet (Toyota Technological Institute) Jeremy Gibbons (University of Oxford) Kevin Hammond (University of St Andrews) Bastiaan Heeren (Utrecht University) Graham Hutton (University of Nottingham) Mark P. Jones (Portland State University) Gabriele Keller (University of New South Wales) Fabrice Le Fessant (INRIA/LIX, France) Todd Millstein (UCLA) Mike Sperber (DeinProgramm) Christopher A. Stone (Harvey Mudd College) Andrew Tolmach (Portland State University and INRIA Rocquencourt) Janis Voigtländer (Technische Universität Dresden) Stephanie Weirich (University of Pennsylvania) Important Dates ~~~~~~~~~~~~~~~ Submission: 11:00 6 April 2007, Samoa time (AST) Author response: 11:00 23 May to 11:00 25 May 2007 (AST) Notification: 8 June 2007 Final papers due: 20 July 2007 ICFP 2007 Web Site ~~~~~~~~~~~~~~~~~~ http://www.informatik.uni-bonn.de/~ralf/icfp07.html Special Issue of JFP ~~~~~~~~~~~~~~~~~~~~ Authors of the best final papers, as determined by the program committee, will be invited to submit journal versions for a special issue of the Journal of Functional Programming.

1 0

Default (or empty) values
by Max Vasin 17 Jan '07

17 Jan '07

Hello all! Let > data Book = Book { > authors :: [String], > title :: String, > editor :: Maybe String, > edition :: Maybe String, > volume :: Maybe (Int, Int), -- e.g. volume 1 of 3 > publisher :: String, > year :: Int, > pages :: Int > } and > convertBook :: Map String String -- a map from field names to values (string representation) > -> Maybe Book convertBook takes info about book from some external source (e.g. a BibTeX database) and returns Just book value or Nothing (if convertion failed). Fields of the Book datatype which are not (Maybe a) are required to be present. convertBook looks like > convertBook = (rq "title" (\b v -> b { title = v }) <.> > rq "publisher" (\b v -> b { publisher = v }) <.> > ... ) (Just $ Book [] "" Nothing Nothing Nothing "" 0 0) I don't like the `(Just $ Book [] "" Nothing Nothing Nothing "" 0 0)' part, I would prefer instead someting like `empty :: Book'. So I define > class Empty e where > empty :: e But still I have to emplement instances by hand. There are a number of approaches to automatically derive instances (TH, generic classes in GHC, drift). What would you recommend using in this case? Or may be it would be better to drop out Empty and use something else? TIA -- WBR, Max Vasin.

4 8

Re: [Haskell-cafe] Re: Newbie: Project: Missionary and Cannibal [Contd].
by thapaps＠gmail.com 17 Jan '07

17 Jan '07

thank you very much for all your Help. I am finally able to do something (O: I watched the video presentation from Edsge W. Dijkstra. It is very helpful. thank you once again for providing me the link. I am trying to call a function and print a message. moveLoadR :: Int -> Int -> (IO ()-> a) moveLoadR m c | m==0 && c==0 = moveEndR $ putStrLn "END" | otherwise = moveLoadR (m-1) (c-1) $ putStrLn "Starting Missionary and Cannibal Game.\nLeft Bank: Missionary=3:Cannibal=3: Moving From: Left ===> Right: Missionary=1 Cannibal=1 \n" moveEndR :: (IO ()->a) moveEndR = putStrLn"END OF Solution" <<< === THIS IS INCORRECT. I tried doing this . but it will take me to the infinite Loop. moveEndR :: (IO ()->a) moveEndR = moveEndR $ putStrLn"END OF GAME" Any help in this would be greatly appreciated. . On 1/16/07, Paul Johnson <paul(a)cogito.org.uk> wrote: > > This is presumably your homework. See > http://www.haskell.org/haskellwiki/Homework_help > > This kind of problem is often solved by using the List monad, so try > looking at that first. > > Failing that, have a list of moves to make a sequence. Then make a list > of all possible sequences. Then filter out the ones that break the > rules. Whatever is left is the answer you want. > > Paul. > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

Haskell category (was: Article review: Category Theory)
by Peter Berry 16 Jan '07

16 Jan '07

On 16/01/07, David House <dmhouse(a)gmail.com> wrote: > I'd love comments from newcomers and experts alike regarding my > approach, the content, improvements and so on. Of course, it's on the > wikibook, so if you have anything to add (that's not _too_ substantial > otherwise I'd recommend discussion first) then go ahead. Interesting timing for me :) I was going to post about category theory as well, but my motivation is the opposite - I'd like to ask about it. (I've changed the subject since this ought to be a separate thread.) My final year undergraduate project involves defining the semantics of a memoization function in Haskell using category theory, so of course I've been trying to figure out exactly what the Haskell category consists of. I've put a summary of my thoughts at http://sucs.org/~pwb/cats.txt . I'd appreciate comments, criticism, etc. -- Peter Berry <pwberry(a)gmail.com> Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html

1 0

Laziness through boxing
by C Rodrigues 16 Jan '07

16 Jan '07

I had a problem with strictness in the Parsec library, and I'd like to know if there's a good way to solve it. The following illustrates the problem. This raises an error when run: main = parseTest (return undefined >> return 0) "" Whereas this does not: main = parseTest (return (Just undefined) >> return 0) "" I have a parser that does parsing and name resolution at the same time, by passing the completed symbol table in as a part of the parser state. Lookups into the completed symbol table have to be lazy since that symbol table is not ready until parsing is complete. My parser kept producing <<loop>> when it ran, which turned out to be an effect of strictness in Parsec. My solution was to box all the lazy values with Just. The result feels awkward to me. It involves fromJust, and moreover, it's easy to miss a place where boxing is required, and hard to track down the cause of a <<loop>>. Is there a better way to deal with this issue? And why is Parsec strict in return values? -Chris _________________________________________________________________ >From photos to predictions, The MSN Entertainment Guide to Golden Globes has it all. http://tv.msn.com/tv/globes2007/?icid=nctagline1

2 1

Re: Newbie: Project: Missionary and Cannibal
by Paul Johnson 16 Jan '07

16 Jan '07

This is presumably your homework. See http://www.haskell.org/haskellwiki/Homework_help This kind of problem is often solved by using the List monad, so try looking at that first. Failing that, have a list of moves to make a sequence. Then make a list of all possible sequences. Then filter out the ones that break the rules. Whatever is left is the answer you want. Paul.

1 0

Higher kinds (and impredicativity?)
by Jim Apple 16 Jan '07

16 Jan '07

Why is this declaration ill-formed: data Bad t where Bad :: Bad (forall (f :: * -> *) . f) GHC 6.6 says: `f' is not applied to enough type arguments Expected kind `*', but `f' has kind `* -> *' In the type `forall f :: (* -> *). f' In the type `Bad (forall f :: (* -> *). f)' In the data type declaration for `Bad' I suppose this is because the kind inference rule is C, x : k1 |- y : * ----------------------- C |- (\forall x : k1 . y) : * I'd expect C, x : k1 |- y : k2 ----------------------- C |- (\forall x : k1 . y) : k2 Is there a foundational or an implementation reason for this restriction? Jim

2 4

Newbie: Project: Missionary and Cannibal in Haskell
by thapaps＠gmail.com 16 Jan '07

16 Jan '07

I am very new to haskell. my project is to solve Missionary and Cannibal this is what I have been given : 1. 3 Missionary and 3 Cannibal . 2. 1 boat. 3. Max passengers=2. 4. RULE: at any given time number of cannibal cannot exceed number of missionary 5. I need to move all the missionary and cannibal from one bank to the other. I am really confused as to how to proceed to solving this problem. based on 2 passenger I can come of with five different boat loads. this would lead to five different combination at each state. how would i preserve the previous state value and pass it to the next state, What would be the best way to tackle this problem? any direction any help in this will be highly appreciated.

2 1

Redefining superclass default methods in a subclass
by Brian Hulley 15 Jan '07

15 Jan '07

Hi, Looking at some of the ideas in http://www.haskell.org/haskellwiki/The_Other_Prelude , it struck me that the class system at the moment suffers from the problem that as hierarchies get deeper, the programmer is burdened more and more by the need to cut-and-paste method definitions between instances because Haskell doesn't allow a superclass (or ancestor class) method default to be redefined in a subclass. For example, consider this part of a proposal for Functor => Applicative => Monad: -- I've just used 'm' so it's easy to see what parts are relevant to Monad class Functor m where fmap :: (a -> b) -> m a -> m b class Functor m => Applicative m where return :: a -> m a (<*>) :: m (a -> b) -> m a -> m b (>>) :: m a -> m b -> m b ma >> mb = -- left as exercise for a rainy day! class Applicative m => Monad m where (>>=) :: m a -> (a -> m b) -> m b The problem with this is that whereas someone defining a Monad at the moment only needs to define (return) and (>>=), with the above, though it gives obvious advantages in flexibility, generality etc, defining a new Monad involves providing methods (in instance decls) for fmap and (<*>) as well, and the default method for (>>) is ma >> mb = (fmap (const id) ma) <*> mb (from that page above) which I'm sure everyone will agree is a *lot* more complicated than: ma >> mb = ma >>= (\_ -> mb) Not only is the first definition for (>>) more complicated, it obscures the simple fact that for monads it's just a trivial special-use case of >>= where the bound argument is ignored. Therefore I'm wondering if it would be possible to allow default methods for a superclass to be defined, or redefined, in a subclass, so we could write: class Applicative m => Monad m where (>>=) :: m a -> (a -> m b) -> m b mf <*> ma = mf >>= \f -> ma >>= \a -> return (f a) ma >> mb = ma >>= \_ = -> mb fmap f ma = ma >>= \a -> return (f a) (I know the above can be written in a more point-free style but I wrote it like that to make it easy to understand what's happening.) The essential point here (excuse the pun :-) ) is that it is impossible to write the default methods in the class in which the operation is defined, because the implementation depends on methods of the relevant subclass (and will therefore be different for different subclasses though not for each particular instance of a given ancestor class of a particular subclass). As Haskell stands at the moment, we are forced to cut and paste identical methods for each individual instance of each ancestor class of a particular subclass because we can't override an ancestor class method in the *class* decl for a subclass. The type class system at present is based on the idea that you can define related methods together and in terms of each other, at one level of the hierarchy. However as the above example shows, related methods sometimes need to be spread over the hierarchy but we still want to be able to define default implementations of them in terms of each other. Perhaps there is some reason this can't be done? Brian. -- http://www.metamilk.com

6 10

Re: [Haskell-cafe] Higher kinds (and impredicativity?)
by Jim Apple 15 Jan '07

15 Jan '07

On 1/15/07, Doaitse Swierstra <doaitse(a)cs.uu.nl> wrote: > Values that live as elements in data have to be data themselves, and > thus have to be of a type that has kind *. But the example I give doesn't have a "value" of kind * -> * living in data. The constructor is nullary, only the parameter to the type is not of kind *. This is fine in declarations like: data Good (x :: * -> *) where Good :: Good Maybe What I'm asking is why, for declarations like data OK (x :: * -> *) where OK :: OK x type Fine = OK Maybe type Evil = OK (forall (f :: * -> *) . f) Fine is allowed, while Evil is not. This is not the case for data OK' (x :: *) where OK' :: OK' x type Fine' = OK' Maybe type Evil' = OK' (forall (f :: *) . f) When both Fine' and Evil' are accpeted. Jim > On Jan 15, 2007, at 3:39 AM, Jim Apple wrote: > > > Why is this declaration ill-formed: > > > > data Bad t where > > Bad :: Bad (forall (f :: * -> *) . f) > > > > GHC 6.6 says: > > > > `f' is not applied to enough type arguments > > Expected kind `*', but `f' has kind `* -> *' > > In the type `forall f :: (* -> *). f' > > In the type `Bad (forall f :: (* -> *). f)' > > In the data type declaration for `Bad' > > > > I suppose this is because the kind inference rule is > > > > C, x : k1 |- y : * > > ----------------------- > > C |- (\forall x : k1 . y) : * > > > > I'd expect > > > > C, x : k1 |- y : k2 > > ----------------------- > > C |- (\forall x : k1 . y) : k2 > > > > Is there a foundational or an implementation reason for this > > restriction? > > > > Jim

1 1