- Haskell - Haskell.org

THEORETICAL COMPUTER SCIENCE '02 - Accepted papers
by Michel Barbeau 13 Apr '02

13 Apr '02

-- Michel Barbeau School of Computer Science, Carleton University 1125 Colonel By Drive, Ottawa, Ontario, Canada K1S 5B6 Phone: (613) 520-2600 x 1644 Fax: (613) 520-4334 �� 2nd IFIP International Conference on �� THEORETICAL COMPUTER SCIENCE �� (TCS 2002) �� Montreal, August 25-30, 2002 �� co-sponsored by� EATCS and ACM SIGACT �(http://www.scs.carleton.ca/~santoro/TCS2002/indexTCS2002.html) �� ==========================3D=========================3D===== ========================3D=========================3D== TRACK A - Algorithms, Complexity, Models of Computations ==========================3D=========================3D -------------------------------- Jochen Alber, Jiri Fiala Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs Nikhil Bansal, Zhen Liu, Arvind Sankar Bin-Packing with Fragile Objects S. Bespamyatnikh, B. Bhattacharya, D. Kirkpatrick, M. Segal Lower and upper bounds for tracking mobile servers Alina Beygelzimer, Mitsunori Ogihara On the enumerability of the determinant and the rank Beate Bollig, Stephan Waack, Philipp Woelfel Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication Vasco Brattka, Martin Ziegler Computability of Linear Equations G. Calinescu. I.I. Mandoiu, A. Zelikovsky Symmetric connectivity with minimum power consumption in radio networks Olivier Carton, V�ronique Bruy�re Hierarchy among Automata on Linear Orderings Z. Chen A Modified Recursive Triangular Factorization� for Cauchy-like Systems of Linear Equations M. Cieliebak, T. Erlebach, Z. Liptak, J. Stoye, E. Welzl Algorithmic complexity of protein identification: searching in weighted strings Alessandro Dal Palu`, Enrico Pontelli, Desh Ranjan An Efficient Parallel Pointer Machine Algorithm for Nearest-Common Ancestor Problem M. Duflot, L. Fribourg, C. Picaronny Randomized dining philosophers without fairness assumption Alon Efrat, Sariel Ar-Peled Locating guards in Art Galleries Leszek Gasieniec, Igor Potapov Gossiping with Single Messages in Radio Networks Nicolas Hanusse, Dimitris Kavvadias, Evangelos Kranakis, Danny Krizanc Memoryless Search Algorithms in a Network with Faulty Advice Lane A. Hemaspaandra, Mayur Thakur Rice-Style Theorems in Complexity Theory Matthew Hertz, Neil Immerman,� J. Eliot,� B. Moss Framework for Analyzing Garbage Collection Christopher M. Homan, Mayur Thakur One-Way Permutations and Self-Witnessing Languages Klaus Jansen, Hu Zhang Approximation Algorithms for General Packing Problems with Modified Logarithmic Potential Function Gregory Lafitte On randomness and infinity A. Pagourtzis, P. Penna, K. Schlude, K. Steinhofel, D.S. Taylor, P. Widmayer Server placements, roman domination and other dominating set variants B. S. Panda, Sajal K. Das A Linear Time Algorithm for Finding Tree 3-Spanner on 2-Trees Joerg Rothe, Holger Spakowski, Joerg Vogel Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections Paolo Santi, Douglas M. Blough, Mauro Leoncini, Giovanni Resta On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks Tomoyuki Yamakami Quantum NP and Quantum Operator Marius Zimand Probabilistically checkable proofs the easy way ==========================3D=========================3D TRACK B - Logic, Semantics, Specification and Verification ==========================3D=========================3D Patrick Baillot Checking Polynomial Time Complexity with Types Chiara Braghin, Agostino Cortesi, Riccardo Focardi, Steffen van Bakel Boundary Inference for Enforcing Security Policies in Mobile Ambients Hana Chockler, Orna Kupferman Coverage of Implementations by Simulating Specifications Giovanni Conforti, Orlando Ferrara, Giorgio Ghelli TQL Algebra and its Implementation Dino Distefano, Arend Rensink, Joost-Pieter Katoen Model Checking Birth and Death Matthew Fluet, Riccardo Pucella Phantom Types and Subtyping Rachid Guerraoui, Petr Kouznetsov On the Weakest Failure Detector for Non-Blocking Atomic Commit Martin Hyland, Gordon Plotkin, John Power Combining Computational Effects: commutativity & sum Salvatore La Torre, Supratik Mukhopadhyay, Aniello Murano Optimal-Reachability and Control for Acyclic Weighted Timed Automata Daniel Leivant Substructural Verification and Computational Feasibility Stephane Lengrand, Dan Dougherty, Pierre Lescanne An Improved System of Intersection Types for Explicit Substitutions Aline Brum Loreto, Laira Vieira Toscani, Leila Ribeiro Decidability and Tractability of a Problem in Object-Based Graph Grammars Fabio Martinelli About Compositional Analysis of� Pi-Calculus Processes Catuscia Palamidessi, Oltea Milhaela Herescu A Randomized Encoding of the Pi-Calculus with Mixed Choice I.C.C. Phillips, M.G. Vigliotti On Reduction Semantics for the Push and Pull Ambient� Calculus Alan Schmitt Safe Dynamic Binding in the Join Calculus Olivier Serre Vectorial Languages and Linear Temporal Logic Scott D. Stoller A Bound on Attacks on Authentication Protocols Xiaogang Zhang, John Potter Responsive Bisimulation

1 0

"Introducing Parallelism in a Lazy Functional Language"
by Hal Daume III 13 Apr '02

13 Apr '02

Hey, I know this isn't the official point of this mailing list, but I'm working on something related to the paper mentioned in the subject (by Nathan Charles). I'm trying to find more information about it, but unfortunately it seems that Nathan has left York. Does anyone know where I could find him? -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

1 0

Re: Confused about seq and forms.
by Jay Cox 13 Apr '02

13 Apr '02

On Fri, 12 Apr 2002, Bernard James POPE wrote: <snip> > Do you have a copy of the book: The implementation of Functional Programming > Languages, by Simon Peyton Jones? > > It is sadly out of print, but most universities have copies in their libraries. > > It is one of the best references that I know of. > > page 198 of that book has what you want to know. > > Cheers, > Bernie. Just to pass it along in case somebody else wants the reference. I'm a bit suprised why you only replied to me. The message part not included was as much educational to me as Janis Janis Voigtlaender's message. I'd post it all if I weren't afraid that might offend you for some reason or violate some implicit politeness law I don't know of. Thanks both, Jay Cox

1 0

trying to tie the knot
by Hal Daume III 13 Apr '02

13 Apr '02

Hi All, I thought I was starting to get my head around the whole tying the knot phenomenon, but when my program produced "*** Exception: <<loop>>" I figured I was probably missing something :). Here's what I'm trying to do (I know I could do it without tying the knot, but that seemed like a reasonable approach and I wanted to get my hands dirty or feat wet): I'm reading in a file; that is I have a function String -> MyDataType. More specifically I'm reading in a Tree, and the tree is specified in the file with these "Subtree" fields. So you can be reading along in the tree and then instead of actually seeing a branch or leaf, you'll see somethign like "[S1]" which means "stick subtree S1 in here". later in the file (arbitrarily later), you will see something like "Subtree [S1]" and then following that is that tree. So what I did was I changed my function to a String -> [(String,Tree)] -> (Tree, [(String,Tree)] function where the list is a lookup for the subtrees. I then said: readTrees s = let (t, st) = readTrees' s st in t and then the readTrees' basically read the tree in as normal; except when it gets to something like "[S1]" it does lookup "[S1]" subTrees to get the subtree and then when it gets to "Subtree [S1]" it reads in the subtree and then adds it to the subtree list. Is this not an appropriate use of tying the knot or amd I just doing something wrong? I've attached my code if you want to read it; It's marginally more complex that I've written here jsut because of some of the idiosyncracies in the file format... - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 1

RE: deriving over renamed types
by Simon Peyton-Jones 12 Apr '02

12 Apr '02

It's a bug in GHC 5.02 and earlier; fixed in 5.03 Simon | -----Original Message----- | From: Hal Daume III [mailto:hdaume@ISI.EDU] | Sent: 04 April 2002 00:15 | To: Haskell Mailing List | Subject: deriving over renamed types | | | Why can't I do this: | | > import FiniteMap | > type FM = FiniteMap | > instance (Show a, Show b) => Show (FiniteMap a b) where | > show = show . fmToList | > data X = X (FM Int Int) | > deriving (Show) | | if I replace | | > type FM = FiniteMap | | with | | > type FM a b = FiniteMap a b | | it works fine. I wasn't aware there was (supposed to be) a | difference between these two declarations? Is there? | | - Hal | | | -- | Hal Daume III | | "Computer science is no more about computers | hdaume(a)isi.edu | than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

2 1

More Haskell Blue Sky: Partial Type Annotations
by Ashley Yakeley 12 Apr '02

12 Apr '02

I sometimes come across a situation when I only want to provide a _partial_ type annotation, perhaps because the full type has some variable unified with some variable in some other type annotation, or something. For instance: f :: forall a. [a] -> [a] -> [a] f x y = g x where g [] = y g (_:_) = x ...there doesn't seem to be a way of giving a type annotation for 'g'. Theoretically it's '[a] -> [a]', but where 'a' is the same as the 'a' in the type signature for 'f'. Under this proposal, unqualified type variables would be considered to be 'free' rather than implicitly forall-qualified. So for instance, any function could be given the partial type annotation 'a -> b'. For instance, all these annotations would be the same given this function: k :: a k :: a -> ba k :: a -> b -> a k :: forall b. a -> b -> a k :: forall a b. a -> b -> a k x y = x ...and these would both be the same, but different from the previous: k' :: Int -> ba k' :: forall b. Int -> b -> Int k' x y = x And so we could write this: f :: forall a. [a] -> [a] -> [a] f x y = g x where g :: [a] -> [a] -- partial annotation may be sufficient g [] = y g (_:_) = x I admit that's a bit of a change, and might break programs... In addition, it doesn't address the occasional need to tie type annotations together, something that has often made me add ugly dummy arguments used just for their type. -- Ashley Yakeley, Seattle WA

4 4

IFL 2002 Announcement
by Ricardo Pe~na 11 Apr '02

11 Apr '02

(Apologies for multiple postings) ============================================================ IFL 2002 14th International Workshop on the IMPLEMENTATION OF FUNCTIONAL LANGUAGES Madrid Spain September 16 - 18, 2002 ============================================================= Important dates --------------- Registration deadline: July 30th, 2002 Submission deadline : August 26th, 2002 further details : http://dalila.sip.ucm.es/ifl02 ============================================================= Scope of IFL 2002 ----------------- The aim of the workshop is to bring together researchers and users actively engaged in the implementation and application of functional programming languages to discuss results and new directions of research. The workshop is intended to provide an open forum for researchers who wish to present and discuss new ideas and concepts, work in progress, preliminary results etc. related primarily but not exclusively to the implementation of functional or function-based languages. A not necessarily exhaustive list of topics includes language concepts type checking compilation techniques (abstract) interpretation automatic program generation (abstract) machine architectures array processing concurrent/parallel programming and program execution heap management runtime profiling and performance measurements debugging and tracing verification of functional programs tools and programming techniques Contributions on applications of functional programming, e.g., in teaching, or on theoretical work in any of the above areas are also welcome. Contributions ------------- All attendees are encouraged to submit papers to be published in the draft proceedings and to give presentations at the workshop. Submitted papers must be written in English, conform to the LNCS format (available at: http://www.springer.de/comp/lncs/authors.html) and not exceed 16 pages. Papers should be submitted by August 26th as postscript or pdf files using the submission page of the workshop accessible through http://dalila.sip.ucm.es/ifl02. After the workshop, we intend to publish a high-quality subset of contributions in the Springer LNCS series. All speakers attending the workshop are invited to submit a paper. Papers for the LNCS proceedings will be refereed according to normal conference standards. -- Ricardo Pe~na e-mail: ricardo(a)sip.ucm.es Departamento Sistemas Informaticos y Programacion Facultad de Informatica Universidad Complutense de Madrid, 28040 MADRID Ph: (+ 34) 91 394 4313 FAX: (+ 34) 91 394 4602 http://dalila.sip.ucm.es/~ricardo

1 0

��Ϣ��!��Ż�!
by tony 11 Apr '02

11 Apr '02

�װ��ѣ� ��ã� ��缼��ţ��޹�˾��ʺ��л��տ��ʼ��ϵ�ϣ��ܳ�Ϊ�� Ҫ��顣��һ�Ҳ��¼��ᾧ��о��ƹ�ͷ�չ�¼��ڻ��Ϣ�� ҵӦ�÷��ĸ��¼��ҵ��:http://www.raeline.net email:webmaster@raeline.net лл�� ˾��2000��ȫ��ʻ��Ƴ��²�Ʒ��ȫ��пռ䶼֧ ��ݿ⣨linux+PHP+Mysol;NT+asp+acess��⽫��ֵ��ѡ�� 1.30M�ռ䣫50M��ҵ��䣫1��ȫ�棬��198Ԫ/�ꡣ ��2.50M�ռ䣫100M��ҵ��䣫1��ȫ�棬��248Ԫ/�ꡣ ��3.100M�ռ䣫100M��ҵ��䣫1��ȫ�棬��318Ԫ/�ꡣ ��4.100M�ռ�+100M��䣫1��+��ַ��ģ��վ+��վ��ҵ��Ϣ ��1000Ԫ �� Ǿ��Ϊ��ṩ��õķ��񡣣��ų��ʧ��Ը��˿Ҳ��Ϊ ��һ��Ĳ��ġ��ǳ�ŵ��ⰴʵ��˿ ��ף��ģ�˳�� webmaster of raeline.net webmaster(a)raeline.net ��缼��ţ��޹�˾ --------------------------------------------------------------- �е�Ⱥ��ʼ�,��ר��(http://www.21cmm.com) ��CMM��У(http://www.21cmm.com)��Ŀ��ר��

1 0

RE: More Haskell Blue Sky: Partial Type Annotations
by Simon Peyton-Jones 11 Apr '02

11 Apr '02

Already in GHC, and describe in our paper on scoped type variables: http://research.microsoft.com/~simonpj/papers/scoped-tyvar Simon | -----Original Message----- | From: Ashley Yakeley [mailto:ashley@semantic.org] | Sent: 11 April 2002 12:11 | To: Haskell List | Subject: More Haskell Blue Sky: Partial Type Annotations | | | I sometimes come across a situation when I only want to provide a | _partial_ type annotation, perhaps because the full type has some | variable unified with some variable in some other type annotation, or | something. For instance: | | f :: forall a. [a] -> [a] -> [a] | f x y = g x where | g [] = y | g (_:_) = x | | ...there doesn't seem to be a way of giving a type annotation | for 'g'. | Theoretically it's '[a] -> [a]', but where 'a' is the same as | the 'a' in | the type signature for 'f'. | | Under this proposal, unqualified type variables would be | considered to be | 'free' rather than implicitly forall-qualified. So for instance, any | function could be given the partial type annotation 'a -> b'. For | instance, all these annotations would be the same given this function: | | k :: a | k :: a -> ba | k :: a -> b -> a | k :: forall b. a -> b -> a | k :: forall a b. a -> b -> a | | k x y = x | | ...and these would both be the same, but different from the previous: | | k' :: Int -> ba | k' :: forall b. Int -> b -> Int | | k' x y = x | | And so we could write this: | | f :: forall a. [a] -> [a] -> [a] | f x y = g x where | g :: [a] -> [a] -- partial annotation may be sufficient | g [] = y | g (_:_) = x | | I admit that's a bit of a change, and might break programs... In | addition, it doesn't address the occasional need to tie type | annotations | together, something that has often made me add ugly dummy | arguments used | just for their type. | | -- | Ashley Yakeley, Seattle WA | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

1 0

does this have a name (recusive datatypes)
by Hal Daume III 10 Apr '02

10 Apr '02

Does this have a name: > data S s a = Nil | S a (s (S s a)) it seems to capture the essense of many recursive data structures. With: > newtype Id a = Id a > newtype Pair a = Pair (a,a) we get that: lists are isomorphic to S Id binary trees are isomorphic to S Pair rose trees are isomorphic to S [] probably more... Is there any theory about what types of recursive data structures can be captured with "S" and what types cannot? It seems that those datastructures which are isomorphic to S x for some x (satisfying certain properties) are exactly those on which one can apply things like maps, filters and folds. For instance, > class Map s where map :: (a -> b) -> s a -> s b > instance Map Id where map f (Id i) = Id (f i) > instance Map Pair where map f (Pair (a,b)) = Pair (f a, f b) > instance Map [] where map = Prelude.map > instance Map s => Map (S s) where > map f Nil = Nil > map f (S a ss) = S (f a) (map f ss) (note i haven't actually loaded this class stuff in a compiler so i might have a typo or soemthing, but it should be clear). it seems the same can be applied to folds and filters, so certainly if s is a functor, so is S s, but what more can we say? Also, if we want to write a show instance for S s, this seems to be impossible. Is it? If so, is this a weakness in Haskell (cyclic instance declarations) or is it theoretically not possible? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

3 4