- Haskell - Haskell.org

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 28 Apr '05

28 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

Undefined of Char.toUpper ?
by Luo Shuli 27 Apr '05

27 Apr '05

Dear Haskellers, I am a beginer of the haskell language and study it from <<Yet Another Haskell Tutarial>> of Hal Daume III. Example from the tutarial: Prelude> map Char.toUpper "Hello World" I try it on Hugs for windows32, compile error: ERROR - Undefined qualified variable "Char.toUpper" Could anybody tell me what's the matter with it? Thanks, Luo Shuli

3 2

Re: ANNOUNCE: The jhc Haskell compiler.
by Antonio Regidor García 27 Apr '05

27 Apr '05

Very interesting! What license uses jhc? The COPYING file seems to be empty. Best regards, Antonio Regidor García ______________________________________________ Renovamos el Correo Yahoo!: ¡250 MB GRATIS! Nuevos servicios, más seguridad http://correo.yahoo.es

5 4

Re: [Haskell] MPTCs and type inference
by Iavor Diatchki 26 Apr '05

26 Apr '05

Hello, On 4/25/05, Andrew Pimlott <andrew(a)pimlott.net> wrote: > I appreciated your explanation, but can you also address (to the list) > the last case given by the original poster? > > > On 4/25/05, Andreas Rossberg <rossberg(a)ps.uni-sb.de> wrote: > > > in particular, when I compare with the single parameter case: > > > > > > class C a where fc :: a -> a -> () > > > > > > c1 x = let p = fc x in () > > > c2 x = let p y = fc x y in () > > > > > > where > > > > > > c1 :: C a => a -> () > > > c2 :: C a => a -> () > > > > > > is inferred, as I would expect. The inference steps for this case are much the same except, that the inferred type for "p" now will be: "a -> ()", provided that we can solve the constraint "C a". Because we have assumptions about "a" in the environment (namely it is mentioned in the type of the varible "x") we cannot generalize the type of "p". It therefore remains monomorphic, and the constraint "C a" is propagated to the type of "c2". -Iavor

2 1

Read and write file on Windows XP.
by Alexandre Weffort Thenorio 26 Apr '05

26 Apr '05

I have a small program which simply reads a text file, gets the second line and changes it and writes a clone file with the second line changed. Basically it looks like that: main :: IO() main =do -- Some code here hexFile <- catch (readFile "int.hex") (\_ -> do putStrLn "File int.hex not found" getLine exitWith ExitSuccess) --some code here newLine <- outputLine keyno key (lines(hexFile)) --finish code for main function here outputLine keyno key orgFile = do -- Some code that modifies second line here newHexFile <- openFile "newint.hex" WriteMode hPutStrLn newHexFile (orgFile!!0 ++ "\n" ++ final ++ unlines (drop 2 orgFile)) The final variable above is the string containing the second line. What happens is everything works fine on my PC (Windows 2000) but on another PC (Using Windows XP) it sometimes gives a file which is incomplete, a couple of lines missing in the end making the file smaller and wrong. So I was wondering could it be the computer itself or is there any issue with Windows XP when it comes to reading and writing files. I tried using openFileEx but to my surprise it says it is deprecated (Which function to se instead then?). Best Regards NooK

2 2

MPTCs and type inference
by Andreas Rossberg 26 Apr '05

26 Apr '05

This may well be stupidity on my side, but some experiments with multi parameter type classes got me slightly confused. Can somebody explain the following behaviour to me? class D a b where fd :: a -> b -> () d1 x = let p = fd x in () d2 x = let p y = fd x y in () GHC derives the following types: d1 :: D a b => a -> () d2 :: a -> () Hugs rejects d1 on the grounds that the type is ambiguous, but agrees on the type of d2. I do not understand where the context disappears to in this example - in particular, when I compare with the single parameter case: class C a where fc :: a -> a -> () c1 x = let p = fc x in () c2 x = let p y = fc x y in () where c1 :: C a => a -> () c2 :: C a => a -> () is inferred, as I would expect. -- Andreas Rossberg, rossberg(a)ps.uni-sb.de Let's get rid of those possible thingies! -- TB

2 1

SOEGraphics
by Peter Padawitz 26 Apr '05

26 Apr '05

The Mar2005 release of Hugs includes SOEGraphics, but does not recognize the type constructor Draw. Has it been changed? Peter

2 1