[Haskell-cafe] APLAS 2013 second call for papers
===
APLAS 2013
11th Asian Symposium on Programming Languages and Systems
9-11 December 2013
Melbourne, Australia (colocated with CPP 2013)
CALL FOR PAPERS
===
==
BACKGROUND
==
APLAS aims to stimulate programming language research by providing a
forum for the presentation of latest results and the exchange of ideas
in programming languages and systems. APLAS is based in Asia, but is
an international forum that serves the worldwide programming language
community.
APLAS is sponsored by the Asian Association for Foundation of Software
(AAFS) founded by Asian researchers in cooperation with many researchers
from Europe and the USA. Past APLAS symposiums were successfully held
in Kyoto ('12), Kenting ('11), Shanghai ('10), Seoul ('09), Bangalore
('08), Singapore ('07), Sydney ('06), Tsukuba ('05), Taipei ('04) and
Beijing ('03) after three informal workshops. Proceedings of the past
symposiums were published in Springer's LNCS.
==
TOPICS
==
The symposium is devoted to foundational and practical issues in
programming languages and systems. Papers are solicited on topics such
as
* semantics, logics, foundational theory;
* design of languages, type systems and foundational calculi;
* domain-specific languages;
* compilers, interpreters, abstract machines;
* program derivation, synthesis and transformation;
* program analysis, verification, model-checking;
* logic, constraint, probabilistic and quantum programming;
* software security;
* concurrency and parallelism;
* tools and environments for programming and implementation.
Topics are not limited to those discussed in previous symposiums.
Papers identifying future directions of programming and those
addressing the rapid changes of the underlying computing platforms
are especially welcome. Demonstration of systems and tools in the
scope of APLAS are welcome to the System and Tool presentations
category. Authors concerned about the appropriateness of a topic
are welcome to consult with program chair prior to submission.
==
SUBMISSION
==
We solicit submissions in two categories:
*Regular research papers* describing original scientific research
results, including tool development and case studies. Regular
research papers should not exceed 16 pages in the Springer LNCS
format, including bibliography and figures. They should clearly
identify what has been accomplished and why it is significant.
Submissions will be judged on the basis of significance, relevance,
correctness, originality, and clarity. In case of lack of space,
proofs, experimental results, or any information supporting the
technical results of the paper could be provided as an appendix or a
link to a web page, but reviewers are not obliged to read them.
*System and Tool presentations* describing systems or tools that support
theory, program construction, reasoning, or program execution in the
scope of APLAS. System and Tool presentations are expected to be
centered around a demonstration. The paper and the demonstration
should identify the novelties of the tools and use motivating
examples. System and Tool papers should not exceed 8 pages in the
Springer LNCS format, including bibliography and figures. Submissions
will be judged based on both the papers and the described systems or
tools. It is highly desirable that the tools are available on the
web.
Papers should be submitted electronically via the submission web page:
https://www.easychair.org/conferences/?conf=aplas2013
Acceptable formats are PostScript or PDF. Submitted papers must be
unpublished and not submitted for publication elsewhere. Papers must
be written in English. The proceedings will be published as a volume
in Springer's LNCS series. Accepted papers must be presented at the
conference. (While the general chair and the program chair cannot
submit papers, other members of the program committee can.)
=
DATES
=
Abstract due:10 June 2013 (Monday), 23:59 UTC
Submission due: 14 June 2013 (Friday), 23:59 UTC
Notification:26 August 2013 (Monday)
Final paper due: 19 September 2013 (Thursday)
Conference: 9-11 December 2013 (Monday-Wednesday)
==
ORGANIZERS
==
General chair:
Peter Schachte (University of Melbourne)
Program chair:
Chung-chieh Shan (Indiana University)
Program committee:
Filippo Bonchi (CNRS, ENS-Lyon, France)
Yu-Fang Chen (Academia Sinica, Taiwan)
Shigeru Chiba (The University of Tokyo, Japan)
Jacques Garrigue (Nagoya University, Japan)
Robert Glück (University of Copenhagen, Denmark)
R. Govindarajan (Indian Institute of Science, India)
Kazuhiro Inaba (Google, Inc., Japan)
Jie-Hong Roland Jiang (National Taiwan University, Taiwan)
Shin-ya Katsumata (Kyoto University, Japan)
Gabriele Keller
[Haskell-cafe] APLAS 2013 call for papers
===
APLAS 2013
11th Asian Symposium on Programming Languages and Systems
9-11 December 2013
Melbourne, Australia (colocated with CPP 2013)
CALL FOR PAPERS
===
==
BACKGROUND
==
APLAS aims to stimulate programming language research by providing a
forum for the presentation of latest results and the exchange of ideas
in programming languages and systems. APLAS is based in Asia, but is
an international forum that serves the worldwide programming language
community.
APLAS is sponsored by the Asian Association for Foundation of Software
(AAFS) founded by Asian researchers in cooperation with many researchers
from Europe and the USA. Past APLAS symposiums were successfully held
in Kyoto ('12), Kenting ('11), Shanghai ('10), Seoul ('09), Bangalore
('08), Singapore ('07), Sydney ('06), Tsukuba ('05), Taipei ('04) and
Beijing ('03) after three informal workshops. Proceedings of the past
symposiums were published in Springer's LNCS.
==
TOPICS
==
The symposium is devoted to foundational and practical issues in
programming languages and systems. Papers are solicited on topics such
as
* semantics, logics, foundational theory;
* design of languages, type systems and foundational calculi;
* domain-specific languages;
* compilers, interpreters, abstract machines;
* program derivation, synthesis and transformation;
* program analysis, verification, model-checking;
* logic, constraint, probabilistic and quantum programming;
* software security;
* concurrency and parallelism;
* tools and environments for programming and implementation.
Topics are not limited to those discussed in previous symposiums.
Papers identifying future directions of programming and those
addressing the rapid changes of the underlying computing platforms
are especially welcome. Demonstration of systems and tools in the
scope of APLAS are welcome to the System and Tool presentations
category. Authors concerned about the appropriateness of a topic
are welcome to consult with program chair prior to submission.
==
SUBMISSION
==
We solicit submissions in two categories:
*Regular research papers* describing original scientific research
results, including tool development and case studies. Regular
research papers should not exceed 16 pages in the Springer LNCS
format, including bibliography and figures. They should clearly
identify what has been accomplished and why it is significant.
Submissions will be judged on the basis of significance, relevance,
correctness, originality, and clarity. In case of lack of space,
proofs, experimental results, or any information supporting the
technical results of the paper could be provided as an appendix or a
link to a web page, but reviewers are not obliged to read them.
*System and Tool presentations* describing systems or tools that support
theory, program construction, reasoning, or program execution in the
scope of APLAS. System and Tool presentations are expected to be
centered around a demonstration. The paper and the demonstration
should identify the novelties of the tools and use motivating
examples. System and Tool papers should not exceed 8 pages in the
Springer LNCS format, including bibliography and figures. Submissions
will be judged based on both the papers and the described systems or
tools. It is highly desirable that the tools are available on the
web.
Papers should be submitted electronically via the submission web page:
https://www.easychair.org/conferences/?conf=aplas2013
Acceptable formats are PostScript or PDF. Submitted papers must be
unpublished and not submitted for publication elsewhere. Papers must
be written in English. The proceedings will be published as a volume
in Springer's LNCS series. Accepted papers must be presented at the
conference. (While the general chair and the program chair cannot
submit papers, other members of the program committee can.)
=
DATES
=
Abstract due:10 June 2013 (Monday), 23:59 UTC
Submission due: 14 June 2013 (Friday), 23:59 UTC
Notification:26 August 2013 (Monday)
Final paper due: 19 September 2013 (Thursday)
Conference: 9-11 December 2013 (Monday-Wednesday)
==
ORGANIZERS
==
General chair:
Peter Schachte (University of Melbourne)
Program chair:
Chung-chieh Shan (Indiana University)
Program committee:
Filippo Bonchi (CNRS, ENS-Lyon, France)
Yu-Fang Chen (Academia Sinica, Taiwan)
Shigeru Chiba (The University of Tokyo, Japan)
Jacques Garrigue (Nagoya University, Japan)
Robert Glück (University of Copenhagen, Denmark)
R. Govindarajan (Indian Institute of Science, India)
Kazuhiro Inaba (Google, Inc., Japan)
Jie-Hong Roland Jiang (National Taiwan University, Taiwan)
Shin-ya Katsumata (Kyoto University, Japan)
Gabriele Keller
[Haskell-cafe] ML Workshop: register early by August 15
ACM SIGPLAN Workshop on ML Sunday, 18 September 2011, Tokyo, Japan (co-located with ICFP) http://conway.rutgers.edu/ml2011/ CALL FOR PARTICIPATION * Early Registration deadline is August 15! * The ML family of programming languages includes dialects known as Standard ML, Objective Caml, and F#. These languages have inspired a large amount of computer-science research, both practical and theoretical. This workshop aims to provide a forum for discussion and research on ML and related technology (higher-order, typed, or strict languages). The format of ML 2011 will continue the return in 2010 to a more informal model: a workshop with presentations selected from submitted abstracts. Presenters will be invited to submit working notes, source code, and extended papers for distribution to the attendees, but the workshop will not publish proceedings, so any contributions may be submitted for publication elsewhere. We hope that this format will encourage the presentation of exciting (if unpolished) research and deliver a lively workshop atmosphere. INVITED SPEAKERS Naoki Kobayashi (Tohoku University) Atsushi Ohori (Tohoku University) ACCEPTED TALKS Efficiently scrapping boilerplate code in OCaml Dmitri Boulytchev, Sergey Mechtaev Implementing implicit self-adjusting computation (short talk) Yan Chen, Joshua Dunfield, Matthew A. Hammer, Umut A. Acar Lightweight typed customizable unmarshaling Pascal Cuoq, Damien Doligez, Julien Signoles Adding GADTs to OCaml: the direct approach Jacques Garrigue, Jacques Le Normand A demo of Coco: a compiler of monadic coercions in ML (short talk) Nataliya Guts, Michael Hicks, Nikhil Swamy, Daan Leijen Verifying liveness properties of ML programs M. M. Lester, R. P. Neatherway, C.-H. L. Ong, S. J. Ramsay MixML remixed Andreas Rossberg, Derek Dreyer Report on OCaml type debugger Kanae Tsushima, Kenichi Asai Camomile: a Unicode library for OCaml (short talk) Yoriyuki Yamagata PROGRAM COMMITTEE Amal Ahmed (Indiana University) Andrew Tolmach (Portland State University) Anil Madhavapeddy (University of Cambridge) Chung-chieh Shan (chair) Joshua Dunfield (Max Planck Institute for Software Systems) Julia Lawall (University of Copenhagen) Keisuke Nakano (University of Electro-Communications) Martin Elsman (SimCorp) Walid Taha (Halmstad University) STEERING COMMITTEE Eijiro Sumii (chair) (Tohoku University) Andreas Rossberg (Google) Jacques Garrigue (Nagoya University) Matthew Fluet (Rochester Institute of Technology) Robert Harper (Carnegie Mellon University) Yaron Minsky (Jane Street) signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Domain-Specific Languages: Call for Participation
DSL 2011: IFIP Working Conference on Domain-Specific Languages 6-8 September 2011, Bordeaux, France Call for Participation: Online registration deadline July 30, 2011 Details of the program and accommodation are available at http://dsl2011.bordeaux.inria.fr. == Invited Speakers == - Jeremy Gibbons - University of Oxford, UK. - Claude Kirchner - INRIA, France. == Distilled Tutorials on Domain-Specific Languages == The purpose of these tutorials are not to give a general overview, but to make the attendees aware of one point and to make them master it. - Jerzy Karczmarczuk. Specific scientific data structures, and their processing. - Oleg Kiselyov. Implementing explicit and finding implicit sharing in embedded DSL. - Keiko Nakata. A total interpreter for While with interactive I/O. - Josef Svenningsson. Combining deep and shallow embeddings for EDSLs. - Walid Taha. Accurate programming: thinking about programs in terms of properties. - William Cook. Build your own partial evaluator in 90 minutes. == DSL Technical Papers == - Basile Starynkevitch. MELT a Translated Domain Specific Language Embedded in the GCC Compiler. - Azer Bestavros and Assaf Kfoury. A Domain-Specific Language for the Incremental and Modular Design of Large-Scale Verifiably-Safe Flow Networks. - Tiark Rompf, Kevin J. Brown, Hassan Chafi, Hyoukjoong Lee, Arvind K. Sujeeth, Martin Odersky and Kunle Olukotun. Building-Blocks for Performance Oriented DSLs. - Dominic Orchard and Alan Mycroft. Efficient and Correct Stencil Computation via Pattern Matching and Static Typing. - Tim Bauer, Martin Erwig, Alan Fern and Jervis Pinto. Adaptation-Based Programming in Haskell. - Eric Walkingshaw and Martin Erwig. A DSEL for Studying and Explaining Causation. - Lucas Beyak and Jacques Carette. SAGA: A DSL for story management. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Deadline June 17: ACM SIGPLAN Workshop on ML
ACM SIGPLAN Workshop on ML Sunday, 18 September 2011, Tokyo, Japan (co-located with ICFP) http://conway.rutgers.edu/ml2011/ CALL FOR CONTENT The ML family of programming languages includes dialects known as Standard ML, Objective Caml, and F#. These languages have inspired a large amount of computer-science research, both practical and theoretical. This workshop aims to provide a forum for discussion and research on ML and related technology (higher-order, typed, or strict languages). The format of ML 2011 will continue the return in 2010 to a more informal model: a workshop with presentations selected from submitted abstracts. Presenters will be invited to submit working notes, source code, and extended papers for distribution to the attendees, but the workshop will not publish proceedings, so any contributions may be submitted for publication elsewhere. We hope that this format will encourage the presentation of exciting (if unpolished) research and deliver a lively workshop atmosphere. SCOPE We seek research presentations on topics related to ML, including but not limited to * applications: case studies, experience reports, pearls, etc. * extensions: higher forms of polymorphism, generic programming, objects, concurrency, distribution and mobility, semi-structured data handling, etc. * type systems: inference, effects, overloading, modules, contracts, specifications and assertions, dynamic typing, error reporting, etc. * implementation: compilers, interpreters, type checkers, partial evaluators, runtime systems, garbage collectors, etc. * environments: libraries, tools, editors, debuggers, cross-language interoperability, functional data structures, etc. * semantics: operational, denotational, program equivalence, parametricity, mechanization, etc. Research presentations should describe new ideas, experimental results, significant advances in ML-related projects, or informed positions regarding proposals for next-generation ML-style languages. We especially encourage presentations that describe work in progress, that outline a future research agenda, or that encourage lively discussion. In addition to research presentations, we seek both Status Reports and Demos that emphasize the practical application of ML research and technology. Status Reports: Status reports are intended as a way of informing others in the ML community about the status of ML-related research or implementation projects, as well as communicating insights gained from such projects. Status reports need not present original research, but should deliver new information. In the abstract submission, describe the project and the specific technical content to be presented. Demos: Live demonstrations or tutorials should show new developments, interesting prototypes, or work in progress, in the form of tools, libraries, or applications built on or related to ML. In the abstract submission, describe the demo and its technical content, and be sure to include the demo's title, authors, collaborators, references, and acknowledgments. (Please note that you will need to provide all the hardware and software required for your demo; the workshop organizers are only able to provide a projector.) Each presentation should take 20-25 minutes, except demos, which should take 10-15 minutes. The exact time will be decided based on the number of accepted submissions. We plan to make videos of the presentations available on ACM Digital Library. SUBMISSION INSTRUCTIONS Email submissions to ccshan AT cs.rutgers.edu. Submissions should be at most two pages, in PDF format, and printable on US Letter or A4 sized paper. Persons for whom this poses a hardship should contact the program chair. Submissions longer than a half a page should include a one-paragraph synopsis suitable for inclusion in the workshop program. IMPORTANT DATES * 2011-06-17: Submission * 2011-07-22: Notification * 2011-09-18: Workshop PROGRAM COMMITTEE Amal Ahmed (Indiana University) Andrew Tolmach (Portland State University) Anil Madhavapeddy (University of Cambridge) Chung-chieh Shan (chair) (Rutgers University) Joshua Dunfield (Max Planck Institute for Software Systems) Julia Lawall (University of Copenhagen) Keisuke Nakano (University of Electro-Communications) Martin Elsman (SimCorp) Walid Taha (Halmstad University) STEERING COMMITTEE Eijiro Sumii (chair) (Tohoku University) Andreas Rossberg (Google) Jacques Garrigue (Nagoya University) Matthew Fluet (Rochester Institute of Technology) Robert Harper (Carnegie Mellon University) Yaron Minsky (Jane Street) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
Daryoush Mehrtash dmehrt...@gmail.com wrote in haskell-cafe: I am confused about this comment: Mostly we preferred (as do the domain experts we target) to write probabilistic models in direct style rather than monadic In the haskell implementation of the lawn model there are two different version of the grassModel ( https://github.com/rst76/probability/blob/master/src/Lawn.hs)... By domain expert preferring direct style do you mean that they prefer the first version over the 2nd version? No, there is no way to write probabilistic models in direct style in Haskell, and domain experts prefer neither Haskell version you showed. A symptom of direct style is being able to write something like flip 0.3 flip 0.5 where () takes two Bool arguments. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
Daryoush Mehrtash dmehrt...@gmail.com wrote in article AANLkTim0LTOviud2fyzU7NAsraQMuCKa=qyfroxn8...@mail.gmail.com in gmane.comp.lang.haskell.cafe: I see the problem now. But I am confused as to why there are no Bool class (like Num, Fractional...) in Haskell. If I had such a class then the problem is solved, (by making the pm a an instance of it) right? Or are there still more issues that I am not seeing? Sorry, I gave a bad example. Here are two more general symptoms of direct style: being able to write something like f (if flip 0.3 then LT else EQ) where f is an existing function that takes an Ordering argument, and even being able to write something like and (map flip [0.3, 0.5]) where and :: [Bool] - Bool map :: (a - b) - [a] - [b] are existing functions. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
Arnaud Clère arnaud.cl...@free.fr wrote in article ik64e9$j6a$1...@dough.gmane.org in gmane.comp.lang.haskell.cafe: On 24/02/2011 09:30, o...@okmij.org wrote: The sort of laziness needed for non-deterministic programming calls for first-class store. It can be emulated, albeit *imperfectly*, for example, as was described in the ICFP09 paper. What do you mean by imperfectly? I think Oleg meant that, because the garbage collector only understands the native store and not our emulation of first-class stores, cells of a first-class store that are no longer referenced will nevertheless not be garbage-collected until the store itself is garbage-collected. What we need is a way to tell the garbage collector that the store reference and the cell reference are both needed to access the data so the data can be garbage-collected as soon as *either* the store reference *or the cell reference* is. (Analogy from the capabilities literature: the key and the lock are both needed to open the door so the door can be garbage-collected as soon as either the key or the lock is.) Any thoughts on how to achieve that? Do you think implementing 'probM' with 'share' would lead to the same performance problems you experienced in probM.hs? No, implementing probM with share would be like what OCaml HANSEI currently does, except in monadic notation rather than direct style. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
Leon Smith leon.p.sm...@gmail.com wrote in article AANLkTikF6EX4U+uTwNcrdFZPj-ijTWb74o2W_RJMGOe=@mail.gmail.com in gmane.comp.lang.haskell.cafe: On Wed, Feb 23, 2011 at 10:52 AM, Chung-chieh Shan ccs...@cs.rutgers.edu wrote: Mostly we preferred (as do the domain experts we target) to write probabilistic models in direct style rather than monadic style. Haskell's laziness doesn't help -- in fact, to avoid running out of memory, we'd have to defeat that memoization by sprinkling () - throughout the types. I don't think that () - is even guaranteed to work... That's quite true. Then again, it's not guaranteed that () - is needed for good memory usage. We just need a sufficiently smart compiler! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
On 2011-02-24T16:20:46-0600, Antoine Latter wrote: On Thu, Feb 24, 2011 at 12:57 PM, Chung-chieh Shan wrote: What we need is a way to tell the garbage collector that the store reference and the cell reference are both needed to access the data so the data can be garbage-collected as soon as *either* the store reference *or the cell reference* is. (Analogy from the capabilities literature: the key and the lock are both needed to open the door so the door can be garbage-collected as soon as either the key or the lock is.) Any thoughts on how to achieve that? Here's a weak cell which is a candidate for GC as soon as either the cell or the key is lost: http://hpaste.org/44280/weak_ref_needing_both_halves That's promising! The lock I have in mind would probably be a map from Int to weak pointers. I'm unfamiliar with System.Mem.Weak so I'll have to study this code further. What is addFinalizer lock (finalize wk) for? It seems wk doesn't have any finalizers to run. Thanks! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HANSEI in Haskell?
Hello! Thank you for your interest. Daryoush Mehrtash dmehrt...@gmail.com wrote in haskell-cafe: Is the Embedded domain-specific language HANSEI for probabilistic models and (nested) inference described in: http://okmij.org/ftp/kakuritu/index.html#implementation available in Haskell? The closest to that I know of is this one: http://d.hatena.ne.jp/rst76/20100706 https://github.com/rst76/probability Or you can apply this monad transformer to a probability monad: http://sebfisch.github.com/explicit-sharing/ Is there a reason why the author did the package in Ocaml rather than Haskell? Mostly we preferred (as do the domain experts we target) to write probabilistic models in direct style rather than monadic style. Haskell's laziness doesn't help -- in fact, to avoid running out of memory, we'd have to defeat that memoization by sprinkling () - throughout the types. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ACM SIGPLAN Workshop on ML
ACM SIGPLAN Workshop on ML Sunday, 18 September 2011, Tokyo, Japan (co-located with ICFP) http://conway.rutgers.edu/ml2011/ CALL FOR CONTENT The ML family of programming languages includes dialects known as Standard ML, Objective Caml, and F#. These languages have inspired a large amount of computer-science research, both practical and theoretical. This workshop aims to provide a forum for discussion and research on ML and related technology (higher-order, typed, or strict languages). The format of ML 2011 will continue the return in 2010 to a more informal model: a workshop with presentations selected from submitted abstracts. Presenters will be invited to submit working notes, source code, and extended papers for distribution to the attendees, but the workshop will not publish proceedings, so any contributions may be submitted for publication elsewhere. We hope that this format will encourage the presentation of exciting (if unpolished) research and deliver a lively workshop atmosphere. SCOPE We seek research presentations on topics related to ML, including but not limited to * applications: case studies, experience reports, pearls, etc. * extensions: higher forms of polymorphism, generic programming, objects, concurrency, distribution and mobility, semi-structured data handling, etc. * type systems: inference, effects, overloading, modules, contracts, specifications and assertions, dynamic typing, error reporting, etc. * implementation: compilers, interpreters, type checkers, partial evaluators, runtime systems, garbage collectors, etc. * environments: libraries, tools, editors, debuggers, cross-language interoperability, functional data structures, etc. * semantics: operational, denotational, program equivalence, parametricity, mechanization, etc. Research presentations should describe new ideas, experimental results, significant advances in ML-related projects, or informed positions regarding proposals for next-generation ML-style languages. We especially encourage presentations that describe work in progress, that outline a future research agenda, or that encourage lively discussion. In addition to research presentations, we seek both Status Reports and Demos that emphasize the practical application of ML research and technology. Status Reports: Status reports are intended as a way of informing others in the ML community about the status of ML-related research or implementation projects, as well as communicating insights gained from such projects. Status reports need not present original research, but should deliver new information. In the abstract submission, describe the project and the specific technical content to be presented. Demos: Live demonstrations or tutorials should show new developments, interesting prototypes, or work in progress, in the form of tools, libraries, or applications built on or related to ML. In the abstract submission, describe the demo and its technical content, and be sure to include the demo's title, authors, collaborators, references, and acknowledgments. (Please note that you will need to provide all the hardware and software required for your demo; the workshop organizers are only able to provide a projector.) Each presentation should take 20-25 minutes, except demos, which should take 10-15 minutes. The exact time will be decided based on the number of accepted submissions. We plan to make videos of the presentations available on ACM Digital Library. SUBMISSION INSTRUCTIONS Email submissions to ccshan AT cs.rutgers.edu. Submissions should be at most two pages, in PDF format, and printable on US Letter or A4 sized paper. Persons for whom this poses a hardship should contact the program chair. Submissions longer than a half a page should include a one-paragraph synopsis suitable for inclusion in the workshop program. IMPORTANT DATES * 2011-06-17: Submission * 2011-07-22: Notification * 2011-09-18: Workshop PROGRAM COMMITTEE Amal Ahmed (Indiana University) Andrew Tolmach (Portland State University) Anil Madhavapeddy (University of Cambridge) Chung-chieh Shan (chair) (Rutgers University) Joshua Dunfield (Max Planck Institute for Software Systems) Julia Lawall (University of Copenhagen) Keisuke Nakano (University of Electro-Communications) Martin Elsman (SimCorp) Walid Taha (Halmstad University) STEERING COMMITTEE Eijiro Sumii (chair) (Tohoku University) Andreas Rossberg (Google) Jacques Garrigue (Nagoya University) Matthew Fluet (Rochester Institute of Technology) Robert Harper (Carnegie Mellon University) Yaron Minsky (Jane Street) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] parsing exercise
Sebastian Fischer fisc...@nii.ac.jp wrote in article AANLkTimZfqoLG5z=vsxsjltn_r5xh+ed49-ngknhn...@mail.gmail.com in gmane.comp.lang.haskell.cafe: I expect writing this function to be quite tedious (ignore commas in parens, ignore parens in strings, quotation, ...) and would prefer to copy code from some parsing library. Do you have an idea what I could use? Or how to solve it from scratch in a few lines? Maybe Text.Show.Pretty.parseValue in the pretty-show package can help? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Insert wit here. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type System vs Test Driven Development
Evan Laforge qdun...@gmail.com wrote in article aanlktinfyp-bpbs1ga8_=o9wcrhe+duux-vfrmdl2...@mail.gmail.com in gmane.comp.lang.haskell.cafe: Incidentally, I've never been able to figure out how to use QuickCheck. Maybe it has more to do with my particular app, but QuickCheck seems to expect simple input data and simple properties that should hold relating the input and output, and in my experience that's almost never true. For instance, I want to ascertain that a function is true for compatible signals and false for incompatible ones, where the definition of compatible is quirky and complex. I can make quickcheck generate lots of random signals, but to make sure the compatible is right means reimplementing the compatible function. Or I just pick a few example inputs and expected outputs. Besides those example inputs and expected outputs, what about: If two signals are (in)compatible then after applying some simple transformations to both they remain (in)compatible? A certain family of signals is always compatible with another family of signals? Silence is compatible with every signal? Every non-silent signal is (in)compatible with itself (perhaps after applying a transformation)? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig INSERT PARTISAN STATEMENT HERE ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Formatting function types
Lauri Alanko l...@iki.fi wrote in article 20101230133355.gb...@melkinpaasi.cs.helsinki.fi in gmane.comp.lang.haskell.cafe: The following is much clearer: openTempFile :: FilePath - String - IO (FilePath, Handle) (Possibly with the arrows aligned.) I can't understand how the arrows first convention still lingers so strongly when it is (to me) so obviously wrong and misleading. What about chains of $ in terms? (Both - in types and $ in terms associate to the right. What about + - * / in terms, which associate to the left?) -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Where is Galt's Gulch? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: If the local variable can be changed ...
zaxis z_a...@163.com wrote in article 27844016.p...@talk.nabble.com in gmane.comp.lang.haskell.cafe: As we know, the local variable is allocated on stack which is thread safe. It's not. http://en.wikipedia.org/wiki/Funarg_problem#Example -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig masha'allah insha'allah ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: looking for a good algorithm
Hong Yang hyang...@gmail.com wrote in article f31db34d090452x7786572ay4482dffc4824a...@mail.gmail.com in gmane.comp.lang.haskell.cafe: I want to shuffle the rows to maximize the number of columns whose first 100 rows have at least one number Sounds like the maximum coverage problem, which is said to be NP-hard. [citation needed] http://en.wikipedia.org/wiki/Maximum_coverage_problem -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig The answer to the ultimate question of life the universe and everything = 42 but usually it's not. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Finally tagless - stuck with implementation of?lam
Robert Atkey bob.at...@ed.ac.uk wrote in article 1254778973.3675.42.ca...@bismuth in gmane.comp.lang.haskell.cafe: To implement the translation of embedded language types to Haskell types in Haskell we use type families. This type-to-type translation is indeed the crux of the trickiness. By the way, Section 4.3 of our (JFP) paper describes how to follow such a translation without type families. If I were to avoid type families in Haskell, I would make Symantics into a multiparameter type class class HOAS repr arrow int where lam :: (repr a - repr b) - repr (arrow a b) app :: repr (arrow a b) - repr a - repr b fix :: (repr a - repr a) - repr a let_ :: repr a - (repr a - repr b) - repr b int :: int - repr int add :: repr int - repr int - repr int sub :: repr int - repr int - repr int mul :: repr int - repr int - repr int The underlying problem with the implementation of 'lam' is that you have to pick an evaluation order for the side effects you want in the semantics of your embedded language. The two obvious options are call-by-name and call-by-value. (Section 5 of our (JFP) paper addresses both CBN and CBV.) -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Here's a souvenir of it. He made me write this down so I'd remember to get this book and read it. Transcendent Speculations on Apparent Design in the Fate of the Individual, that's a mouthful isn't it. I wrote this down at gun-point. - Gaddis ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Finally tagless - stuck with implementation?of?lam
Don Stewart d...@galois.com wrote in article 20091006031054.gb18...@whirlpool.galois.com in gmane.comp.lang.haskell.cafe: ccshan: (Section 5 of our (JFP) paper addresses both CBN and CBV.) Do you have a link to the paper? Sorry, here it is. http://www.cs.rutgers.edu/~ccshan/tagless/jfp.pdf -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Here's a souvenir of it. He made me write this down so I'd remember to get this book and read it. Transcendent Speculations on Apparent Design in the Fate of the Individual, that's a mouthful isn't it. I wrote this down at gun-point. - Gaddis ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: combinatorial search with running bound
I wish I had enough of your code to type-check my code and perhaps even
try running it!
Michael Mossey m...@alumni.caltech.edu wrote in article
3942.75.50.175.130.1253997756.squir...@mail.alumni.caltech.edu in
gmane.comp.lang.haskell.cafe:
-- This is state used in the state monad.
data SearchState = SearchState { -- running maximum:
ssMaximum :: Int
-- remember the full list of right boxes
-- so we can initiate a new outer loop
, ssRights :: [Box]
}
boxesSep2 :: [Box] - [Box] - Int
boxesSep2 lefts rights =
let ls = sortBy ((flip compare) `on` rightExtent) lefts
rs = sortBy ((flip compare) `on` leftExtent) rights
in fst $ runState (boxesSep2' ls rs) (SearchState minBound rs)
First, ssRights never changes, so it should not be kept inside the state
monad. Also, ssMaximum is already stored in the state, so boxesSep2'
need not return it.
data SearchState = SearchState { ssMaximum :: Int }
boxesSep2 :: [Box] - [Box] - Int
boxesSep2 lefts rights =
let ls = sortBy ((flip compare) `on` rightExtent) lefts
rs = sortBy ((flip compare) `on` leftExtent) rights
in ssMaximum (execState (boxesSep2' ls rs) (SearchState minBound))
boxesSep2' :: [Box] - [Box] - State SearchState Int
-- Termination of algorithm:
boxesSep2' [] _ = gets ssMaximum
-- Initiate a new inner loop:
boxesSep2' (l:ls) [] = do
rights - gets ssRights
boxesSep' ls rights
Instead, boxesSep2' can simply iterate through the left boxes.
boxesSep2' :: [Box] - [Box] - State SearchState ()
boxesSep2' ls rs = mapM_ (flip boxesSep2'' rs) ls
-- Common case:
boxesSep2' lss@(l:ls) (r:rs) = do
-- In this way of writing the code, we distinguish between the
-- left/right separation which is the sum of the extents, and the
-- question of whether there is vertical overlap.
let v = isVerticalOverlap l r
sep = lrSeparation l r
ss - get
let max = ssMaximum ss
if sep = max
then boxesSep' ls (ssRights ss) --Here we prune (initiate new inner
loop)
else do
-- Update max is needed:
when v (put ss { ssMaximum = sep })
boxesSep' lss rs
The inner loop through the right boxes doesn't need to maintain the full
list of right boxes, because that list is already part of the closure
(flip boxesSep2'' rs) above.
boxesSep2'' :: Box - [Box] - State SearchState ()
boxesSep2'' l [] = return ()
boxesSep2'' l (r:rs) = do
let v = isVerticalOverlap l r
sep = lrSeparation l r
max - gets ssMaximum
when (sep max) (do
when v (put (SearchState { ssMaximum = sep }))
boxesSep2'' l rs)
Personally, I think it's slightly clearer to drop the SearchState
constructor and use foldl and explicit state-passing instead of mapM_
and the state monad. But that's less crucial than removing the full
rights list from the state. (In the state, the full rights list is a
defunctionalized delimited continuation.)
When you ask for a pair of boxes, How closely can they be brought together
without intersection? that provides a lower bound on the question How
closely can the groups be brought together? (I.e. for that pair of boxes,
bring them any closer and they intersect, so it is a lower bound.) The
maximum of all these lower bounds in the minimum needed separation.
I think I see.
Cheers!
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
Computer Science is no more about computers
than astronomy is about telescopes.
-Edsger Dijkstra
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: combinatorial search with running bound
Michael Mossey m...@alumni.caltech.edu wrote in article 3942.75.50.175.130.1253997756.squir...@mail.alumni.caltech.edu in gmane.comp.lang.haskell.cafe: The problem is to determine how closely the groups can be brought together without any boxes intersection. The basic algorithm is to consider each pair of boxes and ask if they have any vertical overlap---if so, figure out how closely they can be brought together without intersecting, otherwise ignore them. Then take the maximum of those numbers. Wouldn't you mean minimum instead of maximum then? I suspect that your code would be clearer without using a state monad. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Computer Science is no more about computers than astronomy is about telescopes. -Edsger Dijkstra ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Unifcation and matching in Abelian groups
John D. Ramsdell ramsde...@gmail.com wrote in article 7687290b0908190243y70541426x3d485267c4a94...@mail.gmail.com in gmane.comp.lang.haskell.cafe: I've been studying equational unification. I decided to test my understanding of it by implementing unification and matching in Abelian groups. I am quite surprised by how little code it takes. Let me share it with you. Thanks! Another small change that might shorten the code is to use Data.Map for linear combinations: type Lin = Data.Map.Map String Int -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Shaik Riaz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: I love purity, but it's killing me.
Paul L nine...@gmail.com wrote in article 856033f20906082224s2b7d5391gdc7a4ed913004...@mail.gmail.com in gmane.comp.lang.haskell.cafe: The open question is whether there exists such a solution that's both elegant and efficient at maintain proper sharing in the object language. What is your criterion for efficient? We certainly can get rid of all interpretive overheads by either having a tagless interpreter (as in Oleg and Shan's paper), or by direct compilation. (BTW, the paper is by Jacques Carette, Oleg Kiselyov, and Chung-chieh Shan.) But so far I don't see how a tagless interpreter could handle sharing when it can't be distinguished in the host language. Indeed, I would agree with those on this thread who have stated that sharing should be distinguished in the host language. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig We want our revolution, and we want it now! -- Marat/Sade We want our revolution, and we'll take it at such time as you've gotten around to delivering it -- Haskell programmer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Pike's Newsqueak talk
Tim Newsham news...@lava.net wrote in article pine.bsi.4.64.0906051608180.14...@malasada.lava.net in gmane.comp.lang.haskell.cafe: Could it be the amb described at http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice/ http://conal.net/blog/posts/smarter-termination-for-thread-racing/ ? It reminds me a little of unamb but is different. I agree, but could it be the amb described there? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig We want our revolution, and we want it now! -- Marat/Sade We want our revolution, and we'll take it at such time as you've gotten around to delivering it -- Haskell programmer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: I love purity, but it's killing me.
On 2009-05-27T03:58:58-0400, Paul L wrote: One possible solution is to further introduce a fixed point data constructor, a Rec or even LetRec to explicitly capture cycles. But then you still incur much overheads interpreting them, I don't understand this criticism -- what interpretive overhead do you mean? Certainly the Rec/LetRec encoding is pretty efficient for one object language with cycles, namely the lambda calculus with Rec or LetRec. :) One concrete way for you to explain what interpretive overhead you mean, if it's not too much trouble, might be to compare a Rec/LetRec encoding of a particular object language to another encoding that does not have the interpretive overhead you mean and is therefore more efficient. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig We want our revolution, and we want it now! -- Marat/Sade We want our revolution, and we'll take it at such time as you've gotten around to delivering it -- Haskell programmer signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Pike's Newsqueak talk
Tim Newsham news...@lava.net wrote in article pine.bsi.4.64.0906051510070.14...@malasada.lava.net in gmane.comp.lang.haskell.cafe: his language also supports an interesting imperative primitive that lets you pick the first available value from a set of channels which isn't available in pure Haskell expressions. Has anyone implemented a primitive like this for Haskell? Could it be the amb described at http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice/ http://conal.net/blog/posts/smarter-termination-for-thread-racing/ ? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig We want our revolution, and we want it now! -- Marat/Sade We want our revolution, and we'll take it at such time as you've gotten around to delivering it -- Haskell programmer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: mapM as a Space Leak
Thomas Hartman tphya...@gmail.com wrote in article 910ddf450903261240p4e4fc8b3pa927fac1b80b2...@mail.gmail.com in gmane.comp.lang.haskell.cafe: Well, that's reassuring. The reason I asked is that the testp function didn't just show poor performance. The state monad implementation actually gave a different answer -- nonterminating, where the pattern matching solution terminated. Indeed, DIFFERENT Haskell programs can give different answers, even on the SAME Haskell implementation. That should not be surprising at all. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 100 Days to close Guantanamo and end torture http://100dayscampaign.org/ http://www.avaaz.org/en/end_the_war_on_terror/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: categories and monoids
Wolfgang Jeltsch g9ks1...@acme.softbase.org wrote in article 200903181116.37073.g9ks1...@acme.softbase.org in gmane.comp.lang.haskell.cafe: Am Dienstag, 17. März 2009 18:43 schrieben Sie: There's no such implication in English. The standard example used by linguists is fake gun. Okay, but this is a corner case isn???t it? Perhaps (depending on what you consider to be a corner case). But then why not take generalized monoid to be a corner case too? And the phrase ???generalized monoid??? has another problem. It???s not a single monoid that is generalized but the ???monoid concept???. The class of monoids is extended to become the class of categories. I'm not sure what problem you mean. Perhaps you have in mind a grammar that defines what strings are well-formed English sentences and a semantics that specifies their denotations (say, their truth conditions), such that it turns out that the meaning of generalized monoid is inappropriate. But what do you have in mind? Linguists typically take adjectives to denote functions from noun meanings to noun meanings. Because linguists also typically take nouns to denote functions, adjectives end up denoting higher-order functions. That's why this message is still generalized on-topic. :) -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Who would have thought LISP would come back to life. Steve Bourne, in an interview about Bourne Shell. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Memoizing partially evaluated computations.
Sebastiaan Visser sfvis...@cs.uu.nl wrote in article d86a7d11-f95f-4a27-a13c-2d78afda2...@cs.uu.nl in gmane.comp.lang.haskell.cafe: Suppose I have a list of IO computations that depends on a few very time consuming pure operations. The pure operations are not dependent on the real world: computation :: [IO Int] computation = [ smallIOfunc timeConsumingPureOperation0 , smallIOfunc timeConsumingPureOperation1 , smallIOfunc timeConsumingPureOperation2 , smallIOfunc timeConsumingPureOperation3 ] where smallIOfunc a = print a return a I take it that, because you do not really have the control to change things `deep' inside the code, it is not an option to redefine computation = [ smallIOfunc x0 , smallIOfunc x1 , smallIOfunc x2 , smallIOfunc x3 ] where smallIOfunc a = print a return a x0 = timeConsumingPureOperation0 x1 = timeConsumingPureOperation1 x2 = timeConsumingPureOperation2 x3 = timeConsumingPureOperation3 Can you define smallIOfunc to be more polymorphic in the monad? That is, can you define a class of monads (MonadBehavior, let's call it) that contains member functions for operations (such as print) you want to perform in smallIOfunc, then write smallIOfunc to be polymorphic over such a monad? If so, you can then implement two instances of this class: one for IO and one for a term representation of behavior. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Who would have thought LISP would come back to life. Steve Bourne, in an interview about Bourne Shell. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Memoizing partially evaluated computations.
On 2009-03-18T21:24:58-0600, Luke Palmer wrote: On Wed, Mar 18, 2009 at 6:21 AM, Chung-chieh Shan ccs...@post.harvard.eduwrote: computation = [ smallIOfunc x0 , smallIOfunc x1 , smallIOfunc x2 , smallIOfunc x3 ] where smallIOfunc a = print a return a x0 = timeConsumingPureOperation0 x1 = timeConsumingPureOperation1 x2 = timeConsumingPureOperation2 x3 = timeConsumingPureOperation3 Um, just to clarify, this code is exactly equivalent to the original, including sharing behavior. The only time a let (or where) clause changes sharing is if the variable is used more than once in the body. Ah, good point! Of course, timeConsumingPureOperation0 above is a metavariable for a Haskell expression, not just a Haskell variable. But I guess I also took smallIOfunc to be a metavariable for a Haskell context (i.e., a Haskell expression with a hole), not just a Haskell function name. You make an important point that sharing is changed only if the variable (such as x0) is used more than once in the body. Let me note that the definition of computation doesn't have to mention x0 multiple times syntactically for x0 to be used more than once. It's enough for x0 to appear once under a lambda. Here's a concrete example: main :: IO () main = once once once :: IO () once = do putStrLn foo putStrLn (unsafePerformIO (putStrLn hello) `seq` world) If I put () - in front of the second-to-last line, then hello appears twice, not once, in the output. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 100 Days to close Guantanamo and end torture http://100dayscampaign.org/ http://www.avaaz.org/en/end_the_war_on_terror/ signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ANNOUNCE: pqueue-mtl, stateful-mtl
Ryan Ingram ryani.s...@gmail.com wrote in article 2f9b2d30902151615n1e8e25e8ubbee20d93c8ec...@mail.gmail.com in gmane.comp.lang.haskell.cafe: You can roll your own pure STT monad, at the cost of performance: Do you (or anyone else) know how to prove this STT implementation type-safe? It seems to be safe but I'm not sure how to prove it. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig A mathematician is a device for turning coffee into theorems. Paul Erdos (1913-1996) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ANNOUNCE: pqueue-mtl, stateful-mtl
Louis Wasserman wasserman.lo...@gmail.com wrote in article ab4284220902160801x51e6c3b6m3a7ee0698ac97...@mail.gmail.com in gmane.comp.lang.haskell.cafe: The point here is that a MonadST instance guarantees that the bottom monad is an ST -- and therefore single-threaded of necessity -- and grants any ST-based monad transformers on top of it access to its single state thread. This approach sounds like Fluet and Morrisett's monadic regions (ICFP 2004, JFP 2006), for which Oleg and I produced a easier-to-use implementation (Haskell 2008). You may find these papers helpful! http://ttic.uchicago.edu/~fluet/research/rgn-monad/ http://okmij.org/ftp/Haskell/regions.html#light-weight -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Attending a mathematics lecture is like walking through a thunderstorm at night. Most of the time you are lost, wet and miserable but at rare intervals there is a flash of lightening and the whole countryside is lit up. - Tom Koerner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Can this be done?
wren ng thornton w...@freegeek.org wrote in article 4993bbee.9070...@freegeek.org in gmane.comp.lang.haskell.cafe: It's ugly, but one option is to just reify your continuations as an ADT, where there are constructors for each function and fields for each variable that needs closing over. Serializing that ADT should be simple (unless some of those functions are higher-order in which case you run into the same problem of how to serialize the function arguments). In GHC's STG machine this representation shouldn't have much overhead, though it does require the developer to do the compiler's job. FWIW, this idea is called defunctionalization (due to Reynolds), and it works for higher-order functions as well (because you can defunctionalize those function arguments in the same way). People in many fields put a lot of effort into turning their programs into state machines... -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Attending a mathematics lecture is like walking through a thunderstorm at night. Most of the time you are lost, wet and miserable but at rare intervals there is a flash of lightening and the whole countryside is lit up. - Tom Koerner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Delimited continuations: please comment
Cristiano Paris cristiano.pa...@gmail.com wrote in article afc62ce20902120855i77acf725p1069aab21037a...@mail.gmail.com in gmane.comp.lang.haskell.cafe: In effect, this is a bit different from the syscall service routine described by Oleg, as the scheduler function reacts in different ways for subsequent calls (the first time feeds Hello!, the second one World!, in a nice monad style). Yet, I liked the separation between the scheduler and the job, which are two completely different values and which I tried to keep. It's not unheard of for the scheduler to react in different ways to the same system call -- I'm thinking of reading from a file, for example. As this is (almost) my first time using delconts, could you provide feedback, comments, opinions about my piece of code and the topic in general (convenience, performances, alternatives and so on)? You clearly understand the whole idea, and your code demonstrates it in a nice way. Oleg and I have found this programming style particularly convenient when we need to - fork processes (i.e., backtrack in the monad), - run the same processes under different schedulers (e.g., a debugger), - nest the applications of schedulers (i.e., provide virtualization). -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Attending a mathematics lecture is like walking through a thunderstorm at night. Most of the time you are lost, wet and miserable but at rare intervals there is a flash of lightening and the whole countryside is lit up. - Tom Koerner ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Different return type?
John Ky newho...@gmail.com wrote in article
bd4fcb030901181744i2b26172bv2328974ff911f...@mail.gmail.com in
gmane.comp.lang.haskell.cafe:
data Person = Person { name :: String, ... }
data Business = Business { business_number :: Int, ...}
key person = name person
key business = business_number business
Let's make this concrete:
data Person = Person { name :: String, age :: Integer }
data Business = Business { business_number :: Int, revenue :: Double }
key person = name person
key business = business_number business
Even without dependent types, you can do the following (but of course,
you lose some syntactic sugar for records):
data Individual k v = Individual { key :: k, value :: v }
type Person = Individual String Integer
type Business = Individual Int Double
name :: Person - String
name = key
age :: Person - Integer
age = value
business_number :: Business - Int
business_number = key
revenue :: Business - Double
revenue = value
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
May all beings be well and happy!~
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Fwd: Haskell as a religion
Henning Thielemann schlepp...@henning-thielemann.de wrote in article
494ae7a3.3000...@henning-thielemann.de in gmane.comp.lang.haskell.cafe:
In C/C++ referential transparent functions code can be declared by
appending a 'const' to the prototype, right?
No.
$ cat x.cc
int f() const;
int f() { return 3; }
$ gcc x.cc
x.cc:1: error: non-member function ???int f()??? cannot have cv-qualifier
You can define a const member function, but it can call rand() just
fine.
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
If you want to go somewhere, goto is the best way to get there.
Ken Thompson.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Shared modification inside lambdas
Andrew Hunter [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: All well and good, but it seems to me that if I'm embedding the DSl, shouldn't I be able to use the host language's facilities--for example, function abstractions and applications--directly? Indeed. Using binding in the host language to represent binding in the embedded language is called higher-order abstract syntax (HOAS). Well, I tried this, and it seems it works OK, like so: data Expr = Var String | Const Int | Plus Expr Expr | Quantified Range (Int - Expr) (Do you still need or even want Var String?) ... I could write something like: refine (Quantified range pred) = Quantified range pred' where pred' = \c - refine (pred c) But the problem is that this refines the term, again, every time I apply an argument to pred' ... The paper by Jacques Carette, Oleg Kiselyov, and me http://www.cs.rutgers.edu/~ccshan/tagless/jfp.pdf (revised version to appear in JFP) shows how to perform partial evaluation (which is an optimization, like your refinement) using HOAS. However, it's a bit tricky, in a language like Haskell (98) without so-called metaprogramming or staging facilities at the term level, to make the optimizations happen only once (rather than every time the embedded abstraction is invoked). It can be done! Let me point you to some code that we only mention in passing in that paper, which performs type-checking using HOAS. The type-checking happens only once; then the type-checked term can be interpreted many times. http://okmij.org/ftp/tagless-final/ http://okmij.org/ftp/tagless-final/IncopeTypecheck.hs Hope this helps. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 2008-11-25 Elimination of Violence Against Women http://unifem.org/vaw/ 1948-12-10 Universal Declaration of Human Rights http://everyhumanhasrights.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Monadic bind with associated types + PHOAS?
Ryan Ingram [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: I really like the syntax for do-notation. And I really like how great Haskell is as writing embedded languages, a lot of which comes from the programmable semicolon that monadic bind gives you. AFAICT, standard Haskell 98 already gives you the ability to express binding and sharing in PHOAS, except not using do-notation: class Symantics repr where lam :: (repr a - repr b) - repr (a - b) app :: repr (a - b) - repr a - repr b add :: repr Int - repr Int - repr Int int :: Int - repr Int let_ :: Symantics repr = repr a - (repr a - repr b) - repr b let_ e body = app (lam body) e testSharing :: Symantics repr = repr Int testSharing = let_ (add (int 3) (int 4)) (\x - add x x) Oleg has already noted that you can nicely express the showing, optimization (such as partial evaluation), and transformation (such as to CPS) of embedded code in this framework. I agree with him and you that this representation is a promising direction to explore. All that's missing in standard Haskell 98, then, is the ability to use do-notation: (=) = let_ testSharing = do x - add (int 3) (int 4) add x x But -XNoImplicitPrelude in GHC 6.10 is supposed to enable it, no? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 2008-11-20 Universal Children's Day http://unicef.org/ 1948-12-10 Universal Declaration of Human Rights http://everyhumanhasrights.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: streaming translation using monads
Warren Harris [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: However, the use of a universal type for the values would still seem to be required since there is no way to implement type-indexed values when the queries themselves are expressed as an abstract datatype rather than as functions. Am I overlooking something? You might find inspiration in the fact that printf and scanf can be expressed in ML/Haskell without any fancy type-system features. http://www.brics.dk/RS/98/12/ http://cs.nyu.edu/zheyang/papers/YangZ--ICFP98.html http://article.gmane.org/gmane.comp.lang.haskell.general/16409 http://www.itu.dk/people/mir/typesafepatterns.pdf Credits to: Olivier Danvy, Zhe Yang, Kenichi Asai, Oleg Kiselyov, Morten Rhiger. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 2008-11-20 Universal Children's Day http://unicef.org/ 1948-12-10 Universal Declaration of Human Rights http://everyhumanhasrights.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] How to get the binary respentation of?the Int/Double.
Ryan Ingram [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Actually, this is a good question, at least as relating to floating point values. Is there a primitive to view the machine representation of floats? Not a primitive, but it can be defined: module Cast (cast) where import Foreign.Storable (Storable, sizeOf, peek) import Foreign.Marshal.Utils (with) import System.IO.Unsafe (unsafePerformIO) import Foreign.Ptr (castPtr) cast :: (Storable a, Storable b) = a - b cast a = b where b | sizeOf a == sizeOf b = unsafePerformIO $ with a $ peek . castPtr -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Don't mess with me lady; I've been drinking with skeletons. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: universal algebra support in Haskell?
Galchin, Vasili [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Do you have any examples of say instance Lattice? http://web.cecs.pdx.edu/~mpj/pubs/lattices.html http://web.cecs.pdx.edu/~mpj/pubs/springschool.html -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig You can take the boy out of Harvard, but you can't take the boy's signature... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell in Artificial Intelligence
Christos Chryssochoidis [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: I'm interested in doing a survey about the use of Haskell in the field of Artificial Intelligence. I searched in Google, and found in the HaskellWiki, at www.haskell.org/haskellwiki/Haskell_in_industry, two organizations that use Haskell and do work related to AI. Besides that, I haven't found much else. Could somebody from the Haskell community give me some pointer to a project or system related to AI that uses Haskell? I started using Haskell in my graduate introductory AI course. The basic advantage is that of embedding domain-specific languages in Haskell (well documented in, for example, Composing Contracts and Playing the DSL Card). In this case, the embedded language is that of probability distributions and decision processes. The Haskell implementation can simulate a decision process as well as find a best response strategy. Unfortunately, the documentation is sparse outside my class lectures, but you can find the code with comments at http://conway.rutgers.edu/~ccshan/wiki/cs530/ (search for Process.lhs). -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Human cognition is not equipped to update the list of players in our complex social rosters by accommodating a particular person's sudden inexistence. -- Jesse Bering, Never Say Die: Why We Can't Imagine Death. Scientific American Mind - October 22, 2008 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A problem with nested regions and higher-order?functions
Mario Bla??evi?? [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in
gmane.comp.lang.haskell.cafe:
I'm trying to apply the nested regions (as in Lightweight Monadic
Regions by Oleg Kiselyov and Chung-chieh Shan) design pattern, if
that's the proper term, in hope to gain a bit more type safety in
this little library I'm working on (Streaming Component Combinators,
available on Hackage). I guess the problem is that I'm getting too
much type safety now, because I can't get the thing to compile. ...
Hi! Thanks for your interest. It sounds like a promising application
of region checking. I actually side with the type checker on this
problem:
type SingleHandler x y = forall r1s rs. Ancestor r1s rs =
Handle r1s x - Region rs y
type DoubleHandler x y z = forall r1d r2d rd. (Ancestor r1d rd, Ancestor
r2d rd) =
Handle r1d x - Handle r2d y - Region rd z
Here a SingleHandler is defined as an operation, in an arbitrary region
on an arbitrary handle, that is valid as long as the region of the
operation descends from the region of the handle. For example, reading
a string from an arbitrary open file is a SingleHandler File String.
However, copying a string from an arbitrary open file to another fixed
file is not a SingleHandler, because such an operation is valid only
in a region that descends from the destination file handle's region!
That's what GHC complained about as it checks your mapD:
mapD :: (SingleHandler x z - SingleHandler y z)
- DoubleHandler x w z - DoubleHandler y w z
mapD f d = \y w- f (\x- d x w) y
So we really need to change the type of mapD if we want it to be
accepted by a sound type system. The simplest way is to not require
that mapD return a DoubleHandler (a binary operation that works in an
arbitrary region):
mapD :: ((Handle r1 x - Region r z) -
(Handle r1 x - Region r z))
- ((Handle r1 x - Handle r2 w - Region r z) -
(Handle r1 x - Handle r2 w - Region r z))
mapD f d = \y w- f (\x- d x w) y
This type is a special case of the type automatically inferred for mapD
by Haskell if you omit the type signature. Haskell doesn't have any
trouble type-checking higher-order functions, such as this mapD, but
higher-rank types can call for manual annotations, as illustrated below.
Another way to get mapD to type-check is to pass it (as its first
argument) not a SingleHandler transformer but a transformer of
operations that may work only in descendents of a given region r2. We
want to write
type H r2 x y = forall r1 r. (Ancestor r1 r, Ancestor r2 r) =
Handle r1 x - Region r y
mapD :: (forall r2. H r2 x z - H r2 y z)
- DoubleHandler x w z - DoubleHandler y w z
mapD f d = \y w- f (\x- d x w) y
(forall r2 takes scope over both H r2 x z and H r2 y z above) but
GHC doesn't see that we intend to unify the r2d in the expansion of
DoubleHandler y w z with the r2 in this type signature of mapD.
So, we need to put an explicit type annotation on the use of f in the
body of mapD. To do so, we add {-# LANGUAGE ScopedTypeVariables #-}
and expand the type synonym DoubleHandler y w z in the type signature
of mapD:
mapD :: forall x y z w r1d r2d rd. (Ancestor r1d rd, Ancestor r2d rd) =
(forall r2. H r2 x z - H r2 y z)
- DoubleHandler x w z
- Handle r1d y - Handle r2d w - Region rd z
mapD f d = \y w- (f :: H r2d x z - H r2d y z) (\x- d x w) y
Not so pretty anymore, but it does pass the type checker (GHC 6.8.2).
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
-
Ken Shan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: type classes
class RingTy a b where
order :: a - Integer
units :: a - [b]
class VectorSpaceTy a b | a - b where
dimension :: a - Integer
basis :: (Field c) = a - [b c]
where `b' is a vector space over the field `c'.
It looks like you are using the first (of two) type arguments to the
RingTy and VectorSpaceTy type classes as abstract types; in other words,
operations on rings and vector spaces don't really care what the type
a is in RingTy a b and VectorSpaceTy a b. Is that true?
Assuming so, if I may strip away the (extremely sweet) syntactic sugar
afforded by type classes for a moment, what you seem to be doing is to
pass dictionaries of types
data RingTy a b = RingTy {
order :: a - Integer,
units :: a - [b] }
data VectorSpaceTy a b = VectorSpaceTy {
dimension :: a - Integer,
basis :: forall c. (Field c) = a - [b c] }
to operations on rings and vector spaces. Because the type a is
abstract, you may as well pass dictionaries of types
data RingTy b = RingTy {
order :: Integer,
units :: [b] }
data VectorSpaceTy b = VectorSpaceTy {
dimension :: Integer,
basis :: forall c. (Field c) = [b c] }
to these operations. The information that you want computed just
once per ring or per vector space can be defined as lexically scoped
variables where you create these dictionaries in the first place.
To add back the syntactic sugar (i.e., to make the dictionary arguments
implicit) and to make the type system check that elements of different
vector spaces are not confused, you may find Dylan Thurston's technique
useful: http://www.cs.rutgers.edu/~ccshan/prepose/prepose.pdf
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
2008-07-04 Independence from America! http://caab.org.uk/
2008-07-05 International Co-operative Day http://ica.coop/
http://www.guardian.co.uk/politics/2008/jul/02/labour.tradeunions
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A Monad for on-demand file generation?
Joachim Breitner [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Am Montag, den 30.06.2008, 07:08 -0500 schrieb Derek Elkins: You may want to look at Magnus Carlsson's Monads for Incremental Computing http://citeseer.comp.nus.edu.sg/619122.html not exactly what I need, but very interesting read. Maybe I can use some of the ideas. You might also find relevant the work on adaptive computation by Umut Acar and collaborators. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 2008-07-04 Independence from America! http://caab.org.uk/ 2008-07-05 International Co-operative Day http://ica.coop/ http://www.guardian.co.uk/politics/2008/jul/02/labour.tradeunions ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Monad for HOAS?
Conal Elliott [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: I share your perspective, Edsko. If foo and (Let foo id) are indistinguishable to clients of your module and are equal with respect to your intended semantics of Exp, then I'd say at least this one monad law holds. - Conal I am at least sympathetic to this perspective, but the Expr constructors are not as polymorphic as the monad operations: if in do a - foo return a foo has type ExprM String (perhaps foo is equal to return []), then we want to generate the DSL expression Let [] id, but [] is not of type Expr. Because whenever foo's type is not ExprM Expr the above code using do notation must be exactly equal to foo, by parametricity even when foo's type is ExprM Expr we cannot generate Let. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig The pomotarians have nothing to lose but their value chains. Call the Thermodynamics Police! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: GADT rhymes with cat
[EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Quoting Jeremy Apthorp [EMAIL PROTECTED]: Clearly, this pronounciation is gay dee tea. I always new those types were a bit queer. Not that there's anything wrong with that. ... If it type-checks, it must be correct! I thought the t was silent as well, an unaspirated stop? Egad! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Is mathematics a syntax of language? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell w/ delimited continuations
Taral [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: On Sat, Feb 23, 2008 at 1:05 AM, [EMAIL PROTECTED] wrote: reset ((\x - x + x) (shift f f)) This one doesn't typecheck, since you can't unify the types (a - r) and r. Some type systems for delimited continuations, such as Danvy and Filinski's (http://www.daimi.au.dk/~danvy/Papers/fatc.ps.gz; DIKU TR 89/12), allows changing the answer type and admits this code. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig God exists since mathematics is consistent, and the devil exists since its consistency cannot be proved. -- Hermann Weyl. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Designing DSL with explicit sharing [was: I love?purity, but it's killing me]
Matthew Naylor [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in
gmane.comp.lang.haskell.cafe:
sklansky f [] = []
sklansky f [x] = [x]
sklansky f xs = left' ++ [ f (last left') r | r - right' ]
where
(left, right) = splitAt (length xs `div` 2) xs
left' = sklansky f left
right' = sklansky f right
...
To write sklansky using your approach, it seems (to me) that the DSL's
expression type needs to be extended to support lists.
It's actually enough for the -metalanguage- to support lists. You may
not be surprised that the key is to program using continuations (again,
functions just at the metalanguage level, not the object-language
level): sklansky should have the (metalanguage) type
Exp repr = (repr a - repr a - repr a)
- [repr a] - ([repr a] - repr b) - repr b
but it would be more convenient to use the continuation monad (from
Control.Monad.Cont) and regard the creation of a name in the object
language as a side effect in the metalanguage.
import DSLSharing (Exp(..), unS)
import Control.Monad.Cont (Cont(Cont), runCont)
sklansky :: Exp repr = (repr a - repr a - repr a)
- [repr a] - Cont (repr b) [repr a]
sklansky f [] = return []
sklansky f [x] = return [x]
sklansky f xs = do
let (left, right) = splitAt (length xs `div` 2) xs
left' - sklansky f left
right' - sklansky f right
fmap (left' ++) (mapM (Cont . let_ . f (last left')) right')
Here's a quick test (I added some whitespace):
*Sklansky flip unS 0
$ flip runCont id
$ fmap (foldl sub (constant 0))
$ sklansky add
$ map (variable.('x':).show) [0..9]
let v0 = x0 + x1 in
let v1 = x3 + x4 in
let v2 = x2 + x3 in
let v3 = x2 + v1 in
let v4 = v0 + x2 in
let v5 = v0 + v2 in
let v6 = v0 + v3 in
let v7 = x5 + x6 in
let v8 = x8 + x9 in
let v9 = x7 + x8 in
let v10 = x7 + v8 in
let v11 = v7 + x7 in
let v12 = v7 + v9 in
let v13 = v7 + v10 in
let v14 = v6 + x5 in
let v15 = v6 + v7 in
let v16 = v6 + v11 in
let v17 = v6 + v12 in
let v18 = v6 + v13 in
0 - x0 - v0 - v4 - v5 - v6 - v14 - v15 - v16 - v17 - v18
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
I am a signature virus. Put me in your signature.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: I love purity, but it's killing me.
Henning Thielemann [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: It seems to become a FAQ. I think all DSLs suffer from the same problems: sharing and recursion. I've used wrappers for CSound, SuperCollider, MetaPost, they all have these problems. What do you mean by the recursion problem? Sometimes (or perhaps even often), sharing in an EDSL can be expressed in two ways. First, to reuse a -value- in the embedded language, you could introduce a let construct in the embedded language. let_ expr body = body expr Second, to reuse an -expression- in the embedded language, if your interpreter is compositional (here by interpreter I include a compiler, and by compositional I mean a fold), then you can represent an embedded expression simply as its interpretation. add x y = x + y let expr = add x y in add expr expr Jacques Carette, Oleg Kiselyov, and I have been exploring this final representation. http://okmij.org/ftp/Computation/tagless-typed.html -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig I am a signature virus. Put me in your signature. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: anybody can tell me the pronuncation of?haskell?
[EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Arigato gozaimasu. Jerzy Karczmarczuk. PS. If you think that arigato is a genuine Japanese word, well, check how the appropriately translated word is spelled in Portuguese... I'm not sure what you mean by genuine, but I suspect that whether arigato is genuine does not depend on Portuguese. http://linguistlist.org/issues/12/12-1871.html http://linguistlist.org/issues/12/12-1906.html -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig It is intensely annoying to an old Lisp hacker to see Java succeeding despite being worse at just about everything Lisp was ever criticised for. Richard A. O'Keefe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Hamming's Problem
Calvin Smith [EMAIL PROTECTED] wrote: The author of Pugs (Perl6 implemented in Haskell) gives a nice solution to the problem of generating the Hamming numbers in the following interview: http://www.perl.com/pub/a/2005/09/08/autrijus-tang.html?page=last Dougal Stanton [EMAIL PROTECTED] wrote: There is an implementation on the wikipedia article for Haskell: Note that Dijkstra's two exercises are not the same as Hamming's original problem. I recommend the exercises! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig One thing that UNIX does not need is more features. It is successful in part because it has a small number of good ideas that work well together. Merely adding features does not make it easier for users to do things -- it just makes the manual thicker. -- Rob Pike, Brian W. Kernighan, 1983. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: re: generics and grammars
Greg Meredith [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Thanks for the references! Have two-level types been applied to parser generation? Hrm, I'm not sure what kind of application you have in mind, so I suppose the answer is that I'm not aware of any application. (: I suppose that the parser for the type-level fixpoint of a type constructor is the term-level fixpoint of a parser constructor. Unfortunately data Fix f = Fix (f (Fix f)) deriving Read doesn't work in Haskell, because there's no way to express the constraint that the type f a is an instance of Read whenever the type a is. However, see Valery Trifonov. 2003. Simulating quantified class constraints. In Haskell workshop, 98-102. http://flint.cs.yale.edu/trifonov/papers/sqcc.pdf http://flint.cs.yale.edu/trifonov/papers/sqcc.ps.gz This discussion also reminds me of Ralf Hinze. 2000. A new approach to generic functional programming. In POPL, 119-132. http://www.informatik.uni-bonn.de/~ralf/publications.html Cheers, Ken -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Nevertheless, most cosmologists, including Dr. Guth and Dr. Linde, agree that the universe ultimately must come from somewhere, and that nothing is the leading candidate. Dennis Overbye, New York Times, May 22, 2001. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: grammars and generics
Greg Meredith [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Here is an idea so obvious that someone else must have already thought of it and worked it all out. Consider the following grammar. Hello! If I understand your basic idea correctly, it is to split a recursive data type into two parts, a non-recursive type constructor and a knot-tying recursive type. This idea has been christened two-level types by Tim Sheard and Emir Pasalic. 2004. Two-level types and parameterized modules. Journal of Functional Programming 14(5):547-587. The idea dates earlier, to initial-algebra semantics and functional programming with bananas and lenses: Mark P. Jones. 1995. Functional programming with overloading and higher-order polymorphism. In Advanced functional programming: 1st international spring school on advanced functional programming techniques, ed. Johan Jeuring and Erik Meijer, 97-136. Lecture Notes in Computer Science 925. http://web.cecs.pdx.edu/~mpj/pubs/springschool.html Erik Meijer, Maarten Fokkinga, and Ross Paterson. 1991. Functional programming with bananas, lenses, envelopes and barbed wire. In Functional programming languages and computer architecture: 5th conference, ed. John Hughes, 124-144. Lecture Notes in Computer Science 523. http://research.microsoft.com/~emeijer/Papers/fpca91.pdf Cheers, Ken -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Nevertheless, most cosmologists, including Dr. Guth and Dr. Linde, agree that the universe ultimately must come from somewhere, and that nothing is the leading candidate. Dennis Overbye, New York Times, May 22, 2001. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Whither memo and hash-consing?
Hello, What is the current status of the Memo module, for memoizing functions? It seems to have disappeared from the standard Hugs/GHC distributions; are we supposed to just find the old code on Google which uses System.Mem.Weak? A related question is whether anyone has built a library for hash-consing. Ideally it's just a function hashCons with a type like (Ord a) = a - a. Thank you. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig The old name for the Giraffe was Cameleopard, literally a Camel-Leopard. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: On the verge of ... giving up!
[EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: That's not my experience. I didn't really understand Kalman filters until I read the Wikipedia page. It's better than most of the tutorials out there. While we're off topic, here's a nice introduction to Kalman filters: http://www.cs.unc.edu/~welch/kalman/maybeck.html -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Inspired by http://www.xkcd.com/327/, I am considering changing my name to Chung-chieh ');DROP TABLE EMPLOYEES;-- Shan to see if anything breaks ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Fast Paced Haskell Tutorial
Paulo J. Matos [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: I'm interested in a freely available fast paced haskell tutorial. By fast paced, I means I want something that goes through basic in a very fast pace, presents a couple of examples and then talks about more advanced features. A set of tutorials would be also good. References to these kind of tutorials would be great. You might like http://www.haskell.org/tutorial/ -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig If monads encapsulate effects and lists form a monad, do lists correspond to some effect? Indeed they do, and the effect they correspond to is choice. Wadler 1995, Monads for fn'l programming ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Typeclasses and implicit parameters
[EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: That higher-rank type makes all the difference. Yes. You can even do this portably, using nothing unsafe, with Dylan Thurston's technique: Oleg Kiselyov and Chung-chieh Shan. 2004. Functional pearl: Implicit configurations -- or, type classes reflect the value of types. In Proceedings of the 2004 Haskell workshop, 33-44. New York: ACM Press. http://www.cs.rutgers.edu/~ccshan/prepose/ -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig We're not teaching Scheme. I spend about an hour teaching Scheme, and for the rest of the semester I /use/ Scheme to teach /computer science/. Brian Harvey (UC Berkeley) on comp.lang.scheme. Aug 22, 2007. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: zip3, zip4 ... - zipn?
Frank Buss [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Is it possible to write a function like this: zipn n list_1 list_2 list_3 ... list_n which implements zip3 for n=3, zip4 for n=4 etc.? Looks like variable number of arguments are possible, like printf shows, so a general zipn should be possible, too. If it is possible, why there are functions like zip5 and not just zipn? Check out: Fridlender, Daniel, and Mia Indrika. 2000. Do we need dependent types? Journal of Functional Programming 10(4):409-415. http://www.math.chalmers.se/~indrika/jfp.ps.gz McBride, Conor. 2002. Faking it: Simulating dependent types in Haskell. Journal of Functional Programming 12(4-5): 375-392. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Remember Hirosima 1945-08-06, Nagasaki 1945-08-09. http://petitions.pm.gov.uk/Free-Vanunu/ http://www.vanunu.org/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Zippers, Random Numbers Terrain
Thomas Conway [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: On 8/2/07, apfelmus [EMAIL PROTECTED] wrote: That concludes the infinite terrain generation for one dimension. For higher dimension, one just needs to use 2D objects instead of intervals to split into two or more pieces. For instance, one can divide equilateral triangles into 4 smaller ones. In fact, it doesn't matter whether the starting triangle is equilateral or not when using the midpoints of the three sides to split it into four smaller triangles. Nice. Nice indeed! The infinite binary tree of the terrain intervals reminds me of the hyperbolic plane, of course, and its use in arbitrary-precision real arithmetic (cue a real mathematician). The issue of the RNG running backwards was what made me realize that rather than using StdGen in the nodes, if you simply number them (Hmmm - the nodes are countably infinite :-)), you can then [e.g.] use a cryptographic hash or similar to turn them into random numbers. You can seed the hash to generate different terrains. Isn't the whole point of a good RNG that running it forwards and backwards should be statistically the same? You may be interested that in some of the code I wrote for the right angle isosceles triangle case, I got into precision problems. [...] After pondering on this for a while, I realized instead of representing the scale of the triangle as a Double, I could use (Either Double Double), with Left x representing the scale x, and Right x representing the scale x * sqrt 2 / 2. That way, all the rounding problems can be made to go away. Well, not all of them - after all Double has limited digits of mantissa, but down to quite small scales, the arithmetic will be precise. Actually, you could use (Either Rational Rational), except that performance would be [even more] atrocious. What about a possibly infinite list of binary digits in base sqrt(2)? Surely the beauty would overshadow any performance problems. (: -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Elegance is optional. -- Richard A. O'Keefe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: advantages of using fix to define rcursive functions
Harald ROTTER [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: I read about the usage of fix to define recursive functions. Although I think that I understood how to use fix, I still wonder what the advantages of fix are (as compared to the conventional approach to define recursive functions). You might enjoy this paper: Bruce J. McAdam, 1997. That about wraps it up: Using FIX to handle errors without exceptions, and other programming tricks. Tech. Rep. ECS-LFCS-97-375, Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh. http://www.lfcs.informatics.ed.ac.uk/reports/97/ECS-LFCS-97-375/ -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig It is the first responsibility of every citizen to question authority. Benjamin Franklin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: xkcd #287 NP-Complete
Tom Pledger [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: We've seen some nice concise solutions that can deal with the original problem: solve 1505 [215, 275, 335, 355, 420, 580] I'll be a nuisance and bring up this case: solve 150005 [2, 4, 150001] Here's my solution to the xkcd problem (yay infinite lists): xkcd_c287' = foldr (\cost without - let (poor, rich) = splitAt cost without with = poor ++ zipWith (++) rich (map (map (cost:)) with) in with) ([[]] : repeat []) [215, 275, 335, 355, 420, 580] -- [2, 4, 150001] !! 1505 -- 150005 Replacing the two lines with comments by the comments solves your case quickly. Thanks! That was fun! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig http://www.unaids.org/en/HIV_data/epi2006/ UNAIDS/WHO AIDS Epidemic Update: December 2006 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Newbie question about tuples
peterv [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: I don't think Haskell has something like a fixed-length array or constant expressions that *must* be resolved at compile-time (like the N in the C++ template)? Or like Digital Mars D's static if statement (which is a control-flow statement that *must* succeed at compile time)? Actually, Haskell can do it one better: you can have fixed-length arrays whose length is known only at run time. That is, you can have the compiler check that you will only be adding arrays with the same length, but find out what that length is (and pass it around non-redundantly) at run time. (You can encode the same idea, more verbosely, using generics in Java and C#.) Please see (among other work): http://ofb.net/~frederik/vectro/ http://www.cs.rutgers.edu/~ccshan/prepose/ http://www.eecs.usma.edu/webs/people/okasaki/icfp99.ps -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig http://www.unaids.org/en/HIV_data/epi2006/ UNAIDS/WHO AIDS Epidemic Update: December 2006 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Lightweight sequent calculus and linear abstractions
[EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Conor McBride has posed an interesting problem: implement constructors P v for embedding pure values v Ofor holes f :$ a for application, left-associative and an interpreting function emmental such that emmental (P (+) :$ (P (*) :$ O :$ P 10) :$ O) 4 2 = 42 Hrm! I don't see the original message where the problem was posed, but it is indeed interesting. Here is my solution, but I don't need P, O, and :$ to be constructors, so I rename them to p, o, and $:, respectively: emmental m = m id p x k = k x o k = k (m $: n) k = m (\f - n (\x - k (f x))) infixl 0 $: test = emmental (p (+) $: (p (*) $: o $: p 10) $: o) 4 2 -- 42 All credit is due to Danvy and Filinski (DIKU TR 89/12, Section 3.4; later Danvy's functional unparsing paper, JFP 8(6)). One way to understand this code is that o is like the word what in a language like Mandarin (shenme) or Japanese (dare) that does not move any wh-word to the boundary of a clause. In Japanese, emmental would correspond to the -ka that marks the scope of a question and awaits an answer (in this case the numbers 4 and 2). Or, we have control inversion: the argument to emmental is a sandboxed user process that occasionally requests input. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Gordon Brown's special advisors: www.christianaid.org.uk/stoppoverty/climatechange/stories/special_advisers.aspx ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Mathematica
Andrew Coppin [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: The absurdly efficient number crunching is obviously not implementable in Haskell - or indeed virtually any language except assembly. [...] The pretty user interface is obviously not implementable in Haskell. [...] It seems it would be a fairly difficult task to implement the pattern matching engine properly. Why? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 2007-05-15 International Conscientious Objection Day http://wri-irg.org/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: flip fix and iterate
Bryan Burgers [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: On the topic of 'fix', is there any good tutorial for fix? I searched google, but mostly came up with pages including things like 'bug fix'. It's hard for me to get an intuition about it when 'fix' always stack overflows on me because I don't really know how to use it. Perhaps try: Bruce J. McAdam. 1997. That about wraps it up: Using FIX to handle errors without exceptions, and other programming tricks. Tech. Rep. ECS-LFCS-97-375, Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh. http://www.lfcs.informatics.ed.ac.uk/reports/97/ECS-LFCS-97-375/ -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig This is a fairly straightforward coding problem: There aren't many really interesting ways to screw up. -- Leslie Lamport ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A different Maybe maybe
Joachim Breitner [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: [Also on http://www.joachim-breitner.de/blog/archives/229-A-different-Maybe-maybe.html] This is known as the Church encoding of algebraic data types. In this generality, it seems to be first described by Corrado Böhm and Alessandro Berarducci (1985) in Automatic synthesis of typed L-programs on term algebras, Theoretical Computer Science 39:135-154. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Web 2.0 is a commemorative coin minted in celebration of the end of the dot-com crash. Like all commemorative coins, it has no actual value. -- Michael Swaine, Dr.Dobb's J., March 2006 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: How did you stumble on Haskell?
Bob Davison [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: This leads me off thread to ask if anyone could recommend reading for someone who has done mathematics to college level, but nearly 30 years ago when many English schools didn't cover 20th century mathematics. I thought calculus was about differentiation and integration and was very surprised to discover that there were such things as 'predicate calculus', 'propositional calculus', and various flavours of 'lambda calculus'. I also have little or no idea of set theory, group theory, domain theory, combinatory logic, ... How about The Haskell Road to Logic, Maths and Programming by Kees Doets and Jan van Eijck (http://homepages.cwi.nl/~jve/HR/), reviewed by Ralf Lämmel (http://arxiv.org/abs/cs/0512096)? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Earth???s crammed with heaven, And every common bush afire with God; But only he who sees, takes off his shoes; The rest sit round it and pluck blackberries. ??? Elizabeth B. Browning ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Higher kinds (and impredicativity?)
Jim Apple [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: C, x : k1 |- y : * --- C |- (\forall x : k1 . y) : * I'd expect C, x : k1 |- y : k2 --- C |- (\forall x : k1 . y) : k2 Is there a foundational or an implementation reason for this restriction? I consider it a foundational reason. You seem to want (forall (f :: * - *) . f) to have kind * - *. But that means that I should be able to apply it to a type, say Int, to get a type (forall (f :: * - *) . f) Int. What values inhabit this type? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig My mother is a fish. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Higher kinds (and impredicativity?)
Jim Apple [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: (forall (f :: * - *) . f) Int. What values inhabit this type? The same ones that inhabit (forall (f :: * - *) . f Int); that is, none (or _|_). I don't see the uninhabitability of a type as reason why the type itself should be ill-formed, even in a domain without lifted types. I'm sorry I wasn't clear; I did not mean to argue that a type should be ill-formed just because it is not inhabited. Let me try to say something else. The kind system should be to types as the type system is to terms; in particular, if a type is well-kinded (i.e., well-formed) then it should either be a value type (such as [Int] and forall a. a) or contain a redex (such as (\a - a) Int). The proposed type above is neither; it is stuck just as the program 1 + \x-x is stuck. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: rebinding = for restricted monads
David Roundy [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: class WitnessMonad wm where (=) :: wm w w' a - (a - wm w' w'' b) - wm w w'' b () :: wm w w' a - wm w' w'' b - wm w w'' b return :: a - wm w w' a fail :: String - wm w w' a I suspect that you want w and w' to be the same type in the types of return and fail. Previous work: Atkey, Robert. 2006. Parameterised notions of computation. In MSFP 2006: Workshop on mathematically structured functional programming, ed. Conor McBride and Tarmo Uustalu. Electronic Workshops in Computing, British Computer Society. http://homepages.inf.ed.ac.uk/ratkey/param-notions.pdf http://haskell.org/pipermail/haskell-cafe/2004-July/006448.html -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig FORTH is a program that interfaces keyboards with computer. Charles H.Moore, Geoffrey C. Leach, 1970. http://www.ultratechnology.com/4th_1970.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: automonadization of code?
Adam Megacz [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Is there any work on automatic translation of code in some tiny imperative language into Haskell code that uses the ST and/or IO monads (or perhaps even pure functional code)? Is it possible to distinguish the automatic translation you have in mind from writing a monadic interpreter for an imperative language (which has been done since Moggi and Wadler)? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig FORTH is a program that interfaces keyboards with computer. Charles H.Moore, Geoffrey C. Leach, 1970. http://www.ultratechnology.com/4th_1970.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: what GUI library should i select?
Simon Peyton-Jones [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: I wonder whether it'd be possible to make the gtk2hs stuff emit warnings if you make calls from two different threads? Then an application would complain constructively rather than becoming unstable. ... or whether it's possible to represent the gtk2hs thread by a phantom type, to enforce the restriction statically? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Batman don't...but Kathmandu! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A type class puzzle
Yitzchak Gale [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in
gmane.comp.lang.haskell.cafe:
replace0 :: a - a - a
replace1 :: Int - a - [a] - [a]
replace2 :: Int - Int - a - [[a]] - [[a]]
This message is joint work with Oleg Kiselyov. All errors are mine.
Part of what makes this type-class puzzle difficult can be explained
by trying to write Prolog code to identify those types that the
general replace function can take. We use an auxiliary predicate
repl(X0,X,Y0,Y), which means that X0 is int - applied the same number
of times to X as Y0 is [] applied to Y.
repl(X, X, Y, Y).
repl((int - X0), X, [Y0], Y) :- repl(X0, X, Y0, Y).
We can now write a unary predicate replace1(X0) to test if any given
type X0 is a valid type for the replace function.
replace1(X0) :- repl(X0, (Y - Y0 - Y0), Y0, Y).
Positive and negative tests:
?- replace1(bool - bool - bool).
?- replace1(int - bool - [bool] - [bool]).
?- replace1(int - int - bool - [[bool]] - [[bool]]).
?- replace1(int - int - int - [[int]] - [[int]]).
?- \+ replace1(bool - [bool] - [bool]).
The optimist would expect to be able to turn these Prolog clauses
into Haskell type-class instances directly. Unfortunately, at least
one difference between Prolog and Haskell stands in the way: Haskell
overloading resolution does not backtrack, and the order of type-class
instances should not matter. Suppose that we switch the two repl
clauses and add a cut, as follows:
repl((int - X0), X, [Y0], Y) :- !, repl(X0, X, Y0, Y).
repl(X, X, Y, Y).
Now the second-to-last test above
?- replace1(int - int - int - [[int]] - [[int]]).
fails, because repl needs to look ahead beyond the current argument
type to know that the third int in the type is not an index but a list
element. This kind of ambiguity is analogous to a shift-reduce conflict
in parsing.
We could roll our own backtracking if we really wanted to, but let's
switch to the saner type family
replace0 :: a - a - a
replace1 :: Int - [a] - a - [a]
replace2 :: Int - Int - [[a]] - a - [[a]]
where the old list comes before the new element. The corresponding
Prolog predicate and tests now succeed, even with the switched and cut
repl clauses above.
replace2(X0) :- repl(X0, (Y0 - Y - Y0), Y0, Y).
?- replace2(bool - bool - bool).
?- replace2(int - [bool] - bool - [bool]).
?- replace2(int - int - [[bool]] - bool - [[bool]]).
?- replace2(int - int - [[int]] - int - [[int]]).
?- \+ replace2([bool] - bool - [bool]).
Regardless of this change, note that a numeric literal such as 2 in
Haskell can denote not just an Int but also a list, given a suitable Num
instance. Therefore, the open-world assumption of Haskell type classes
forces us to annotate our indices with ::Int in Haskell.
Below, then, are the tests that we strive to satisfy.
x1 = abc
x2 = [ab, cde, fghi, uvwxyz]
x3 = [[[i1 + i2 + i3 | i3 - [10..13]] | i2- [4..5]] | i1 - [(1::Int)..3]]
test1:: String
test1 = replace (1::Int) x1 'X'
{- expected error reported
test2:: [String]
test2 = replace (1::Int) x2 'X'
-}
test3:: [String]
test3 = replace (1::Int) x2 X
test4:: [String]
test4 = replace (2::Int) (1::Int) x2 'X'
test5:: [[[Int]]]
test5 = replace (2::Int) (0::Int) (1::Int) x3 (100::Int)
The remainder of this message shows two ways to pass these tests. Both
ways require allowing undecidable instances in GHC 6.6.
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
In the first way, the Replace type-class parses the desired type for
replace into a tuple of indices, in other words, a type-level list
of indices. An auxiliary type-class Replace' then reverses this list.
Finally, another auxiliary type-class Replace'' performs the actual
replacement.
class Replace'' n old new where
repl'' :: n - old - new - old
instance Replace'' () a a where
repl'' () old new = new
instance Replace'' n old new = Replace'' (n,Int) [old] new where
repl'' (i,i0) old new =
case splitAt i0 old of (h,[] ) - h
(h,th:tt) - h ++ repl'' i th new : tt
class Replace' n n' old new where
repl' :: n - n' - old - new - old
instance Replace'' n old new = Replace' n () old new where
repl' n () = repl'' n
instance Replace' (n1,n2) n3 old new = Replace' n1 (n2,n3) old new where
repl' n1 (n2,n3) = repl' (n1,n2) n3
class Replace n a b c where
repl :: n - a - b - c
instance Replace' () n [old] new = Replace n [old] new [old] where
repl = repl' ()
instance Replace (i,n) a b c = Replace n i a (b-c) where
repl i0 i = repl (i,i0)
replace n = repl () n
The second way, shown below, eliminates the intermediate tuple of
indices used above. This code doesn't require allowing undecidable
instances in Hugs, but it does use functional dependencies to coax
Haskell into applying the last Replace instance.
class Replace old
[Haskell-cafe] Re: darcs: the first haskell tool more popular than?Haskell itself?
Josh Hoyt [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: On 1/24/06, Jared Updike [EMAIL PROTECTED] wrote: What happened to Avoid success at all costs? http://research.microsoft.com/Users/simonpj/papers/haskell-retrospective/ I was unaware of that motto. It looks like we'd better do something to make darcs harder to use. Time for a coalgebra of patches? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Can't sleep, clown will eat me. --- Unlike you I get Windows shoved down my throat at work. Ooh, that's a pane in the neck. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Announcing Djinn, new version 2004-12-13
Lennart Augustsson [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.general: There is a new version of Djinn available, with two notable new features: Haskell data types can be defined and the found functions are sorted (heuristically) to present the best one first. Hello, I wonder why the only Church numerals Djinn found were 0 and 1? Djinn :set +m Djinn num ? (a - a) - (a - a) num :: (a - a) - a - a num x1 x2 = x1 x2 -- or num _ x2 = x2 Very cool, in any case. Ken -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Medicine makes people ill, mathematics makes them sad, and theology makes them sinful. -- Martin Luther (1483-1546) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ReaderT and concurrency
In http://www.eecs.harvard.edu/~ccshan/prepose/prepose.pdf Oleg and I survey the approaches that others have mentioned and propose a new technique that is particularly relevant in concurrent programs. Ken -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig If debugging is the process of removing bugs, then programming must be the process of putting them in. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Category theory monad ---- Haskell monad
Michael Vanier [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Basically, though, the Haskell implementation _is_ the category theoretic definition of monad, with bind/return used instead of (f)map/join/return as described below. Doesn't the Haskell implementation really correspond to the notion of a strong monad in category theory, once we take into account the fact that free variables can occur anywhere in the arguments to bind and return? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig 2005-09-08 International Literacy Day http://www.un.org/depts/dhl/literacy/ 2005-09-21 International Day of Peace http://www.internationaldayofpeace.org/ 2005-09-22 European Car-Free Day http://www.22september.org/ 2005-09-26 European Day of Languages http://www.ecml.at/edl/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Annotating calculations
Rene de Visser [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: I have a somewhat complicated calculation programmed in Haskell. This calculation is coded without using monads. I want to also produce a report describing the details of this calculation for each particular set of inputs. e.g. Number of hours worked = 100. Gross pay per hour = 50. Total gross = 100 * 50 = 500. etc. But about 20 times more complicated than the above. I suggest that you consider defining an instance of Num for the type of a calculation result annotated with details. A binary operator like + can then both perform the calculation and combine the annotations. You probably want an additional operation (outside the Num class) that adds a new annotation for the current intermediate result. This way, you may be able to reuse all or most of your calculation code for computing with and without keeping track of the report. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Mothers are the necessity of invention. --Bill Watterson ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: mathematical notation and functional programming
(Is Lemming the same person as Henning Thielemann?) On 2005-01-30T21:24:24+0100, Lemming wrote: Chung-chieh Shan wrote: Wait a minute -- would you also say that 1+x has no meaning at the first glance, because x is a variable whereas 1 is an integer, so some lifting is called for? For me 'x' is a place holder for a value. But you can only adds two *numbers* to get a number. It makes no sense to add a number to a placeholder. So it makes no sense to write 1+x, no? For the expression '1+x' I conclude by type inference that 'x' must be a variable for a scalar value, since '1' is, too. But the expression '1/O(n^2)' has the scalar value '1' on the left of '/' and a set of functions at the right side. Type inference fails, so my next try is to make the operands compatible in a somehow natural way. It seems to me that your classification of certain notations as wrong and others as right assumes a certain type inference system that allows adding a number to a placeholder but disallows dividing a function by a set of functions. Since mathematical notation invokes many implicit conversions, it's sometimes no longer unique or obvious what implicit conversion to use. Many users of O(n^2) seem to consider it as a placeholder for some expression, where the value of the expression is bounded by n^2. Lambda notation also involves much ambiguity and many implicit conversions. In particular, x can mean the identity function from integers to integers as well as the identity function from booleans to booleans, as well as a function that maps an integer-boolean pair to the integer of the pair, as well as a function that maps an integer-boolean pair to the boolean of the pair, and so on. Right; they are control operators in the sense that call/cc is a control operator. So they seem to be operators that work on expressions rather than values. In this respect they are similar to the lambda operator, aren't they? Yes. You use 'ask' twice in the second expression. Does this mean that there may be two different values for 'ask'? If this is the case your second interpretation differs from my second interpretation. No -- when I use ask I mean the one defined in Control.Monad.Reader. Church style, System F(-omega), alpha-conversion, lambda calculus, eta reduction, currying - Where can I find some introduction to them? What about Haskell Curry? What about Bourbaki? - I have heard they worked hard to find a unified notation. (I'm sure that other people would have better suggestions, but I rather like Benjamin Pierce's book Types and programming languages.) Ken -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig War crimes will be prosecuted. War criminals will be punished. And it will be no defense to say, I was just following orders.' George W. Bush, address to the nation, 2003-03-17 http://www.whitehouse.gov/news/releases/2003/03/20030317-7.html signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: mathematical notation and functional programming
Henning Thielemann [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in
gmane.comp.lang.haskell.cafe:
Over the past years I became more and more aware that common mathematical
notation is full of inaccuracies, abuses and stupidity. I wonder if
mathematical notation is subject of a mathematical branch and whether
there are papers about this topic, e.g. how one can improve common
mathematical notation with the knowledge of functional languages.
I would like to know too!
But I would hesitate with some of your examples, because they may simply
illustrate that mathematical notation is a language with side effects --
see the third and fifth examples below.
Things I'm unhappy about are for instance
f(x) \in L(\R)
where f \in L(\R) is meant
(I'm not sure what you are referring to here -- is there a specific L
that you have in mind?)
F(x) = \int f(x) \dif x
where x shouldn't be visible outside the integral
(Not to mention that F(x) is only determined up to a constant.)
O(n)
which should be O(\n - n) (a remark by Simon Thompson in
The Craft of Functional Programming)
I'm worried about this analysis, because would O(1) mean O(\n - 1), and
1/O(n^2) mean 1/O(\n - n^2)? And what about the equal sign in front of
most uses of big-O notation? I would rather analyze this notation as
O = shift k. exists g. g is an asymptotically bounded function
and k(g(n))
where shift is Danvy and Filinski's control operator (paired with
reset). This way, we can use (as people do)
reset(f(n) = 2^{-O(n)})
to mean that
exists g. g is an asymptotically bounded function
and f(n) = 2^{-g(n)*n}.
Note that the argument to g is not specified in the original notation,
and neither is the reset explicit. But the parentheses in O(n) is now
regarded as mere multiplication (making O-of-n a mispronunciation).
With some more trickery underlying the equal sign, one can state
meanings such that O(n) = O(n^2) is true but O(n^2) = O(n) is false.
a b c
which is a short-cut of a b \land b c
What do you think of [a,b,c] for lists?
f(.)
which means \x - f x or just f
I regard this as reset(f(shift k. k)). Besides, even Haskell has (3+).
All of these examples expose a common misunderstanding of functions, so I
assume that the pioneers of functional programming also must have worried
about common mathematical notation.
But AFAIK, nobody ever promised that the mathematical notation used to
talk about functions must denote functions themselves. To take another
example, even though programs are morphisms, we don't always program
in point-free style. And the English word nobody does not denote
anybody!
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
War crimes will be prosecuted. War criminals will be punished. And it
will be no defense to say, I was just following orders.'
George W. Bush, address to the nation, 2003-03-17
http://www.whitehouse.gov/news/releases/2003/03/20030317-7.html
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: mathematical notation and functional programming
On 2005-01-28T20:16:59+0100, Henning Thielemann wrote: On Fri, 28 Jan 2005, Chung-chieh Shan wrote: But I would hesitate with some of your examples, because they may simply illustrate that mathematical notation is a language with side effects -- see the third and fifth examples below. I can't imagine mathematics with side effects, because there is no order of execution. To clarify, I'm not saying that mathematics may have side effects, but that the language we use to talk about mathematics may have side effects, even control effects with delimited continuations. Shift and reset, and other delimited control operators such as control and prompt (which date earlier than shift and reset), are neat. Given that we are talking about language semantics, you may be interested in my paper at http://www.eecs.harvard.edu/~ccshan/cw2004/cw.pdf (which quickly introduces shift and reset). F(x) = \int f(x) \dif x where x shouldn't be visible outside the integral (Not to mention that F(x) is only determined up to a constant.) right, so \int needs a further parameter for the constant Or you can take integration to return a set of functions, and = as \in. That's not actually how I would ultimately analyze things, but it seems to be a start. People say, it is obvious what O(n^2) means. For me it is obvious that they probably want to pass a constant function in, because O takes a function as argument and because I know people often don't distinguish between constant functions and scalar values. Then O(n) = O(n^2) because O(n) and O(n^2) denote the set of constant functions. :-) I am interested in descriptive mathematical notation rather than prescriptive mathematical notation (these are just my terms), in the sense that I want to first ask people what they take certain existing pieces of mathematical notation to mean, then figure out formal rules that underlie these obvious interpretations. But what do you mean with 1/O(n^2) ? O(f) is defined as the set of functions bounded to the upper by f. So 1/O(f) has no meaning at the first glance. I could interpret it as lifting (1/) to (\f x - 1 / f x) (i.e. lifting from scalar reciprocal to the reciprocal of a function) and then as lifting from a reciprocal of a function to the reciprocal of each function of a set. Do you mean that? Wait a minute -- would you also say that 1+x has no meaning at the first glance, because x is a variable whereas 1 is an integer, so some lifting is called for? I never heard about shift and reset operators, but they don't seem to be operators in the sense of higher-order functions. Right; they are control operators in the sense that call/cc is a control operator. With some more trickery underlying the equal sign, one can state meanings such that O(n) = O(n^2) is true but O(n^2) = O(n) is false. Sticking to the set definition of O we would need no tricks at all: O(\n - n) \subset O(\n - n^2) and O(\n - n) /= O(\n - n^2) By trickery I meant taking = to not denote equality. So for me, taking = to denote the subset relation would count as a trick. f(.) which means \x - f x or just f I regard this as reset(f(shift k. k)). Besides, even Haskell has (3+). Hm, (3+) is partial application, a re-ordered notation of ((+) 3), which is only possible if the omitted value is needed only once. But I see people writing f(.) + f(.-t) and they don't tell, whether this means (\x - f x) + (\x - f (x-t)) or (\x - f x + f (x-t)) In this case for most mathematicians this doesn't matter because in the above case (+) is silently lifted to the addition of functions. Yes, so in my mind an environment monad is in effect (so to speak) here, and the difference between the two meanings you pointed out is the difference between liftM2 (+) (liftM f ask) (liftM f (liftM2 (-) ask (return t))) and (+) (liftM f ask) (liftM f (liftM2 (-) ask (return t))) (where import Monad and Control.Monad.Reader :). But AFAIK, nobody ever promised that the mathematical notation used to talk about functions must denote functions themselves. I found that using a notation respecting the functional idea allows very clear terms. So I used Haskell notation above to explain, what common mathematical terms may mean. But Haskell notation does -not- respect the functional idea. First there's the issue of variables: to respect the functional idea we must program in point-free style. Second there's the issue of types: to respect the (set-theoretic) functional idea we must abolish polymorphism and annotate our lambda abstractions in Church style. Surely we don't want the meaning of our mathematical formulas to depend on the semantics of System F(-omega)! Or, as I would prefer, we could design our notation to be both intuitive and formally tractable, without requiring that the concrete syntax of our language directly correspond to the semantics of mathematics or programming. The (simply-typed, pure) lambda
Re: [Haskell-cafe] Partially-applied type synonyms?
On 2004-08-31T09:55:10-0700, Lyle Kopnicky wrote: Sorry, I don't think I made myself clear. I'm not defining PI, it's the standard type binding operator, like lambda is the variable binding operator. Maybe I could write it as 'II' so it looks more like a capital pi. It's not a feature of Haskell, but part of type theory (dependent types). I was mixing and matching and making it look like Haskell. So instead of 'PI r - ContT r m', I could write 'flip ContT', except that 'flip' needs to work on a type level instead of a value level. Or I could write '(`ContT` m)', or 'ContT _ m', where the '_' is a hole. Does this make sense now? Yes, it makes sense now. You need to define newtype FlipContT m r a = FlipContT (ContT r m a) or more generally, newtype Flip c (m :: * - *) r a = Flip (c r m a) The rationale for disallowing matching partially-applied type synonyms is that higher-order unification is undecidable. See also: Neubauer, Matthias, and Peter Thiemann. 2002. Type classes with more higher-order polymorphism. In ICFP '02: Proceedings of the ACM international conference on functional programming. New York: ACM Press. http://www.informatik.uni-freiburg.de/~neubauer/papers/icfp02.pdf http://www.informatik.uni-freiburg.de/~neubauer/papers/icfp02.ps.gz -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Haskell: lazy, yet functional. http://haskell.org/ Aqsis: RenderMan for free. http://aqsis.com/ signature.asc Description: Digital signature ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partially-applied type synonyms?
On 2004-08-30T17:09:39-0700, Lyle Kopnicky wrote: Unfortunately, I need 'PI r - ContT r m', along with a and r, to be a member of the MonadPCont class (PI is the type binding operator). So I thought I'd define ContT' to take the arguments the other way around. Unfortunately, it can't be partially applied. What's your definition of PI? I suspect you simply need to define a newtype that wraps around 'PI r - ContT r m'. See also: Wadler, Philip L. 1994. Monads and composable continuations. Lisp and Symbolic Computation 7(1): 39-56. http://homepages.inf.ed.ac.uk/wadler/topics/monads.html#composable -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Green-Rainbow Party of Massachusetts http://www.green-rainbow.org/ Rich Zitola for Massachusetts State Senate (Worcester and Middlesex District) http://www.vote-zitola.org/ signature.asc Description: Digital signature ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] state in the continuation monad...
On 2004-07-02T16:15:15+0200, Ralf Laemmel wrote: I wonder whether perhaps a more basic step is to understand how type-changing monadic computations can be understood. By this I mean, that the effects model by the monad can change their type as part of the computation. Such a monad would be parameterised by effect types a b, where a is the type of the effect before computation and b is the type after computation. A monad on a category C is a monoid in the category of endofunctors on C. Dylan Thurston, who knows more category theory than I do, tells me that a monoid in a category D is a D-enriched category with a single object. Hence a monad on a category C is a single-object category enriched by the category of endofunctors on C. If we remove the single-object restriction, we arrive at a generalization of monads: a category enriched by the category of endofunctors on C. I call this an efect on C, where efect stands for endofunctor-enriched category. Intuitively, each object in an efect is a state, and each morphism a transition, in a directed graph. For example, a file may be open or closed, and can only be accessed while open. That'd be a two-state efect. John Power, who knows way more category theory than I do, tells me that an enriched category is much nicer (i.e., it actually helps to be an enriched category) when the enriching category is closed. I wonder how this statement plays out in the case of efects. The state monad is one example of a monad that can be generalized to an efect. The continuation monad can also be generalized to an efect; indeed, Danvy and Filinski did so in 1989 when they gave a type system for the delimited control operators shift and reset that allows the answer type to change during a computation (DIKU technical report 89/12; http://www.daimi.au.dk/~danvy/Papers/fatc.ps.gz). Just as the state monad can be implemented with the continuation monad, the state efect can be implemented with the continuation efect. I wonder whether Filinski's representation of monads in terms of shift and reset (POPL 1994, 1999; CMU dissertation 1996) generalizes to efects. That is, can any efect be implemented with the continuation efect? More pragmatically important perhaps, how can we make efects at least as easy to use and understand as monads by the practical programmer? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig It is dry and hot, but cloudy, in Phnom Penh, Cambodia Do Ken. Ken Do Ken Do. Do Ken Do Ken Do Ken Do. Ken. Do. Ken. The following ballot is for voting on a General Resolution to address the effect of the previous general resolution. - Debian Project Secretary signature.asc Description: Digital signature ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Is it possible to read existential types?
On 2004-04-28T15:12:03-0400, S. Alexander Jacobson wrote: Ok, but it sounds like you need to know the list of possible types in advance. Is it possible to have a lib take a filepath and type name as an arbitrary string, and read the instance in? I don't think you need to know the list of possible types in advance. Here is some (only slightly tested) code: import Data.Dynamic import Maybe import Monad lookupRead :: (Eq key, Read val, Typeable val) = key - [(key, (String, String))] - Maybe val lookupRead key list = ret where ret = case lookup key list of Just (typ, val) - if typ == show (typeOf (fromJust ret)) then case reads val of [(v,)] - Just v _- Nothing else Nothing _ - Nothing The question is how to get the result of lookupRead memoized, so that the call to reads happens at most once for each entry in the list. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig BBC News: Universities face week of protest http://news.bbc.co.uk/1/hi/education/3508209.stm pgp0.pgp Description: PGP signature ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Is it possible to read existential types?
On 2004-04-28T23:33:31-0400, S. Alexander Jacobson wrote: I don't think this works. I just tried it with: main = print $ lookupRead 1 [(1,(Integer,100))] This fails for the same reason print $ read 100 fails. You need to give a type signature to avoid type-class instance ambiguity: main = print $ (lookupRead 1 [(1,(Integer,100))] :: Maybe Integer) On GHCi 6.2.1, the above yields Just 100 for me. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Be it declared and enacted by this present Parliament / That the People of England / are / a Commonwealth and free State / without any King or House of Lords.-- An Act declaring England to be a Commonwealth 1649-05-19 | 355 years | 2004-05-19http://tinyurl.com/2dqnh signature.asc Description: Digital signature ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Is it possible to read existential types?
On 2004-04-29T11:50:48-0400, S. Alexander Jacobson wrote: But isn't the point of this code that you don't need that type signature? If I knew in advance that it was an Integer then I wouldn't need to passs Integer in the list. In the context in which the code was originally written, the point was not that you don't need that type signature. Your comment above helped me understand what you want, I think. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig BBC News: Universities face week of protest http://news.bbc.co.uk/1/hi/education/3508209.stm pgp0.pgp Description: PGP signature ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Is it possible to read existential types?
S. Alexander Jacobson [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: Is is possible to read/show an existentially typed list? Would it be possible if, instead of using read/show, I defined some variant that relies on the typeof/typeable infrastructure? Is there a way to read in a typename for use in coercing a read? Dylan Thurston and I encountered this problem a while ago. Show is easy: just use a type like exists a. Show a = Read is hard, because one needs to get the Read dictionary from somewhere, and the dynamic typing facility in Haskell does not include type-class constraint reduction at runtime. The best solution we came up with was to replace the existentially typed list with a list of string-string pairs, where the first string names the type and the second string names the value. The call to read is only done at lookup time, not at file-reading time. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Be it declared and enacted by this present Parliament / That the People of England / are / a Commonwealth and free State / without any King or House of Lords.-- An Act declaring England to be a Commonwealth 1649-05-19 | 355 years | 2004-05-19http://tinyurl.com/2dqnh ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
