April 2008 - 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

The real Monad Transformer
by Henning Thielemann 13 Nov '08

13 Nov '08

It was argued that people avoid Haskell because of terms from Category theory like 'Monad'. This problem can now be solved by a wrapper which presents all the WWW without monads! Start e.g. at http://saxophone.jpberlin.de/MonadTransformer?source=http%3A%2F%2Fwww%2Ehas… Of course the tool is written in Haskell, that is, Haskell helps solving problems which only exist because of Haskell. Bug reports and feature requests can be tracked at https://sourceforge.net/projects/parallelweb

8 10

NW Functional Programming Interest Group
by Greg Meredith 19 Jul '08

19 Jul '08

All, Apologies for multiple listings. A small cadre of us are organizing a Northwest Functional Programming Interest Group (hey... NWFPIG, that's kinda funny). Our first official meeting is at the The Seattle Public Library 1000 - 4th Ave. Seattle, WA 98104 from 17:00 - 18:00 on February 20th. On the first meeting's agenda we'll be - giving people who are interested in or actively using FP for work or play a chance to meet - seeking to build up a pipeline of presentations and guest speakers - trying to keep organizational mishigosh to a minimum Hope to see you there. Monadically yours, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 806 55th St NE Seattle, WA 98105 +1 206.650.3740 http://biosimilarity.blogspot.com

1 6

How to define tail function for Even/Odd GADT lists?
by Ahn, Ki Yung 05 May '08

05 May '08

Using GADTs and functional dependencies, we can define GADT lists that statically distinguishes even length lists from odd length lists. > data Even > data Odd > > class Flip b c | b -> c, c -> b where > > instance Flip Even Odd where > instance Flip Odd Even where > > data List a b where > Nil :: List a Even > Cons :: Flip b c => a -> List a b -> List a c For example, Nil :: forall a. List a Even Cons True Nil :: List Bool Odd Cons False (Cons True Nil) :: List Bool Even We were able to define the function that returns the head. > headList :: List a b -> a > headList (Cons x _) = x However, we were not able to write a function that returns the tail. > tailList :: Flip b c => List a b -> List a c > tailList (Cons _ xs) = xs Is there a way to define the tailList function within the current GHC type system implementation (maybe using some other language extensions), or do we need to improve the type system regarding GADTs and functional dependencies? $ ghci -fglasgow-exts EOlist.hs GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. [1 of 1] Compiling Main ( EOlist.lhs, interpreted ) EOlist.lhs:30:25: Couldn't match expected type `c' against inferred type `b1' `c' is a rigid type variable bound by the type signature for `tailList' at EOlist.lhs:29:21 `b1' is a rigid type variable bound by the constructor `Cons' at EOlist.lhs:30:12 Expected type: List a c Inferred type: List a b1 In the expression: xs In the definition of `tailList': tailList (Cons _ xs) = xs Failed, modules loaded: none. Prelude> Note: You can save this message content as EOList.lhs and load the script with ghci to observe the type error message above.

3 2

Matrix multiplication
by Tillmann Vogt 29 Apr '08

29 Apr '08

Hi, I am currently experimenting with parallelizing C-programs. I have therefore written a matrix vector multiplication example that needs 13 seconds to run (5 seconds with OpenMP). Because I like Haskell I did the same in this language, but it takes about 134 seconds. Why is it so slow? Does someone have an idea? module Main where main = do putStrLn (show (stupid_mul 100)) putStrLn "100 multiplications done" stupid_mul 0 = [] stupid_mul it = (s_mul it) : stupid_mul (it-1) -- without "it" after s_mul only one multiplication is executed s_mul it = mul (replicate 4000 [0..3999]) (replicate 4000 2) mul :: [[Double]] -> [Double] -> [Double] mul [] _ = [] mul (b:bs) c | sp==0 = sp : (mul bs c) -- always false, force evaluation | otherwise = (mul bs c) where sp = (scalar b c) scalar :: [Double] -> [Double] -> Double scalar _ [] = 0 scalar [] _ = 0 scalar (v:vs) (w:ws) = (v*w) + (skalar vs ws) and here the C-program #include <stdio.h> #include <stdlib.h> #include <time.h> #define M 4000 #define N 4000 #define IT 100 double a[M], b[M][N], c[N]; int main(int argc, char *argv[]) { double d; int i, j, l; time_t start,end; printf("Initializing matrix B and vector C\n"); for(j=0; j<N; j++) c[j] = 2.0; for(i=0; i<M; i++) for(j=0; j<N; j++) b[i][j] = j; printf("Executing %d matrix mult. for M = %d N = %d\n",IT,M,N); time (&start); for(l=0; l<IT; l++) #pragma omp parallel for default(none) \ shared(a,b,c) private(i,j,l) for(i=0; i<M; i++) { a[i] = 0.0; for (j=0; j<N; j++) a[i] += b[i][j]*c[j]; } time (&end); d = difftime (end,start); printf ("calculation time: %.2lf seconds\n", d ); return 0; }

4 3

ANNOUNCE: category-extras 0.2
by Dan Doel 28 Apr '08

28 Apr '08

Hello, all. After quite a bit of collaboration with Edward Kmett over the past few days, I've rolled up a new release of category-extras. Perhaps the most significant addition is the generalized hylomorphism he first blogged about here: http://comonad.com/reader/2008/generalized-hylomorphisms/ added to Control.Recursion under the name 'refoldWith', as all other combinators in the library turn out to be special cases of it. Other changes include: * Data.BranchingStream moves to Control.Comonad.Cofree, and various functions are renamed accordingly, as it is the cofree comonad of a functor: Cofree F A = nu X. A * FX * Similarly, a new module has been added: Control.Monad.Free, the free monad of a functor. Free F A = mu X. A + FX * Several new recursion combinators have been added to Control.Recursion. The generalized hylomorphism 'refoldWith' was mentioned above, but we now also have: - Futumorphisms (futu, g_futu) - Chronomorphisms (chrono, g_chrono; name coined by edwardk; they're a combination of a histomorphism and a futumorphism). - Dynamorphisms (dyna, g_dyna; formalize dynamic programming) - Codynamorphisms (codyna, g_codyna; these apparently don't appear in any literature (like chronomorphisms), and we didn't attempt to give them a name, but once one sees dynamorphisms in terms of chronomorphisms/ g_hylomorphisms, this becomes fairly obvious). As can be seen, there's quite a glut of these combinators, and they all correspond to choices of distributive laws for refoldWith, so in the future, it may be better to talk about those directly. For now, though, we have lots of functions with fancy-sounding names. I believe those are the significant updates for this release. Enjoy. hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/category-extras-… darcs: darcs get http://code.haskell.org/~dolio/category-extras/ -- Dan

1 0

Call for Contributions - Haskell Communities and Activities Report, May 2008 edition
by Janis Voigtlaender 25 Apr '08

25 Apr '08

Dear Haskellers, so much has happened in the Haskell world in the past months. Therefore, we would very much like to collect contributions for the 14th edition of the ================================================================ Haskell Communities & Activities Report http://www.haskell.org/communities/ Submission deadline: 10 May 2008 (please send your contributions to hcar at haskell.org, in plain text or LaTeX format) ================================================================ This is the short story: * If you are working on any project that is in some way related to Haskell, please write a short entry and submit it to the us. Even if the project is very small or unfinished or you think it is not important enough -- please reconsider and submit an entry anyway! * If you are interested in any project related to Haskell that has not previously been mentioned in the HC&A Report, please tell us, so that we can contact the project leaders and ask them to submit an entry. * Feel free to pass on this call for contributions to others that might be interested. More detailed information: The Haskell Communities & Activities Report is a bi-annual overview of the state of Haskell as well as Haskell-related projects over the last, and possibly the upcoming 6 months. If you have only recently been exposed to Haskell, it might be a good idea to browse the December 2007 edition -- you will find interesting topics described as well as several starting points and links that may provide answers to many questions. Contributions will be collected until the submission deadline. They will then be compiled into a coherent report that is published online as soon as it is ready. As always, this is a great opportunity to update your webpages, make new releases, announce or even start new projects, or to talk about developments you want every Haskeller to know about! As the purpose of the report is to collect recent or current activities, we encourage you to update all existing summaries and reports. We will probably drop any topics that have not had any activity for the past year, i.e., since May 2007, but we would very much prefer you to present an updated description of the topic. Of course, new entries are more than welcome. Reports should generally be kept brief and informative, ranging from a few sentences to a few hundred words, to keep the whole report reasonably sized. Looking forward to your contributions, Andres and Janis (current editors) FAQ: Q: Which topics are relevant? A: *All* topics which are related to Haskell in some way are relevant. We usually had reports from users of Haskell (private, academic, or commercial), from authors or contributors to projects related to Haskell, from people working on the Haskell language, libraries, on language extensions or variants. We also like reports over distributions of Haskell software, Haskell infrastructure, books and tutorials on Haskell. Reports on past and upcoming events related to Haskell are also relevant. Finally, there might be new topics we don't even think about. As a rule of thumb: if in doubt, then it probably is relevant and has a place in the HCAR. You can also ask the editors. Q: Is unfinished work relevant? Are ideas for projects relevant? A: Yes! You can use the HCAR to talk about projects you are currently working on. You can use it to look for other developers that might help you. You can use it to write ``wishlist'' items for libraries and language features you would like to see implemented. Q: How much should I write? A: There's no formal limit. But generally, entries should be short and to the point. A general introduction is helpful. Apart from that, you should focus on recent or upcoming developments. There also is no minimum length of an entry! The report aims at being as complete as possible, so please consider writing an entry, even if it's only a few lines long. Q: If I don't update my entry, but want to keep it in the report, what should I do? A: Tell us that there are no changes. We will reuse the old entry in this case, but we might drop it if it's older than a year, to give more room and more attention to projects that change a lot. Don't resent complete entries if you haven't changed them. Q: What format should I write in? A: The best format is a LaTeX source file, adhering to the template that's available at: http://haskell.org/communities/05-2008/template.tex There's also a LaTeX style file at http://haskell.org/communities/05-2008/hcar.sty that you can use to preview your entry. If you don't know LaTeX, then use plain text. If you modify an old entry, we will send you your old entry as a template within the next hours (provided we have your valid email address). Please modify that template, rather than using your own version of the old entry as a template. Don't worry about writing correct LaTeX, we will be able to handle your file. Please don't use HTML or even DOC. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

2 1

making inits less strict
by John Tromp 24 Apr '08

24 Apr '08

The standard definition of inits: inits [] = [[]] inits (x:xs) = [[]] ++ map (x:) (inits xs) is unnecessarily strict, evaluating its argument before yielding the initial [] of the result. An improved version is: inits l = [] : case l of [] -> [] (x:xs) -> map (x:) inits xs This allows one to define for instance nats = map length (inits nats) which loops for the standard definition. regards, -John

2 1

Matrix multiplication
by Rishiyur Nikhil 24 Apr '08

24 Apr '08

You may be interested in also looking at the winning entry in the design competition of the "5th ACM-IEEE Intl. Conf. on Formal Methods and Models for Codesign (MEMOCODE'2007)" http://www.ece.cmu.edu/~jhoe/distribution/mc07contest/ The design problem was a fast matrix multiplier using a combination of SW and HW (FPGA). The winning design was implemented using BSV (Bluespec SystemVerilog, www.bluespec.com) which takes its major ideas from Haskell and Term Rewriting Systems. [ For even more spectacular results, take a look at this year's MEMOCODE design contest winner. http://rijndael.ece.vt.edu/memocontest08/ The problem was to decrypt, sort and re-encrypt a file of records. Out of 27 entrants, 9 finished the contest. The winning entry was written entirely using BSV, and beat the second-place finisher by a factor of 11x (yes, 11x, not 11%), and beat the reference software implementation by 1100x. ] Regards, Nikhil

1 0