January 2008 - Haskell-Cafe

Re: [Haskell-cafe] Has character changed in GHC 6.8?
by Miguel Mitrofanov 22 Jan '08

22 Jan '08

> > chr . ord $ 'å' > '\229' > What would I have to do to get an 'å' from '229'? It seems you already have it; 'å' is the same as '\229'. But IO output is still 8-bit, so when you ask ghci to print 'å', you get '\229'. You can use utf-string library (from hackage).

2 1

non-alphabetical mathematical symbols as non-infix function names
by Cetin Sert 22 Jan '08

22 Jan '08

(¬) :: Bool → Bool (¬) q = not q q = True ¬ q : parser error on input q ¬ : parser error (possibly incorrect indentation) (¬ q) : Couldn't match expected type `Bool -> t' against inferred type `Bool' In the expression: (� True) In the definition of `it': it = (� True) * (q ¬) : False (Why) is it not possible to define a (non-infix) function whose name consists of a single non-alphabetical mathematical symbol? ¬ :: Bool → Bool -- parser error on input ** ¬ q = not q -- parser error on input ** Cetin Sert

3 2

Hamming's Problem
by Jose Luis Reyes F. 22 Jan '08

22 Jan '08

Hi, In exercise 2 of http://www.walenz.org/Dijkstra/page0145.html we need to write a function that holds (1) The value 1 is in the sequence (2) If x and y are in the sequence, so is f(x,y), where f has the properties a. f(x,y) > x b. (y1 > y2) => (f(x,y1)>f(x,y2)) This is a solution for this problem, but an inefficient one hammingff :: [Integer] hammingff = 1 : merge [ h x y | x <- hammingff, y <- hammingff ] [ h x y | y <- hammingff, x <- hammingff ] h x y = 2*x+3*y merge :: (Ord a) => [a] -> [a] -> [a] merge [] xs = xs merge ys [] = ys merge (x:xs) (y:ys) = case compare x y of LT -> x : merge xs (y:ys) GT -> y : merge (x:xs) ys EQ -> x : merge xs ys anybody has a better solution?. Thanks Jose

5 7

Yi and Data.ByteString
by Cetin Sert 22 Jan '08

22 Jan '08

1) Can anyone tell me how I can build Yi or point me to a binary release of that editor? I tried to follow the instructions on http://www.nobugs.org/developer/yi/building.html but got a missing component error each time. 2) When if ever is Data.ByteString going to be the default string representation in GHC? I study computational linguistics and plan to switch to Haskell in the near future, that is once I get to grips with the language and the whole new thought model one has to develop as an imperative programmer. Best Regards, Cetin Sert www.corsis.de

6 8

Haskell web dev: Using Haskell and HAppS for Openomy API v2.0
by Don Stewart 22 Jan '08

22 Jan '08

A deployment of HAppS, AlexJ et al's web framework for Haskell, at "openomy", > The latest release of our API is written in Haskell using the new HAppS > framework. The good news, > Since being in production, we've so far found very few issues and > everything runs quickly and smoothly. Haskell and HAppS have turned > out to be a very nice addition to our stable of tools and services. See the review here, http://blog.openomy.com/2008/01/case-study-using-haskell-and-happs-for.html Congratulations to Alex, Musasabi, Shapr, Igloo, Lemmih et al who've worked on getting HAppS into the real world! :) -- Don

2 1

Control.Concurrent.STM.old?
by Thomas DuBuisson 21 Jan '08

21 Jan '08

Does the 'old' function referenced in the SPJ and Tim Harris data invariants paper stil exist? It is of type STM a -> STM a and allowed invariants to compare old TVar values with new ones. I can't find it in any of the Haddocks or the code (and the 'check' funciton is not commented in the Haddock). Tom

2 1

need help for cabal-install
by Steve Lihn 21 Jan '08

21 Jan '08

Hi, I just got cabal-install working. However, I have a problem using it. My GHC is installed in a user-specific location, so when I do the Cabal dance, I have to specfiy "Setup configure --prefix=$HOME/ghc". Now with "cabal install", I can not figure out where to specify the --prefix. Cabal always complains "failed to install package". Help is appreciated. Steve

3 8

Data.Binary questions
by Lauri Pesonen 21 Jan '08

21 Jan '08

Hi, I'm relatively new to Haskell so please bear with me. I'm trying to parse Java class files with Data.Binary and I'm having a few problems: (The class file format is described here: http://java.sun.com/docs/books/jvms/second_edition/html/ClassFile.doc.html and the bytecode instructions are described here: http://java.sun.com/docs/books/jvms/second_edition/html/Instructions.doc.ht… ) 1. The class file format contains a number of tables. The table definitions start with the length of the list and carry on with that many table entries. Lists would be a good representation for them in Haskell, because there is not need to index them directly (except with the constants table). I've created my own list type so that I can redefine the serialisation functions for it so that the serialisation matches the format defined in the class file format: newtype MyList e = MkList ([e]) deriving Show instance (Binary e) => Binary (MyList e) where put (MkList es) = do put (fromIntegral (length es) :: Word16) mapM_ put es get = do n <- get :: Get Word16 xs <- replicateM (fromIntegral n) get return (MkList xs) The problem is that one of the tables, namely the attribute_info structures, use a u32 length field whereas all the other tables use a u16 length field. My implementation uses u16, but it would be nice to be able to use the same data type for both types of tables. I think I can do it by adding a lenght field to MyList and specifying the type when I use MyList in some other data structure, but that would also mean that I have to keep track of the length of the list manually? I'm basically copy-pasting the same code just to use a u32 length field in the serialised form: data Info = MkInfo [Word8] deriving Show instance Binary Info where put (MkInfo xs) = do put (fromIntegral (length xs) :: Word32) mapM_ put xs get = do n <- get :: Get Word32 xs <- replicateM (fromIntegral n) get return (MkInfo xs) 2. This is the bigger problem. The Java class file contains a constants table in the beginning of the file. The other fields later on in the class file contain indexes that reference entries in that constants table. So in order to be able to replace an index in a data structure with the actual string, I need to be able to look up the string from the constants table while I'm deserialising the field. My guess is that I should be able to put the constants table into a state monad. On the other hand Data.Binary already uses the state monad for holding onto the binary data being deserialised. So it's not clear to me if I can use StateT with Data.Binary.Get? And if not, can I implement my own state monad and do it that way? I'm not very comfortable with Monads yet, so I might be missing something very obvious. This is what the get function looks like in my top-level Data.Binary instance: get = do magic <- get :: Get Word32 case magic == magicNumber of -- class files start with 0xCAFEBABE True -> do min <- get -- minor version number u16 maj <- get -- major version number u16 c <- get -- constants table a <- get -- access flags (public, abstract, ...) u16 t <- get -- a u16 index pointing to the name of this class in the constants table s <- get -- a u16 index pointing to the name of the super class in the constants table i <- get -- a table of interfaces f <- get -- a table of fields m <- get -- a table of methods attrs <- get -- a table of class level attributes return (ClassFile (min, maj) c a t s i f m attrs) False -> error "Invalid magic number" Thanks for all the help! -- ! Lauri

2 3

Re: [Haskell-cafe] functional graphs
by Christian Maeder 21 Jan '08

21 Jan '08

Thomas Hartman wrote: > I don't think this will work. > > From > > http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/src/Data-Graph-In… > > the minimal implementatin for Graph is > > -- | Minimum implementation: 'empty', 'isEmpty', 'match', 'mkGraph', 'labNodes' > .... > -- | Decompose a 'Graph' into the 'MContext' found for the given node and the > -- remaining 'Graph'. > match :: Node -> gr a b -> Decomp gr a b > > Basically, match given a node returns the graph minus the node, and a > "context for the node which has ingoing edges/labels, outgoing > edges/labels, the node itself and the node label. With the & operator > you can compose these two things and get back your original graph. > > With the implementation you have described I can't see any way to > implement this match function, unless per my above comment you're > doing something weird like having no graph edges, or all possible > graph edges. And then why use a graph? It's a _complete_ graph, i.e. there is an edge between every two nodes. I want to compute the minimum spanning tree using http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Induct… without rewriting the FGL code and without generating the many edges explicitly. Eventually I want to have a "proper" tree (Data.Tree.Tree) for pre-order traversal. Preorder traversal of a MST gives a sub-optimal solution (not worse than twice as long as the optimum) for the travelling salesman problem (TSP). I may be on the wrong track, though. Thanks Christian > Unless I'm missing something... > > Thomas. > > > 2008/1/18, Christian Maeder <Christian.Maeder(a)dfki.de>: >> Hi, >> >> Given a complete graph as a list of nodes whose edge labels are given by >> a function over two nodes: >> >> data CGraph a b = CGraph [a] (a -> a -> b) >> >> Can I define an instance for the fgl Graph class? >> >> import Data.Graph.Inductive.Graph >> >> instance Graph CGraph where >> empty = CGraph [] -- and now? >> >> I had no idea how to define empty (except using undefined). >> >> I thought of requiring a context for the node labels of type a, but this >> type is not mentioned in the class header. So it looked to me like the >> impossibility to define sets (requiring an Ord) as monads. (i.e. >> instance Monad Data.Set.Set) >> >> Any working proposals for my graph problem? >> >> Cheers Christian

2 1

ICFP2008 Call for Papers
by Matthew Fluet (ICFP Publicity Chair) 21 Jan '08

21 Jan '08

Call for Papers ICFP 2008: International Conference on Functional Programming Victoria, BC, Canada, 22-24 September 2008 http://www.icfpconference.org/icfp2008 Submission deadline: 2 April 2008 ICFP 2008 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 * Functional Pearls: elegant, instructive, and fun essays on functional programming * Practice and Experience: novel results drawn from experience in education or industry. Experience Reports are also solicited, which are short papers (2-4 pages) that provide evidence that functional programming really works or describe obstacles that have kept it from working in a particular application. Functional Pearls and Experience Reports are separate categories of papers that need not report original research results and must be marked as such at the time of submission. Detailed guidelines on both categories are below. What's different this year? ~~~~~~~~~~~~~~~~~~~~~~~~~~~ * No double blind reviewing. Instructions for authors ~~~~~~~~~~~~~~~~~~~~~~~~ By Wednesday, 2 April 2008, 09:00 AM Apia time, submit an abstract of at most 300 words and a full paper of at most 12 pages (4 pages for an Experience Report), including bibliography and figures. The deadline will be strictly enforced and papers not meeting the page limits are summarily rejected. Authors have the option to attach supplementary material to a submission, on the understanding that reviewers are not expected to read it. A submission will be evaluated according to its relevance, correctness, significance, originality, and clarity. It 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. The technical content should be accessible to a broad audience. Each submission must adhere to SIGPLAN's republication policy, as explained on the web. Violation risks summary rejection of the offending submission. Proceedings will be published by ACM Press. Authors of accepted submissions are expected to transfer the copyright to ACM. They may have the option to have their presentation videotaped and published along with the conference proceedings in the ACM Digital Library. Video recordings will only be released at the consent of the presenter, which is expressed by signing an additional copyright release/permission form. Formatting ~~~~~~~~~~ Submissions must be in PDF format printable in black and white on US Letter sized paper and interpretable by Ghostscript. If this requirement is a hardship, make contact with the program chair at least one week before the deadline. ICFP proceedings are printed in black and white. It is permissible to include color in a submission, but you risk annoying reviewers who will have to decide if your final paper will be understandable without it. Papers must adhere to the standard ACM conference format: two columns, nine-point font on a ten-point baseline, with columns 20pc (3.33in) wide and 54pc (9in) tall, with a column gutter of 2pc (0.33in). A suitable document template for LaTeX is available from SIGPLAN. Submission ~~~~~~~~~~ Submissions will be accepted electronically; the submission page is not yet ready. The deadline is set at Samoan time, so if your submission is in by 09:00 AM Wednesday according to your local time, wherever you are, the submission will be on time. The world clock (http://www.timeanddate.com/worldclock/fixedtime.html?month=4&day=2&year=200…) can give you the equivalent in your local time, e.g.,1:00 PM Wednesday in Seattle, 4:00 PM Wednesday in New York, and 9:00 PM Wednesday in London. 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, starting at 09:00 on 21 May 2008 Apia time, to read and respond to reviews. 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 ~~~~~~~~~~~~~~~~~ A Functional Pearl is an elegant essay about something related to functional programming. It might offer: * a new and thought-provoking way of looking at an old idea * an instructive example of program calculation or proof * a nifty presentation of an old or new data structure * an interesting application of functional programming techniques * a novel use or exposition of functional programming in the classroom Functional Pearls are not restricted to the above varieties, however. While pearls often demonstrate an idea through the development of a short program, there is no requirement or expectation that they do so. Thus, they encompass the notions of theoretical and educational pearls. A pearl should be concise, instructive, and entertaining. 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 inelegant. The key to writing a good pearl is polishing. Some advice from Richard Bird: * 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 what obstacles prevent 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. * An Experience Report is at most 4 pages long. 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 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. Typically, more convincing evidence is obtained from papers which show how functional programming was used than from papers which only say that functional programming was used. The most convincing evidence often 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: make a claim about how well functional programming worked on your project and why, and produce evidence to substantiate your claim. 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 are unsure in which category to submit, the program chair will be happy to help you decide. Other information ~~~~~~~~~~~~~~~~~ Conference Chair ~~~~~~~~~~~~~~~~ James Hook (Portland State University) Program Chair ~~~~~~~~~~~~~ Peter Thiemann Albert-Ludwigs-Universität Georges-Köhler-Allee 079 79110 Freiburg, Germany Email: icfp08(a)informatik.uni-freiburg.de Phone: +49 761 203 8051 Fax: +49 761 203 8052 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 ~~~~~~~~~~~~~~~~~ Derek Dreyer (Max Planck Institute for Software Systems) Robert Ennals (Intel Research) Kathleen Fisher (AT&T Research) Zhenjiang Hu (University of Tokyo) Frank Huch (University of Kiel) Andrew Kennedy (Microsoft Research) Kevin Millikin (Google) Henrik Nilsson (University of Nottingham) Chris Okasaki (United States Military Academy) Brigitte Pientka (McGill University) Rinus Plasmeijer (University of Nijmegen) Alan Schmitt (INRIA) Chung-chieh Shan (Rutgers) Mitchell Wand (Northeastern University) Stephen Weeks (Jane Street Capital) Important Dates (at 09:00 Apia time, UTC-11) ~~~~~~~~~~~~~~~ Submission: 2 April 2008 Author response: 21 May 2008 Notification: 16 June 2008 Final papers due: 7 July 2008 ICFP 2008 Web Site ~~~~~~~~~~~~~~~~~~ http://www.icfpconference.org/icfp2008/ Special Journal Issue ~~~~~~~~~~~~~~~~~~~~~ There will be a special journal issue with papers from ICFP 2008. The program committee will invite the authors of select accepted papers to submit a journal version to this issue.

1 0