April 2005 - Haskell - Haskell.org

manipulating untyped lambda-calculus in Haskell
by Vivian McPhail 30 Apr '05

30 Apr '05

Hi, I am writing a NL parser in Haskell, relying on combinatorial grammar for the syntactic derivation. Each word has an associated syntax and semantics, the semantic term is a lambda expression loaded at run-time using hs-plugins. I : np : <semantic term> :: Sem m a love : s\np : <semantic term> :: Sem m a Predicates in english can have up to 5 arguments, and some of these arguments are functions, so the type of Sem m a is an enumeration of the types that we can build up from (STT m a) and (->). I started by enumerating this by hand: \begin{code} data Monad m => Sem m a = ZSem (SST m a) | USem (SST m a -> SST m a) | BSem (SST m a -> SST m a -> SST m a) | TSem (SST m a -> SST m a -> SST m a -> SST m a) | QSem (SST m a -> SST m a -> SST m a -> SST m a -> SST m a) | FSem (SST m a -> SST m a -> SST m a -> SST m a -> SST m a -> SST) -- | U1Sem ((SST m a -> SST m a) -> SST m a) | B1Sem ((SST m a -> SST m a) -> SST m a -> SST m a) | T1Sem ((SST m a -> SST m a) -> SST m a -> SST m a -> SST m a) \end{code} then what I need is a function to apply these: \begin{code} applySem :: Monad m => Sem m a -> Sem m a -> Sem m a applySem (USem a) (ZSem b) = ZSem $ a b applySem (BSem a) (ZSem b) = USem $ a b applySem (TSem a) (ZSem b) = BSem $ a b applySem (QSem a) (ZSem b) = TSem $ a b applySem (U1Sem a) (USem b) = ZSem # a b applySem (B1Sem a) (USem b) = USem $ a b applySem (T1Sem a) (USem b) = BSem $ a b applySem (T2Sem a) (ZSem b) = B1Sem $ a b applySem (B12Sem a) (USem b) = U1Sem $ a b applySem _ _ = error "application of Semantic functions" \end{code} My typing system ensures that only the correct functions will be applied to each other (the typing system manipulates lambda terms with an additional type (Stc Name (Sem m a)). A complete parse will reduce the lambda terms to closed terms containing only App and Stc, no Var or Lam. I can then use applySem to reduce the term to a single (Sem m a) type, which I can then run. What I have done thus far is enumerate by hand, but for full coverage for 5 argument predicates I need to list 5^5 data constructors and entries in the applySem function. For theoretically complete coverage I would need to enumerate all possible types constructed from (STT m a) and (->). It seems that I must be missing something? Is there a more elegant way of doing this? One can make the observation that the applySem function always applies a function of type (b -> a) to a function of type b to yield a function of type a. I suppose I could write a code generator (in haskell) that enumerates all possible derivations of (STT m a) and (->) but there would still be 5^5 data constructors. Thanks, Vivian McPhail PS Is there something I can do with the Typeable class of hs-plugins?

2 1

MonadPlus
by Ashley Yakeley 30 Apr '05

30 Apr '05

I've added a bit more to <http://haskell.org/hawiki/MonadPlus>. I highly recommend people read it before they start claiming in papers that such-and-such a type "may thus be an instance of MonadPlus". -- Ashley Yakeley, Seattle WA

4 5

Reminder: PAT2005 Summer School
by jespera＠diku.dk 30 Apr '05

30 Apr '05

======== REMINDER of PAT2005 ======== Dates have changed: REGISTRATION is OPEN NOW Fee Waiver applications: 8. May Registration closes 20. May Summer School: Program analysis and transformation Organized by: Computer Science Department (DIKU), University of Copenhagen, Denmark Monday-Friday 6-10 June, 2005 Summer School homepage: http://www.diku.dk/PAT2005/ This summer school on Program analysis and transformation will span theory and practice in the field. The overall theme is semantics-based program manipulation, in which practically-motivated operations on programs are solidly based in the semantics of the underlying programming languages. Research profile of the Summer School's topics: This research field began with classical compiler optimisations. These were pragmatically successful and well-automated, but lacking in semantic foundations. This led to the long-pursued goal of truly semantics-based generation of compilers and of abstract machines to implement programming languages. Parallel academic developments included more powerful and interesting program transformations that were developed by hand, one at a time. Major progress has been made in all three areas: semantically well-founded compiler optimisations have been devised and well-automated; compilers and abstract machines can now be generated by semantics-based methods including partial evaluation; and there now exist more powerful, general and well-founded program transformations. The speakers at this Summer School represent the state of the art in this research field. Confirmed speakers and their topics are: Mooly Sagiv (Israel: Tel Aviv) Program analysis using Three-Valued Logic Olivier Danvy (Denmark: Aarhus) On one-step reduction, evaluation, and abstract machines Oege De Moor (UK: Oxford) Incremental execution of transformation specifications Nick Benton, Microsoft Research Cambridge Semantics of static analyses and program transformations Neil Jones (Denmark: DIKU, Copenhagen) Size-change termination analysis of first and higher-order programs Torben Mogensen (Denmark: DIKU, Copenhagen) Introduction to partial evaluation; Program semi-inversion Arne Glenstrup (Denmark: ITU, Copenhagen) Tool tutorial for the Scheme partial evaluators PGG and Similix John Gallagher (Denmark: Roskilde) Program analysis and specialisation using tree automata Robert Glueck (Denmark: DIKU, Copenhagen) Program inversion Kazuhiko Kakehi (Japan: MIST, Tokyo Uniiversity) Attribute grammars and program transformations Prerequisites: Students should have some familiarity with classical compiler optimisations. A basic knowledge of operational semantics of programming languages (eg Structural operational semantics, Natural semantics or Action semantics) would be helpful. Sponsors: The PAT Summer School is partly supported by FIRST Graduate School: http://first.dk/ APPSEM-II: http://www.tcs.informatik.uni-muenchen.de/~mhofmann/appsem2/ Microsoft Research: http://research.microsoft.com/aboutmsr/labs/ Danish Natural Science Research Agency: http://www.forsk.dk Web pages: PAT home page: http://www.diku.dk/PAT2005/ (with details on lecture topics, speaker profiles, timetable, etc.) DIKU guest page: http://www.diku.dk/diku/gaester/index.html (with details on local transport, maps, hotels, etc.) Registration: The registration fee is DKK 1100 = EURO 150. This includes lecture materials, lunches and coffees, and a Summer School dinner. A block of rooms will be reserved at a hotel in central Copenhagen -- specifically, the new Cab Inn. Attendees are expected to arrange and pay for their own travel and lodging. Registration will Open: 5. April, 2005 Close: 20. May, 2005. Fee waivers: There will be a limited number of grants covering part or all of the registration fee. Application materials are available at the course's web page at the beginning of the registration period. Local Organisation Committee: Neil Jones neil(a)diku.dk Andrzej Filinski andrzej(a)diku.dk Torben Mogensen torbenm(a)diku.dk Jesper Andersen jespera(a)diku.dk Karin Outzen karino(a)diku.dk

1 0

[ANNOUNCEMENT]: TFP '05: First Call for Papers
by Kevin Hammond 29 Apr '05

29 Apr '05

[With apologies in advance for any duplication. Kevin] FIRST CALL FOR PAPERS TFP 2005 <http://www.tifp.org/tfp05>: Sixth Symposium on Trends in Functional Programming, September 23rd-24th 2005, Tallinn, Estonia (co-located with ICFP 2005 and GPCE 2005). The 2005 Symposium on Trends in Functional Programming (TFP '05) is an international forum for researchers with interests in all aspects of functional programming languages, focusing on providing a broad view of current and future trends in Functional Programming. Previous TFP symposia were held in Munich, Germany in 2004, in Scotland in 2002 and 2003, as successors to the successful series of Scottish Functional Programming Workshops. TFP <http://www.tifp.org/> aims to combine a lively environment for presenting the latest research results with a formal post-symposium refereeing process leading to the publication by Intellect of a high-profile volume containing a selection of the best papers presented at the symposium. A review of a previous TFP proceedings can be found in the July 2003 issue of the Journal of Functional Programming. BEST STUDENT PAPER AWARD TFP traditionally pays special attention to research students, acknowledging that students are almost by definition part of new subject trends. The TFP05 best student paper award (i.e. for the best paper with a student as first author) acknowledges more formally the special attention TFP has for students. The 2004 award was given to Ron van Kesteren for the paper entitled: "Proof Support for General Type Classes". In order to enhance the quality of student submissions, student papers will be given the option of a feedback on their submission to the symposium proceedings. This feedback is intended for authors who are less familiar with a formal publication process and will provide general qualitative feedback on the submission, but will not give a grade or ranking. SCOPE OF THE SYMPOSIUM The Symposium recognises that new trends may arise through various routes. As part of the Symposium's focus on trends we therefore identify the following five categories of paper. High-quality papers are solicited in any of these categories: RESEARCH PAPERS (leading-edge, previously unpublished research work) POSITION PAPERS (on what new trends should or should not be) PROJECT PAPERS (descriptions of recently started new projects) EVALUATION PAPERS (what lessons can be drawn from a finished project) OVERVIEW PAPERS (summarizing work with respect to a trendy subject) Papers must be original, and not submitted for simultaneous publication in any other forum. They may consider any aspect of functional programming: theoretical, implementation- oriented, or more experience-oriented. Also applications of functional programming techniques to other languages may be considered. Papers on the following subject areas are particularly welcome: o functional programming and security o functional programming and mobility o functional programming applied to global computing o functional languages for embedded systems o telecommunications applications in functional languages o functional GRIDs o validation and verification of functional programs o functional languages for reasoning about imperative/object-oriented programs o interoperability with imperative programming languages o dependently typed functional programming o any new emerging trend in the functional programming area If you are in doubt on whether your paper is within the scope of TFP, please contact the TFP05 program chair, Marko van Eekelen, marko(a)cs.ru.nl. PROCEEDINGS Acceptance to the symposium will be based upon extended abstracts of at least 6 and at most 10 pages. Accepted abstracts are to be completed to full papers for publication in the proceedings that will be available at the symposium in Tallinn. In addition, we intend to continue the TFP tradition of publishing a high-quality subset of contributions in the Intellect series on Trends in Functional Programming. Revised papers will be refereed after the symposium to the normal standards and a subset of the best papers over all categories will be selected for publication by Intellect. This implies (among other things) that: * the paper is written in English. * the paper is well written. * the topic of the paper should be stated clearly. * the submission should clearly indicate to which paper category it belongs: a research, position, project, evaluation or overview paper; it should also indicate whether the paper is a student paper (i.e. first author a student). * for research papers, the approach to solving the problem should be outlined clearly and a detailed discussion of the solution must be given. * the work is properly compared with relevant related work. * there is an abstract, introduction and conclusion. * for research papers, the conclusion should summarise the problem, the solution, and how the work solves the problem. * papers for the symposium proceedings must adhere to the formatting instructions using the tfp.cls style, as will be provided on the TFP05 site; papers must not exceed 16 pages (papers in some categories may comprise considerably less pages). * papers submitted for publication by Intellect must follow formatting and any other instructions provided by the Program Chair. Papers will be judged on their contribution to the research area, with different criteria applying to different categories of paper, as appropriate. SIGNIFICANT DATES Submission of extended abstracts: Friday 8th July 2005 Notification of acceptance: Friday 22th July 2005 Early registration deadline: Friday 29th July 2005 Submission of full papers: Friday 2nd September 2005 Symposium at Tallinn, Estonia: Friday 23rd-Saturday 24th Sept. 2005 Feedback to student papers: Friday 21st October 2005 (provisional) Submission for formal proceedings: Friday 16th December 2005 (provisional) Notification of acceptance: Friday 10th February 2006 (provisional) Camera-ready version: Friday 10th March 2006 (provisional) ORGANISATION Symposium Chair: Kevin Hammond (University of St. Andrews) Program Chair: Marko van Eekelen (Radboud University Nijmegen, NL) Local Organisation: Tarmo Uustalu (Institute of Cybernetics, Tallinn) Treasurer: Greg Michaelson (Heriot-Watt University, Edinburgh) PROGRAM COMMITTEE: Andrew Butterfield, Trinity College Dublin Therese Hardin, Université Paris VI Kevin Hammond, St Andrews University John Hughes, Chalmers University Graham Hutton, University of Nottingham Hans-Wolfgang Loidl, Ludwig-Maximilians-University Munich Rita Loogen, Philipps-University Marburg Greg Michaelson, Heriot-Watt University Edinburgh John O'Donnell, University of Glasgow Ricardo Peña, Universidad Complutense de Madrid Claus Reinke, Canterbury, UK Sven Bodo Scholz, University of Hertfordshire Doaitse Swierstra, Utrecht University Phil Trinder, Heriot-Watt University Edinburgh Tarmo Uustalu, Institute of Cybernetics, Tallinn (and some other still unconfirmed members) SPONSORS We are actively looking for additional TFP sponsors, who may help to subsidise attendance by research students, for example. If you or your organization might be willing to sponsor TFP, or if you know someone who might be willing to do so, please do not hesitate to contact the Symposium chair: Kevin Hammond. Your students will be grateful!

1 0

CFP: International Summer School On Applied Semantics 2005
by Hans-Wolfgang Loidl 29 Apr '05

29 Apr '05

2nd CALL for PARTICIPATION International Summer School On Applied Semantics 2005 Frauenchiemsee, Germany, 8-12 September 2005 http://lionel.tcs.ifi.lmu.de/SummerSchool05/ The International Summer School On Applied Semantics 2005, part of the APPSEM II initiative, will be held on the island of Frauenchiemsee, an island in Lake Chiemsee near Munich, from September 8 to 12, 2005. The summer school provides an opportunity to attend courses on various topics in the area of applied semantics given by leading members of the community. The summer school is organised by the APPSEM II Working Group, and the University of Munich. Immediately after the summer school a workshop on applied semantics will be held at the same location. The summer school is addressed to postgraduate students, researchers and industrials who want to learn about recent developments in programming language research, both in semantic theory and in implementation. LECTURERS Andrew Pitts: Nominal Syntax and Semantics Philippa Gardner: Local Reasoning about Data Update Francois Pottier: A modern eye on ML type inference: old techniques and recent developments Gilles Barthe: Type Checking Dependent Types Chris Hankin: Principles of Program Analysis REGISTRATION AND DATES To register for the Summer School, down-load and fill-in the application form from the Summer School's web page and fax it to: +49 89 2180 9338. The registration fee for the Summer School is 180 Euro, covering attendance of all courses, lecture notes, and meals. Additionally, several options of accomodation, ranging from 25 to 50 Euros per night, are available from the main site of the venue. Deadline for Registration: 1 July 2005 Notification for Grants: 15 July 2005 Summer School: 8-12 September 2005 A limited number of student grants is available. To apply for a grant, fill-in the corresponding section in the above form, too. LOCATION The International Summer School On Applied Semantics 2005 will be held in Frauenchiemsee, an island in Lake Chiemsee, on the border between Germany and Austria, about 100kms in the south east of the Munich Airport or about 70 km in the west of Salzburg Airport. ORGANISING COMMITTEE Prof Martin Hofmann Dr Hans-Wolfgang Loidl Sigrid Roden Konstantin Kutzkow CONTACT Sigrid Roden, Ludwig-Maximilians-Universitaet Muenchen, Institut fuer Informatik, Theoretische Informatik, Oettingenstrasse 67 D 80538 Muenchen GERMANY Fax: +49 89 2180 9337 Tel: +49 89 2180 9338

1 0

REMINDER: Contributions to the HC&A Report (May 2005 edition)
by Andres Loeh 28 Apr '05

28 Apr '05

Dear Haskellers, the deadline for the May 2005 edition of the Haskell Communities and Activities Report is only a few days away -- but this is still enough time to make sure that the report contains a section on *your* project, on the interesting stuff that you've been doing; using or affecting Haskell in some way. Many projects that have been included in former reports have not yet updated their entries. Please have a look at http://haskell.org/communities/topics.html and at the November 2004 edition for reference. * Has your project been listed in previous Reports, but is not yet updated? Please write a short update! * Are you no longer working on a project that was included in the Report? Write up what you are working on instead, and tell me if someone else has picked up the project. * Is some project you have heard about not included in any previous Report? Please let me know ... There is still time to write a completely new entry, on a new compiler, tool, library, company, user group, idea, ... -- as long as there is a connection to the Haskell language, there is a place for it in the Report! Submissions are due by next Tuesday, that is Tuesday, 03 May 2005. Please mail your entries to <hcar at haskell dot org>, in plain text or pseudo-(La)TeX format. More information can be found in the original Call for Contributions at http://www.haskell.org/pipermail/haskell/2005-April/015688.html I look forward to receiving your contributions. Thanks a lot, Andres (current editor) -- Haskell Communities and Activities Report (http://haskell.org/communities) 05/2005 edition submission deadline: 03 May 2005 <hcar(a)haskell.org>

1 0

CFP: MICAI-2005 Artificial Intelligence, Springer LNAI: submission reminder and CFP-2
by Alexander Gelbukh (MICAI) 28 Apr '05

28 Apr '05

MICAI 2005 4th Mexican International Conference on ARTIFICIAL INTELLIGENCE November 14-18, 2005 Monterrey, Mexico www.MICAI.org/2005 Proceedings: Springer LNAI. Submission: May 29 (abstract May 22). Keynote speakers: see website. SECOND CALL FOR PAPERS *** WHAT'S NEW *** - Submission is now open. We strongly encourage you to register your abstract right now, as expression of interest (you can upload the full paper later). - Collocated workshops: Natural Language Understanding and Intelligent Information Access; others to be announced. *** GENERAL INFORMATION *** MICAI is a high-level international conference covering all areas of Artificial Intelligence. Acceptance rate of MICAI-2004 was 38% of submissions from 19 countries. See www.MICAI.org for more info. *** PAPER SUBMISSION *** All accepted papers will be published by Springer-Verlag in their Lecture Notes in Artificial Intelligence (LNAI). Authors are invited to submit original previously unpublished research papers, in English, up to 10 pages, strictly following the LNCS/LNAI format guidelines. Submissions are received through the website, see www.MICAI.org/2005. The title and abstract must be submitted by May 22, then the full paper by May 29. All submissions will be subject to blind peer review by three program committee members. *** IMPORTANT DATES *** May 22: Paper registration deadline (title and abstract required). May 29: Paper submission deadline (only papers registered by May 22). July 17: Acceptance notification. August 7: Camera-ready deadline. *** TOPICS *** Topics of interest are all areas of Artificial Intelligence, including but not limited to: - Expert Systems / KBS - Multiagent systems and Distributed AI - Knowledge Management - Intelligent Interfaces: Multimedia, Virtual Reality - Natural Language Processing / Understanding - Computer Vision - Neural Networks - Genetic Algorithms - Fuzzy logic - Belief Revision - Machine Learning - Intelligent Tutoring Systems - Data Mining - Knowledge Acquisition - Knowledge Representation - Knowledge Verification, Sharing and Reuse - Ontologies - Qualitative Reasoning - Model-Based Reasoning - Constraint Programming - Common Sense Reasoning - Case-Based Reasoning - Nonmonotonic Reasoning - Spatial and Temporal Reasoning - Robotics - Planning and Scheduling - Navigation - Assembly - Hybrid Intelligent Systems - Logic Programming - Automated Theorem Proving - Intelligent Organizations - Uncertainty / Probabilistic Reasoning - Philosophical and Methodological Issues of AI *** CONFERENCE ORGANIZATION *** Conference Chairs: Alvaro de Albornoz, Angel Kuri. Program Chairs: Alexander Gelbukh, Raul Monroy. Tutorial Chairs: Manuel Valenzuela, Horacio Martinez. Workshop Chairs: Ramon Brena, Jose Luis Aguirre. Keynote Talks Coordinator: Carlos Alberto Reyes. Local Chair: Hugo Terashima. Local Steering Committee: Rogelio Soto, Ricardo Swain. *** CONTACT *** General inquiries: micai2005 at MICAI dot org. Inquiries on submission requirements: submission at MICAI dot org. Inquiries on the conference program: program at MICAI dot org. See more contact options on www.MICAI.org/2005. We apology if you receive this CFP more than once. PLEASE CIRCULATE this CFP among your students and colleagues. ------------------------------------------------------------------------ This e-mail was delivered to you by event(a)in.tu-clausthal.de, what is a moderated list runned by Computational Intelligence Group of Technical University of Clausthal, Germany. All event announcements sent through this list are also listed in our conference planner at http://cig.in.tu-clausthal.de/index.php?id=planner. In the case of any requests, questions, or comments, do not hesitate and contact event-owner(a)in.tu-clausthal.de ASAP. ****************************************************** * CIG does not take any responsibility for validity * * of content of messages sent through this list. * ****************************************************** Computational Intelligence Group Institute of Informatics Technical University Clausthal Germany http://cig.in.tu-clausthal.de/

1 0

Zipper as a delimited continuation
by oleg＠pobox.com 27 Apr '05

27 Apr '05

This is the first part of a reply to a query about a zipper with two foci, posted on this list by Oktaviandi Hadi Nugraha on Apr 13. In this part we introduce the framework to answer the question. Our treatment of zipper is quite different from that of Huet (JFP, 1997) and Hinze and Jeuring (JFP 2001). Our zipper is polymorphic over the data structure to traverse, and the zipper creation procedure is generic and does not depend on the data structure at all. Different data structures or different realizations of the same abstract data structure can use the same zipper and the same zipper creation and manipulation functions. Our zipper type depends only on the interface (but not the implementation!) of a traversal function. Our zipper is a derivative of a traversal function rather than that of a data structure itself. Zipper is a construction that lets us replace an item deep in a complex data structure, e.g., a tree or a term, without any mutation. The resulting data structure will share as much of its components with the old structure as possible. The old data structure is still available (which can be handy if we wish to 'undo' the operation later on). Zipper is essentially an `updateable' and yet pure functional cursor into a data structure. Zipper is also a delimited continuation reified as a data structure. In this message, we use delimited continuations directly to derive the zipper. We will be relying on the delimited continuation framework by R. Kent Dybvig, Simon Peyton-Jones and Amr Sabry. Their framework supports shift/reset with multiple prompts and fully polymorphic answertypes. We will be using a slightly modified version of the framework, where the CC monad is a transformer rather than the stand-alone monad. > {-# OPTIONS -fglasgow-exts #-} > module Zipper0 where > > -- Part of the Dybvig, Sabry, Peyton-Jones' library > -- adjusted from being a monad to be a monad transformer > import CC_2CPST > import Control.Monad.Identity > import Control.Monad.Trans We will be using the familiar shift/reset control operators, implemented as follows: > promptP :: Monad m => (Prompt r a -> CC r m a) -> CC r m a > promptP f = do p <- newPrompt; pushPrompt p (f p) > > shiftP :: Monad m => > Prompt r b -> ((CC r m a -> CC r m b) -> CC r m b) -> CC r m a > shiftP p f = letSubCont p $ \sk -> > pushPrompt p (f (\c -> > pushPrompt p (pushSubCont sk c))) We need multiple prompts in the second part to be posted later. The derivation of the zipper starts with a term traversal function. The zipper will be as good and powerful as the traversal function. Let us adopt as a running example the familiar and dear data structure: > data Term = Var String | A Term Term | L String Term > deriving (Eq,Show) In this message, we chose the following function to traverse the lambda-term: > data Direction = Down | DownRight | Up | Next deriving (Eq, Show) > traverse :: (Monad m)=> (Term -> m (Maybe Term, Direction)) -> Term -> m Term > traverse tf term = do > (term', direction) <- tf term > let new_term = maybe term id term' > let select Up t = return t > select Next t@(Var _) = return t > select dir t@(L v t1) | dir == Next || dir == Down > = do > t1' <- traverse tf t1 > return $ L v t1' > select DownRight t@(A t1 t2) = > do > t2' <- traverse tf t2 > return $ A t1 t2' > select dir t@(A t1 t2) | dir == Next || dir == Down > = do > t1' <- traverse tf t1 > t2' <- traverse tf t2 > return $ A t1' t2' > select direction new_term The function `traverse' receives the traversal function `tf' and the lambda-term, and walks and _updates_ the term, as guided by `tf'. The traversal function receives the current subterm and should return a pair. If the first component of a pair is (Just t'), then t' replaces the current subterm. The second component of tf's result is the direction to proceed. The direction Next means proceed in the depth-first order. Other directions may be used to skip some parts of the term and so avoid walking the whole term. The function is written in a monadic style (for an arbitrary monad m). We shall need that later. We will be using the following term as a running example: > -- P2 numeral > term1 = L "f" (L "x" (A (A f (L "f" (A f (L "f" (L "x" x))))) > (A (A f (L "f" (L "x" x))) x))) > where [f,x] = map Var ["f","x"] The first test simply traverses the whole term, makes no alterations and returns the (copy of the) term: > testt1 = runIdentity (traverse (\term -> return (Nothing,Next)) term1) -- *Zipper0> testt1 == term1 -- True To make sure that we really traverse the term, we can print out all the encountered subterms: > testt2 = traverse tf term1 > where tf term = print term >> return (Nothing,Next) We instantiate `traverse' for the IO monad this time. We can skip some parts of the term during the traversal: > testt3 = traverse tf term1 > where > tf term@(A (Var "f") _) = do > print "cutting" >> print term > return (Nothing,Up) > tf term = print term >> return (Nothing,Next) and we can modify the term > testt4 = runIdentity (traverse tf term1) > where tf (L "x" (Var "x")) = return (Just (L "y" (Var "y")),Next) > tf _ = return (Nothing,Next) which indeed returns term1 with all occurrences of (L "x" (Var "x")) replaced with (L "y" (Var "y")). Now we an introduce the zipper: > data Zipper r m term dir = > Zipper term (CC r m (Maybe term, dir) -> CC r m (Zipper r m term dir)) > | ZipDone term It is indeed polymorphic over the term to traverse (as well over the source monad 'm'). We can use this Zipper, as it is, for _any_ data structure that can be traversed by a function that looks like `traverse'. Creating the zipper equally generic: > zip'term :: (Monad (CC r m), Monad m) => > ((term -> CC r m (Maybe term, dir)) -> term -> CC r m term) > -> term -> CC r m (Zipper r m term dir) > zip'term trav term = promptP (\p -> trav (tf p) term >>= (return . ZipDone)) > where tf p term = shiftP p (\k -> return (Zipper term k)) Both Zipper and its creation function depend neither on the representation of the term nor on the traversal strategy. All the information about the data structure and its traversal is encapsulated in one single function `trav'. We can now examine term1, subterm by subterm, using the cursor, zipper, rather than the enumerator, traverse: > zip'through (ZipDone term) = liftIO (print "Done" >> print term) > zip'through (Zipper term k) = do > liftIO $ print term > k (return (Nothing,Next)) >>= zip'through > tz1 :: IO () = runCC (zip'term traverse term1 >>= zip'through) In a sense, we have `inverted' the operation of term traversal. With the cursor, we can keep arbitrary state from one traversal step to another. The cursor provided by zipper is updateable. We can now descend (or walk) to the desired node, replace it, and zip up the result to yield the updated term: > zip'move dir (Zipper term k) = > liftIO (print dir >> print term) >> k (return (Nothing,dir)) > zip'upr (Zipper term k) nt = do > liftIO (print term >> print "replacing with" >> print nt) > k (return (Just nt,Up)) > zip'all'the'way'up (ZipDone term) = return term > zip'all'the'way'up (Zipper term k) = > k (return (Nothing,Up)) >>= zip'all'the'way'up > > tz2 :: IO () > = runCC ( > do > z <- zip'term traverse term1 > z1 <- zip'move Next z > z1 <- zip'move Next z1 > z2@(Zipper (A _ _) k) <- zip'move DownRight z1 > res <- zip'upr z2 (A (Var "x") (Var "x")) >>= zip'all'the'way'up > liftIO $ (print "Result" >> print res) > --zip'through z1 > ) *Zipper0> tz2 Next L "f" (L "x" (A (A (Var "f") (L "f" (A (Var "f") (L "f" (L "x" (Var "x")))))) (A (A (Var "f") (L "f" (L "x" (Var "x")))) (Var "x")))) Next L "x" (A (A (Var "f") (L "f" (A (Var "f") (L "f" (L "x" (Var "x")))))) (A (A (Var "f") (L "f" (L "x" (Var "x")))) (Var "x"))) DownRight A (A (Var "f") (L "f" (A (Var "f") (L "f" (L "x" (Var "x")))))) (A (A (Var "f") (L "f" (L "x" (Var "x")))) (Var "x")) A (A (Var "f") (L "f" (L "x" (Var "x")))) (Var "x") "replacing with" A (Var "x") (Var "x") "Result" L "f" (L "x" (A (A (Var "f") (L "f" (A (Var "f") (L "f" (L "x" (Var "x")))))) (A (Var "x") (Var "x")))) We should point out that we are given an arbitrary number of cursors over the same data structure: for example, in `tz2', the cursor 'z1' is still valid at the end, and still points out to the `third' subterm. The cursor 'z2' is valid as well. All these cursors are isolated: the updates done with the cursor 'z2' and invisible to the cursor 'z1' (as we can see if we uncomment the last statement in tz2). Essentially, each cursor runs in its own transaction. In the second part we will discuss how to make cursors that see the updates of each other. Contrary to the traditional database wisdom, for zippers, it is far harder to implement lower isolation modes than the higher ones.

1 0

Rank-N types vs existential types
by Andre Pang 27 Apr '05

27 Apr '05

Hi all, Let's say I have the following two data types: > {-# OPTIONS_GHC -fglasgow-exts #-} > > module RankNVsExists where > > data RankN = RankNEq (forall a. Eq a => a -> a -> Bool) > | RankNOrd (forall a. Ord a => a -> a -> Bool) > > data Exists = forall a. Eq a => ExistsEq (a -> a -> Bool) > | forall a. Ord a => ExistsOrd (a -> a -> Bool) So, the RankN type uses rank-2 polymorphism to "hide" the expression inside the type, whereas the Exists type uses existentially quantified types instead. The two seem pretty equivalent to me, since the data constructors have the same type. However, I can't help but feel that I'm missing something fundamental about a difference between them. Are the two completely isomorphic? Is there some advantage or disadvantage to using one over the other? -- % Andre Pang : trust.in.love.to.save <http://www.algorithm.com.au/>

4 6

howto implement the getDirectoryContents by hand
by Sun Yi Ming 27 Apr '05

27 Apr '05

hi all, i even know there is a getDirectoryContents function in lib,but that's implemented by primitive function getDirContents,so i try to implement it use openDirStream,readDirStream but failed to recursive the contents, below is my try code: module Test1 where import System.Directory import System.Posix.Directory import Control.Monad dirName = "/home/wise/source/haskell" ls :: FilePath -> IO [FilePath] ls dname = do dirs <- openDirStream dname path <- readDirStream dirs return [path] -- so how to recursive this test = print =<< ls dirName any help is appreciated. Sun Yi Ming

1 0