March 2007 - Haskell - Haskell.org

Announcing Djinn, version 2004-12-11, a coding wizard
by Lennart Augustsson 07 Apr '11

07 Apr '11

Howdy, y'all! I've written a small program that takes a (Haskell) type and gives you back a function of that type if one exists. It's kind of fun, so I thought I'd share it. It's probably best explained with a sample session. calvin% djinn Welcome to Djinn version 2005-12-11. Type :h to get help. # Djinn is interactive if not given any arguments. # Let's see if it can find the identity function. Djinn> f ? a->a f :: a -> a f x1 = x1 # Yes, that was easy. Let's try some tuple munging. Djinn> sel ? ((a,b),(c,d)) -> (b,c) sel :: ((a, b), (c, d)) -> (b, c) sel ((_, v5), (v6, _)) = (v5, v6) # We can ask for the impossible, but then we get what we # deserve. Djinn> cast ? a->b -- cast cannot be realized. # OK, let's be bold and try some functions that are tricky to write: # return, bind, and callCC in the continuation monad Djinn> type C a = (a -> r) -> r Djinn> returnC ? a -> C a returnC :: a -> C a returnC x1 x2 = x2 x1 Djinn> bindC ? C a -> (a -> C b) -> C b bindC :: C a -> (a -> C b) -> C b bindC x1 x2 x3 = x1 (\ c15 -> x2 c15 (\ c17 -> x3 c17)) Djinn> callCC ? ((a -> C b) -> C a) -> C a callCC :: ((a -> C b) -> C a) -> C a callCC x1 x2 = x1 (\ c15 _ -> x2 c15) (\ c11 -> x2 c11) # Well, poor Djinn has a sweaty brow after deducing the code # for callCC so we had better quit. Djinn> :q Bye. To play with Djinn do a darcs get http://darcs.augustsson.net/Darcs/Djinn or get http://darcs.augustsson.net/Darcs/Djinn/Djinn.tar.gz Then just type make. (You need a Haskell 98 implementation and some libraries.) And then start djinn. For the curious, Djinn uses a decision procedure for intuitionistic propositional calculus due to Roy Dyckhoff. It's a variation of Gentzen's LJ system. This means that (in theory) Djinn will always find a function if one exists, and if one doesn't exist Djinn will terminate telling you so. This is the very first version, so expect bugs. :) Share and enjoy. -- Lennart

8 13

Haskell-mode 2.0
by Stefan Monnier 02 Feb '09

02 Feb '09

I have recently taken over maintainership of Haskell-mode, and after making a bunch of changes, I figured it would be a good idea to make a new release. You can find this new release at: http://www-perso.iro.umontreal.ca/~monnier/elisp/ If you think it should also be found at http://www.haskell.org/haskell-mode/, then please tell John Peterson to get back to me (my email to him seem to go straight to the bitbucket. John?). This release has several changes that have all been only lightly tested, especially w.r.t compatibility with various Emacsen. See appended the NEWS file that describes some of the notewirthy changes. Stefan Changes since 1.45: * keybindings C-c <char> have been replaced by C-c C-<char> so as not to collide with minor modes. * The following modules are now automatically activated without having to add anything to haskell-mode-hook: haskell-font-lock (just turn on global-font-lock-mode). haskell-decl-scan (just bind `imenu' to some key). * In recent Emacsen, haskell-doc hooks into eldoc-mode. * haskell-hugs and haskell-ghci are superceded by inf-haskell. * Indentation rules have been improved when using layout inside parens/braces. * Symbols like -> and \ can be displayed as actual arrows and lambdas. See haskell-font-lock-symbols. * Tweaks to the font-lock settings. Among other things paren-matching with things like \(x,y) should work correctly now. * New maintainer <monnier(a)gnu.org>.

3 6

CfP: 2nd CEFP Functional Programming School, June 23-30, 2007
by HORVATH Zoltan 11 Jun '07

11 Jun '07

2nd Central-European Functional Programming School CEFP 2007 Cluj-Napoca, June 23-30, 2007 http://cs.ubbcluj.ro/cefp2007/ First Announcement - Call for participation - Call for PhD student presentation Aims and Scopes: The Central-European Functional Programming School (CEFP) is an intensive summer school series in the field of functional programming. The main goal is to bring together computer scientists, researchers, graduate and especially PhD students. The school would like to promote the research and the education of the functional programming languages, software technologies and programming methodologies. The second CEFP school will be organized by the Babeş-Bolyai University (Cluj-Napoca / Kolozsvár / Klausenburg) between 23-30 June, 2007. The previous school was held in Budapest, Hungary, July, 2005. The invited lecturers are prominent researchers in the field, and they will present state-of-the-art functional programming techniques. Beside the lectures practical courses will be held. The school includes a workshop for PhD students to present their work and get feed-back from the lecturers. Invited Lecturers: Rinus Plasmeijer (Radboud University Nijmegen, The Netherlands): iTasks: Defining Interactive Workflows for the Web Werner Kluge (Christian-Albrechts-Universität zu Kiel, Germany): Abstract Lambda Calculus Machines Marko van Eekelen (Radboud University Nijmegen, The Netherlands): Proving Properties of Lazy Functional Programs Tim Sheard (Portland State University, USA): The Omega Programming Language Ralf Hinze (Universität Bonn, Germany): Generics Three additional short courses will be given: Zoltán Horváth (Eötvös Loránd University, Budapest, Hungary): Refactoring Erlang Programs Zoltán Csörnyei (Eötvös Loránd University, Budapest, Hungary): Lambda-Calculus Horia F. Pop (Babeş-Bolyai University, Cluj-Napoca, Romania): A Tutorial on Object Orientedness in Functional Programming Submissions: PhD students are invited to submit the abstract of their presentations to be included in the workshop programme. Each presentation can be of max. 25 minutes. The full paper version can be submitted after the summer school. It is under negotiation to publish the revised lectures and the selected and reviewed papers in LNCS Volume. Venue: Cluj-Napoca / Kolozsvár / Klausenburg, formerly the capital of Transylvania, is one of the most beautiful medieval cities with a huge multicultural and historical inheritance. Surrounded by marvelous hills and mountains, the city provides fascinating environment for experiencing the unique ambience of a diversified culture, society and nature. Registration and costs: The registration fee (260 Euro) includes the course materials distributed during the school, the post-school volume, lunches, the excursion and the summer school banquet. For further information, accommodation possibilities and registration please visit the web-page of the event: http://www.cs.ubbcluj.ro/cefp2007. The deadline for registration and submissions is 1 June 2007.

1 2

Quicksearch vs. lazyness
by Steffen Mazanek 17 Apr '07

17 Apr '07

Hello, say, we want to find the k'th element in a sorted list. In imperative languages it is much more efficient to not use quicksort first and get the k'th element later, but to use a quicksearch algorithm that sorts only the relevant parts of the array. In Haskell one could implement this idea as follows: qsearch k [] = error ... qsearch k (x:xs) | lsmaller >= k = qsearch k smaller | lsmaller == 0 && k > 1 = qsearch (k-1) greater | lsmaller == 0 = x | otherwise = qsearch (k-lsmaller) (x:greater) where smaller = filter (<= x) xs lsmaller = length smaller greater = filter (> x) xs However, I was wondering whether it might be possible to implement quicksort in a way that quicksearch is done out of the box by lazy evaluation. Is there any way to do this? From my understanding for small k's lazy evaluation already does the trick for the naive quicksort algorithm (quicksort smaller ++ [x] ++ quicksort greater), doesn't it? Is there a search algorithm that makes better use of lazy evaluation out of the box? Best regards, Steffen

4 5

One-year INRIA post-doctoral position
by Frederic Blanqui 11 Apr '07

11 Apr '07

A one-year INRIA post-doctoral position is available: Title: Generation of construction functions guaranteeing algebraic invariants on concrete data types Aim: Although concrete data types are very useful in defining complex data structures, they are not always sufficient to adequately specify the data structures required by some algorithms. Often, only a subset of the concrete data type is in fact used since some invariants between the components are mandatory to ensure the correctness of the program. Now, many invariants can be described by using some equational theory. For instance, a sorted list is a particular representative of the equivalence class of lists modulo commutativity. The usual way to solve this problem is to use abstract data types or, better, private data types if one does not want to lose the ability of doing pattern matching. We propose to study the automatic generation of certified construction functions guaranteeing algebraic invariants on concrete data types, and develop an extension of OCaml with relational data types, that is, data types with invariants described by user defined equations. More information and online application on: http://www.talentsplace.com/syndication1/inria/frpostdoc/details.html?id=PG… Competences and profile: The position involves research and development in the area of functional programming, rewriting theory (in particular Knuth-Bendix completion) and, possibly, interactive theorem proving (experience with a proof assistant such as Coq is welcome). Speaking french is not necessary. Requirements: Candidates are required to hold a PhD degree between May 2006 and June 2007. Salary: the monthly gross salary is approx. EUR 2,150. Environment: - laboratory: LORIA (http://www.loria.fr/) - team: Protheo (http://protheo.loria.fr/) - project: Quotient (http://quotient.loria.fr/) - location: Nancy, in the East of France is at 1:30 from Paris by tren, 1:30 from Luxembourg airport by car, and 1:30 from Germany and Belgium. Application deadline: 1st July 2007. Contact: Frederic Blanqui (http://www.loria.fr/~blanqui/) More information about INRIA post-doctoral positions: http://www.inria.fr/travailler/opportunites/postdoc/postdoc.en.html

1 1

-compiler-options vs {#-LANGUAGE Flags-#}
by S. Alexander Jacobson 05 Apr '07

05 Apr '07

In theory, Haskell modules should contain all information necessary to interpret/compile them properly. In practice, many modules don't because their authors are flagging required language extensions in build systems rather than in module sources. This practice causes problems because then it becomes much hard to move modules between packages or to use a particular module outside of a particular build system context. I experience this problem when I use SearchPath to build HAppS applications. For example, $ sp runhaskell MyModule.hs will recursively download imported modules into a local directory and then run: $ runhaskell -i.haskell-cache MyModule.hs If all the imported modules contain all the right flags in their source then MyModule.main will just run (no need for manual recursion of through a cabal package depency tree!). If some of the imported modules do not include the correct flags, then an error message will result and I am then forced to do: $ sp runhaskell MyModule.hs -cpp -fglasgow-exts -etc And this is bad because (1) some of the modules may not want a particular extension turned on and (2) it is annoying to the user to have to guess at required extensions until they are all added on the command line. Problem (1) is probably small as evidenced by cabals use of global extensions without much complaint. Problem (2) is bigger. Most other modern languages e.g. Java, Python, Perl, Ruby, etc. don't rely on the compiler/interpreter command line options to designate language extensions. Neither should haskell. The correct answer, I believe, is to require that module authors put flags in the module themselves where they belong. At very least it should be considred bad style not to have them in your code and really what would make more sense is for compiler writers to disable command line flags that specify lanaguge-extensions. -Alex- PS Until this is resolved, though it is a hack, I will probably have searchpath automatically add all ghc language extension flags to the command line if the user is using ghc, runghc, or ghci i.e.: "-cpp -fth -fglasgow-exts -fallow-undecidable-instances -fallow-incoherent-instances -fallow-overlapping-instances" Another solution would be to have searchpath map files also carry cabal file URLs and get the flag from there, but some people still use makefiles or other randomness and I would like to make Searchpath work with java, perl,python, and ruby without much change.

7 8

ANNOUNCE: OmegaGB, Haskell Game Boy Emulator
by Bit Connor 04 Apr '07

04 Apr '07

OmegaGB is an emulator for the Nintendo Game Boy, written in pure haskell. It's in a very early state, and only barely shows the title screen of a few games. It uses gtk2hs for the user interface, but there is also a version that doesn't require gtk2hs and uses ascii art. The main problem I am having is getting decent performance. I have set up a darcs repository in the hopes of receiving advice or patches to improve performance. You can find more information about the program at the website: http://www.mutantlemon.com/omegagb/ The program works by maintaining a state of all of the gameboy hardware: cpu registers, memory, and internal timers for various interrupts and other things. A function is used to update the state: updateMachineDisplayFrame :: JoypadKeyStates -> ((RegisterStates, Memory), IrqStates) -> (Display, ((RegisterStates, Memory), IrqStates)) This approach does not give enough performance, and the emulator is not able to run in real time. I have experimented with replacing most of the state with mutable IORefs and an IOUArray for the memory. This gave approximately double the performance, but that is still only 10% of real time speed on my computer. And all this is still without emulating most of the GB graphics hardware, which will require quite a bit more computations. I originally started this project to explore whether haskell is really a capable language in the domain of performance critical applications. I think that with the right optimizations, OmegaGB will be able to do real time emulation. Unfortunately, I am not experienced enough to know what kind of optimizations to use. This is why I am calling out for help. Thanks, Bit Connor PS: Here is some of the profiling output from a typical run: total time = 174.10 secs (3482 ticks @ 50 ms) total alloc = 31,338,925,440 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc renderScanLine Machine 28.6 17.9 machineCpuExecute' Machine 12.6 11.4 tickHBlank Machine 9.1 21.1 tickHBlankMode0 Machine 6.3 13.7 executeInstruction Cpu 5.6 1.6 test02 GuiTest02 5.0 1.4 tickDIV Machine 4.7 13.1 irqUpdate Machine 3.4 0.8 transformIrq Machine 3.3 3.2 tickHBlankMode3 Machine 3.1 6.9 mcti Cpu 2.2 0.5 setRegState Machine 1.9 1.7 setReg2State Machine 1.7 1.8 doFromTo GuiDrawUtil 1.6 1.5 updateMachine Machine 1.4 0.5 updateMachineDisplayFrame Machine 1.3 0.5 writeFlags CpuExecution 1.2 0.3 fetchInstruction Machine 1.1 0.5

2 2

Articles on the value of strong typing
by Jacob Atzen 03 Apr '07

03 Apr '07

Hello list, I am a student at the IT University of Copenhagen doing my final thesis on Domain Specific Languages implemented as embedded languages in Ruby. As you might know Ruby uses a somewhat lax form of typing compared to Haskell which is apparently highly utilized for creating embedded DSL's, at least in the academic world. Additionally many of the articles on embedded languages in Haskell use the typing features of Haskell as an argument for using Haskell in this setting. This lead me to the question: Are there any scientific empirical studies of the values of static / stronger type systems as found in Haskell, C# or Java in real world settings? Or any studies comparing weaker type systems in terms of programmer efficiency, defect ratio, etc. I have been unable to find any such studies as it supposedly is "common knowledge" that strong type systems are of great value. Additionally the people I have asked the question was not aware of any such studies, so now I'm trying this list. Please note that I am looking for papers or articles, preferably from the academic community, and not personal opinions (as valid as they may be). -- Thank you, - Jacob Atzen

6 6

ANNOUNCE: Phooey 1.0 and GuiTV 0.3
by Conal Elliott 30 Mar '07

30 Mar '07

I'm happy to announce a new version of Phooey<http://haskell.org/haskellwiki/Phooey>, a library for functional user interfaces. Highlights in this release: - Uses new TypeCompose <http://haskell.org/haskellwiki/TypeCompose>package, which includes a simple implementation of data-driven computation. - New Applicative functor interface. - Eliminated the catch-all Phooey.hs module. Now import any one of Graphics.UI.Phooey.{Monad,Applicative,Arrow}. - Phooey.Monad has two different styles of output widgets, made by owidget and owidget'. The latter is used to implement Phooey.Applicative. - Self- and mutually-recursive widgets now work again in Phooey.Monad. They wedge in Phooey.Arrow and Phooey.Applicative. Phooey is also used in GuiTV <http://haskell.org/haskellwiki/GuiTV>, a library for composable interfaces and "tangible values". I've also just updated GuiTV to 0.3, to sync with Phooey 1.0. - Conal

1 0

ANNOUNCE: TypeCompose 0.0
by Conal Elliott 30 Mar '07

30 Mar '07

TypeCompose <http://haskell.org/haskellwiki/TypeCompose> provides some classes & instances for forms of type composition. It also includes a very simple implementation of data-driven computation. I factored it out of a new implementation of Phooey <http://haskell.org/haskellwiki/Phooey>. I am very interested in comments and contributions. - Conal

1 0