Subject: Online judge and Haskell? - msg#00120

Previous Message by Date: click to view message preview

Re: Polymorphic stanamically balanced binary trees

oleg describes an implementation of AVL trees that have two main features: 1. The trees are heterogenous (elements within the same tree can have different types). 2. The balance condition is partially enforced by the type checker, and partially by run-time checks. For feature 1, you can take your favorite solution for heterogenous lists (existentials, type dynamic, ...) and extend it to trees. This problem is orthogonal to the balance problem, and I'll ignore it in the rest of this post. For feature 2, there are lots of interesting approaches to push this kind of check into the type checker. For example, Hongwei Xi has several variations that do this using dependent types. It can also be done entirely with nested types. I think I first saw this done for AVL trees by Ross Paterson in 1998. First, here's a type that for trees of height h, given types for trees of height h-1 (t1) and for trees of height h-2 (t2). data Node a t1 t2 = Left t1 a t2 | Even t1 a t1 | Right t2 a t1 Next, here's a type for trees of arbitrary height, given types for trees of height h-1 and h-2. data Tree a t1 t2 = Zero t2 | Succ (Tree a (Node a t1 t2) t1) To start things off, we set t2 to the type of trees of height 0 and t1 to the type of trees of height 1. type AVLTree a = Tree a a () For example, a tree like 1 / 2 would be encoded as Succ | Succ | Zero | Left(1) / \ Even(2) () / \ () () Using polymorphic recursion, you can then implement typical tree functions like insert and delete. The type checker will catch any attempt to build an unbalanced tree. Note that there are no run-time checks in this approach. That last statement is a little bit of a lie. There is no run-time typechecking going on, but there are run-time artifacts of this algorithm, namely the Zero and Succ nodes which encode the height of the tree. Zero and Succ are data constructors, not type constructors as they are in oleg's version, so you have to walk through them at run-time. -- Chris

Next Message by Date: click to view message preview

REMINDER - Contributions to HC&A Report (May 2003 edition)

Dear Haskeller, as you can see from the Report's topics page at http://www.haskell.org/communities/topics.html , both confirmations from well-known contributors and offers from new contributors are still a bit sparse at this stage (not to mention actual contributions:), although we're making progress. First, many thanks to those who simply write their reports and are done with it! But, if the call for contributions should have caught you in your extended Easter holidays, could you please let me know as soon as possible how long that will delay your contributions?-) I wouldn't want to extend the general target deadline by much, as people should really get going on their Haskell Workshop papers soon (hint!-), but we may be able to accomodate individual delays. Just keep in mind that this is really an informal exercise: it probably takes less time to sit down and write an update of your report than it takes to worry about delays and making time.. Otherwise, could everybody send in their individual reports ** by the end of THIS week ** ? Please?-) Thanks, Claus -- Haskell Communities and Activities Report (May 2003 edition) Contributions are due in by the end of THIS week! http://www.haskell.org/communities/ ======================= original call for contributions follows Dear Haskellers, following the early reminder in the preface of the last edition, you've probably been waiting already, contribution in hand, eager to send it in for the May edition of our report (hey, editors can have their dreams, too!-), so here it is: *your* invitation to contribute to the fourth edition of the Haskell Communities & Activities Report http://www.haskell.org/communities/ These bi-annual HC&A Reports should give a birds-eye view of Haskell development over the last 6 months, and perhaps an outlook over concrete plans for the next 6 months. The current plan is to get contributions in by the end of April, and to get the collective report out early next month (some of you will find this an excellent opportunity to collect your thoughts about what to submit to this year's Haskell Workshop, btw;-). The general idea is to update all existing summaries (these reports are really about recent/current activities), to drop any topics that haven't had any activity for two consecutive 6-month periods, and to add any new developments or topics for which no-one contributed summaries to the previous edition, while trying to keep the whole from blowing up (last time, we ended up with about 30 pages). New suggestions for current hot topics, activities, projects, .. are welcome - especially with names and addresses of potential contacts, but here is a non-exclusive list of likely topics: General Haskell developments; Haskell implementations; Haskell extensions; Standardization and documentation; Haskell tutorials, how-tos and wikis; Organisation of Haskell tool and library development; Haskell-related projects and publications; Feedback from specialist mailing lists to the Haskell community as a whole; Haskell libraries or tools; Applications of Haskell; Haskell announcements; .. all (recent) things Haskell Announcements: if you've announced anything new on the Haskell list over the last six months, you'll want to make sure that is reflected in this edition. Project pings: if you're maintaining a Haskell tool/library/.., you'll want to let everyone know that it is still alive and actively maintained, even if there may have been no new additions. Tutorials: if you've fought with some previously undocumented corner of Haskell, and have been kind enough to write down how you did manage to build that networking program, or if you've written a tutorial about some useful programming techniques/patterns, this is your opportunity to spread the word (btw, short, topic-specific, and hands-on tutorials that only show how to achieve a certain practical task would do a lot to make things easier for new Haskellers - Erlang and Perl folks seem to be good at this kind of thing, but why not have a similar effort for Haskell?) Applications: if you've been working quietly, using Haskell for some interesting project or application (commercial or otherwise), you might want to let others know about it, and about your experiences using the existing tools and libraries; are you using Haskell on your job? Feedback: if you're on one of the many specialist Haskell mailing lists, you'll want to report on whatever progress has been made there (GUI API discussions, library organisation, etc.) If you're unsure whether a contact for your area of work has come forward yet, have a look at the report's potential topics page, or get in touch with me. I've contacted last time's contributors, hoping they will volunteer to provide updates of their reports, and will update the contacts on the topics page fairly regularly. But where you don't yet see contacts listed for your own subject of interest, you are very welcome to volunteer, or to remind your local community/project team/mailing list/research group/etc. that they really ought to get their act together and let the Haskell community as a whole know about what they've been doing!-) A typical summary report about a tool/library/project/application/.. would be between 1 and 3 paragraphs of ASCII text (what's it about? major topics and results since the last report? current hot topics? major goals for the next six months?) plus pointers to material for further reading (typically to a home page, or to mailing list archives, specifications and drafts, implementations, meetings, minutes,..). Browsing through previous editions should give you a good idea. Looking forward to your contributions, Claus -- Haskell Communities and Activities Report (May 2003 edition) All contributions are due in by the end of April 2003! http://www.haskell.org/communities/ _______________________________________________ Haskell mailing list Haskell@xxxxxxxxxxx http://www.haskell.org/mailman/listinfo/haskell

Previous Message by Thread: click to view message preview

No more numeric-quest?

Dear Haskell Guys, None of the www.numeric-quest.com pages are available. Has anyone mirrored that stuff elsewhere? Thanks, Mike Fagan

Next Message by Thread: click to view message preview

Re: Online judge and Haskell?

On Mon, Apr 28, 2003 at 08:24:12PM +0200, Steffen Mazanek wrote: > Hello, Hello! > it's me again and I have a new mad idea. > There are a lot of programming contests out there > and unfortunately most (all?) of them do not allow > Haskell code till now! > I think, this is hard to accept. I agree wholeheartedly. > Why not ask the people which run > > acm.uva.es/problemset > > to provide their problem sets, input and output files > and the basic judging software and install it at > haskell.org? I think the best would be to convince them to allow Haskell solutions in http://acm.uva.es/problemset. I don't think that they will reveal input and output files - I surely would not. Having Haskell amongst languages supported by this site would have many advantages: a) you could compare Haskell programs to programs in other languages (but only in terms of efficiency, not programming techniques). b) you could use your existing account on this site (I have one) c) other contestants could get interested in learning Haskell > I think an adaption of this software to permit Haskell code can not be > that difficult! I think there would be some work in ensuring security. They don't run a complete virtual machine (like in VMware or Bochs) to guard against malicious programs. They simply don't allow to use some functions. One of possible judge responses is: * Restricted Function (RF): Your source program tried to use a not allowed function (such as fork(), fopen(), ...) One way of enforcing polite behaviour of Haskell programs could be to accept only modules with function solve :: String -> String which would be run with interact, and to disallow all functions which can break referential transparency, like unsafePerformIO. Or am I missing something? I have already tried to convince them to include some FP. Here is the response I got: > From marce@xxxxxxxxxxxxxxxxxx Fri Aug 9 22:39:11 2002 > From: "Carlos Marcelino Casas Cuadrado" <marce@xxxxxxxxxxxxxxxxxx> > To: "Tomasz Zielonka" <t.zielonka@xxxxxxxxxxxxxxxxxxx> > Subject: Re: How about supporting some functional language? > Date: Fri, 9 Aug 2002 22:24:31 +0200 > > Dear Tomasz Zielonka, > First of all thank you for your help, but we are not thinking about installing > another languaje on the judge. We still have some problems with Pascal, and we > haven't finished installing Java (it has a lot of security problems). We > prefer > make Pascal and Java work before installing another one. Maybe on the future > we'll consider installing OCaml or some other (a lot of people ask us about a > lot of them). > Thanks again. > Carlos. > PS: Anyway, the ACM contest only allows C(C++), Pascal and Java (well, they > used to). > > ----- Original Message ----- > From: "Tomasz Zielonka" <t.zielonka@xxxxxxxxxxxxxxxxxxx> > To: <acm@xxxxxx> > Sent: Wednesday, August 07, 2002 12:21 PM > Subject: How about supporting some functional language? > > > Hello! > > > > What is your opinion on adding some functional programming language to > > the list of languages supported by the judge? > > > > When I solve programming problems, I often start with a prototype in a > > FPL like Haskell, Clean, SML or OCaml. Sometimes this prototype, being > > prototype after all, is too slow or consumes to much memory. But often > > it is as efficient as a program I write later in C or C++. I would be > > very happy if I could just send this program and move on to other > > problems. > > > > I have good experience with using FPL in programming contest. There was > > an online programming contest in Poland, called Pogromcy Algorytmow > > (Algorithms Busters or Algorithms' Busters). In this year's edition one > > could use Pascal, C, C++ and OCaml to write the solutions. I used OCaml > > in 9 out of 13 problems and I don't regret that. > > > > I imagine that you wouldn't install all of the languages I mentioned, > > but probably one of them. > > If you are willing to consider my proposition, I can offer my help in > > choosing the language, its implementation and tayloring it for use in > > online programming contest. > > > > Best regards, > > Tom Who knows, maybe they would be willing to support Haskell now? Especially, if it would be just that easy to ensure security. > Ciao, > Steffen Best regards, Tom -- .signature: Too many levels of symbolic links