- Haskell-Cafe - Haskell.org

ANNOUNCE: vacuum: extract graph representations of ghc heap values.
by Matt Morrow 02 Apr '09

02 Apr '09

I am pleased to announce the release of vacuum, a Haskell<http://haskell.org/>library for extracting graph representations of values from the GHC <http://haskell.org/ghc/> heap, which may then be further processed and/or translated to Graphviz <http://graphviz.org/> dot format to be visualized. The package website is at http://moonpatio.com/vacuum/, which contains a gallery section (which i intend to add to over time). The most recent version is 0.0.6, which is available on Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/vacuum/. Feedback, comments, and/or gallery submissions will be gratefully received via this email address (contrary to the email address currently on the vacuum Hackage page (i fail at setting up email :)). Matt

2 2

Re: [Haskell-cafe] uvector package appendU: memory leak?
by Manlio Perillo 02 Apr '09

02 Apr '09

wren ng thornton ha scritto: > Manlio Perillo wrote: >> Since ratings for each customers are parsed "at the same time", using >> a plain list would consume a lot of memory, since stream fusion can >> only be executed at the end of the parsing. >> >> On the other hand, when I want to group ratings by movies, stream >> fusion seems to work fine. >> > [...] > > For the problem as you've discussed it, I'd suggest a different > approach: You can't fit all the data into memory at once, so you > shouldn't try to. You should write one program that takes in the > per-movie grouping of data and produces a per-user file as output. Well, creating 480189 files in a directory is not a very nice thing to do to a normal file system. I should arrange files in directory, but then this starts to become too complex. The solution I'm using now just works. It takes about 950 MB of memory and 35 minutes, but it's not a big problem since: 1) Once loaded, I can serialize the data in binary format 2) I think that the program can be parallelized, parsing subsets of the files in N threads, and then merging the maps. Using this method, should optimize array copying. The problem is that unionWith seems to be lazy, and there is no no strict variant; I'm not sure. > Then > have your second program read in the reorganized data and do fusion et al. > > This reduces the problem to just writing the PerMovie -> PerUser > program. Since you still can't fit all the data into memory, that means > you can't hope to write the per-user file in one go. The data *do* fit into memory, fortunately. > [...] > > Best of luck. > Thanks Manlio

2 1

Zippers from any traversable [Was: Looking for practical examples of Zippers]
by oleg＠okmij.org 02 Apr '09

02 Apr '09

wren ng thornton wrote: > > how, for instance, turn a nested Map like > > > > Map Int (Map Int (Map String Double) > > > > into a "zipped" version. > You can't. Or rather, you can't unless you have access to the > implementation of the datastructure itself; and Data.Map doesn't provide > enough details to do it. Actually Data.Map does provide enough details: Data.Map is a member of Traversable and anything that supports Traversable (at the very least, provides something like mapM) can be turned into a Zipper. Generically. We do not need to know any details of a data structure (or if it is a data structure: the collection may well be ephemeral, whose elements are computed on the fly). Please see the enclosed code; the code defines a function tmod to interactively traverse the collection, displaying the elements one by one and offering to modify the current element, or quit the traversal. The enclosed code implements the zipper that can only move forward. Chung-chieh Shan has well described how to turn any one-directional zipper into bi-directional. Again generically. http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WalkZip3/ Although the enclosed code demonstrates the possibility of turning a Data.Map into a Zipper, one may wonder about the merits of that endeavour. Data.Map is a very rich data structure, with efficient means to focus on any given element and replace it (e.g., elemAt, replaceAt) and to incrementally deconstruct the map (deleteMax, deleteMin, minView, etc). Triple-nested maps can be processed just as effectively. The case for a tree of maps (which is essentially a file system) is described in http://okmij.org/ftp/Computation/Continuations.html#zipper-fs module ZT where import qualified Data.Traversable as T import Control.Monad.Cont import qualified Data.Map as M -- In the variant Z a k, a is the current, focused value -- evaluate (k Nothing) to move forward -- evaluate (k v) to replace the current value with v and move forward. data Zipper t a = ZDone (t a) | Z a (Maybe a -> Zipper t a) make_zipper :: T.Traversable t => t a -> Zipper t a make_zipper t = reset $ T.mapM f t >>= return . ZDone where f a = shift (\k -> return $ Z a (k . maybe a id)) zip_up :: Zipper t a -> t a zip_up (ZDone t) = t zip_up (Z _ k) = zip_up $ k Nothing reset :: Cont r r -> r reset m = runCont m id shift :: ((a -> r) -> Cont r r) -> Cont r a shift e = Cont (\k -> reset (e k)) -- Tests -- sample collections tmap = M.fromList [ (v,product [1..v]) | v <- [1..10] ] -- extract a few sample elements from the collection trav t = let (Z a1 k1) = make_zipper t (Z a2 k2) = k1 Nothing (Z a3 k3) = k2 Nothing (Z a4 k4) = k3 Nothing in [a1,a3,a4] travm = trav tmap -- Traverse and possibly modify elements of a collection tmod t = loop (make_zipper t) where loop (ZDone t) = putStrLn $ "Done\n: " ++ show t loop (Z a k) = do putStrLn $ "Current element: " ++ show a ask k ask k = do putStrLn "Enter Return, q or the replacement value: " getLine >>= check k check k "" = loop $ k Nothing check k "\r" = loop $ k Nothing check k ('q':_) = loop . ZDone . zip_up $ k Nothing check k s | [(n,_)] <- reads s = loop $ k (Just n) -- replace check k _ = putStrLn "Repeat" >> ask k testm = tmod tmap

2 1

Parsing with Proof
by muad 01 Apr '09

01 Apr '09

Hi everyone on haskell-cafe, I am wondering about how to give a correctness prove of a simple parsing algorithm. I tried to think of a simple example but even in this case I don't know how. I have an abstract syntax: > data Parens = Empty | Wrap Parens | Append Parens Parens assumption (A), in Append x y, x and y are never Empty assumption (B), Strings only contain '(' and ')' characters and a printing function > print :: Parens -> String > print Empty = "" > print (Wrap m) = "(" ++ print m ++ ")" > print (Append x y) = print x ++ print y So the idea is that I would like to write parse :: String -> Maybe Parens, such that if it gives Nothing then the String was malformed, if it gives Just x then the string should be equal to print x. I think I can write such a function in a few different ways, but I don't know how to prove this code works, could anybody show me how? Thank you for any replies. -- View this message in context: http://www.nabble.com/Parsing-with-Proof-tp22814576p22814576.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 3

Re: Definition of "tail recursive" wrt Folds
by Ben Franksen 01 Apr '09

01 Apr '09

Mark Spezzano wrote: > Just looking at the definitions for foldr and foldl I see that foldl is > (apparently) tail recursive while foldr is not. > > Why? > > Is it because foldl defers calling itself until last whereas foldr > evaluates itself as it runs? > > What, strictly speaking, is the definition of ”tail recursive” as opposed > to just “recursive”? An application of some function f inside another function g is in 'tail position' (or a 'tail call') if the result of applying f is the result of g. Operationally speaking, calling f is the very last thing g does. Tail calls can be optimized by a compiler (or interpreter) so that the call does not use additional stack; that is, the call can be replaced by a jump. A function is called ”tail recursive” (as opposed to just “recursive”) if the recursive call to itself is in tail position. If the compiler performs tail call optimization, tail recursive functions can work with constant stack space, similar to a (imperative) loop. Looking at a definition of foldl, e.g. foldl f z0 xs0 = lgo z0 xs0 where lgo z [] = z lgo z (x:xs) = lgo (f z x) xs you see that lgo calls itself in tail position, thus is tail recursive. In contrast, foldr can be defined as foldr k z xs = go xs where go [] = z go (y:ys) = y `k` go ys where you see that the result of go is not the recursive call to go. Instead, the result is y `k` go ys . Thus, foldr is not tail recursive. So, if you are saying that "foldl defers calling itself until last whereas foldr evaluates itself as it runs" then you got the right idea, I think. The point is that foldr still needs to do something (namely to apply (y `k`)) to the result of applying itself. It needs to remember to do so, and thus the stack grows linearly with the size of the list. Cheers Ben

2 2

ANN: cmonad 0.1.1
by Lennart Augustsson 01 Apr '09

01 Apr '09

I've uploaded my CMonad package to Hackage. It allows you to write Haskell code in a C style. Unfortunately, GHC lacks certain optimizations to make efficient code when using CMonad, so instead of C speed you get low speed. Example: Computing some Fibonacci numbers: fib = do { a <- arrayU[40]; i <- auto 0; a[0] =: 1; a[1] =: 1; for (i =: 2, (i :: EIO Int) < 40, i += 1) $ do { a[i] =: a[i-1] + a[i-2]; }; retrn (a[39]); } Example: Copying stdin to stdout: cat = do { c <- auto 0; while ((c =: getchar()) >= 0) $ do { putchar(c); }; return (); } -- Lennart

16 22

[SoC] XML Schema Implementation
by Vlad Dogaru 01 Apr '09

01 Apr '09

Hello everyone, I am writing to judge interest in a Summer of Code proposition: an XML Schema[1] implementation, described as a possbile application here[2]. As both a tool and an inspiration, I intend to use HaXML[3]. More specifically, I would be interested in the degree the Haskell community uses XML Schema, and if you were tempted to use it if we had an implementation. To further expand the question, how useful do you consider each of these components: * a validator * a pretty-printer * a translator from XML Schema to Haskell, similar to DtdToHaskell[4] For the latter item, some runtime checking will definitely be required: restrictions such as value ranges for integers or minimum and maximum occurences of an element cannot, to my knowledge, be enforced through type definitions. Finally, I kindly ask anyone with relevant experience to point out other possible pitfalls. Vlad Dogaru [1] http://www.w3schools.com/Schema/ [2] http://hackage.haskell.org/trac/summer-of-code/ticket/1120 [3] http://www.cs.york.ac.uk/fp/HaXml/ [4] http://www.cs.york.ac.uk/fp/HaXml/Xml2Haskell.html

6 6

Re: [Haskell] Marketing Haskell
by Maarten Hazewinkel 01 Apr '09

01 Apr '09

That's not you usual Koala face. Must be a special Simon^H^H^H^H^HHaskell-Koala species. On 1 Apr 2009, at 10:07, Simon Peyton-Jones wrote: > > Dear Haskell enthusiasts, > > Now that the logo issue finally has been settled, it is time to select > the proper Haskell mascot. As you are no doubt aware, Microsoft's > involvement in Haskell means that we have moved from avoiding success > at all cost to actively marketing the language, and any language > striving for success is entirely dependent on a cute and distinctive > mascot. Where would Perl be today without its camel? > > Since the recent logo discussion has demonstrated once and for all the > futility of attempting a democratic process in the Haskell community - > to be quite honest, the elected logo looks like an error message > from an IBM > mainframe - I have decided to decide on a mascot myself. > > So I hereby declare the official Haskell mascot to be the koala, in > the form of the image attached below. Please ensure that this image > accompanies any material published on the web or on paper. > > Simon > > <haskell-mascot.jpg>_______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell Maarten Hazewinkel maarten.hazewinkel(a)gmail.com Tel: 06-53 692 432 (+31-653 692 432 from outside the Netherlands)

2 1

DEFUN09: Call for Talks & Tutorials (co-located w/ ICFP09)
by Matthew Fluet (ICFP Publicity Chair) 01 Apr '09

01 Apr '09

Call for Talks and Tutorials ACM SIGPLAN 2009 Developer Tracks on Functional Programming http://www.defun2009.info/ Edinburgh, Scotland, September 3 and 5, 2009 The workshop will be held in conjunction with ICFP 2009 http://www.cs.nott.ac.uk/~gmh/icfp09.html Important dates Proposal Deadline: June 5, 2009, 0:00 UTC Notification: June 19, 2009 DEFUN 2009 invites functional programmers and researchers who know how to solve problems with functional progamming to give talks and lead tutorials at the The ICFP Developer Tracks. We want to know about your favorite programming techniques, powerful libraries, and engineering approaches you've used that the world should know about and apply to other projects. We want to know how to be productive using functional programming, write better code, and avoid common pitfalls. We invite proposals for presentations in the following categories. Lightning talks 5- to 10-minute talks that introduce exciting and promising research or techniques that may be in progress or not yet ready for widespread use, but that offer a glimpse into the near future of real world functional programming. Examples: * Clustered high performance computing in a functional language * Making advanced type systems more accessible to working programmers * How and why we're infiltrating category theory info industry How-to talks 45-minute "how-to" talks that provide specific information on how to solve specific problems using functional programming. These talks focus on concrete examples, but provide useful information for developers working on different projects or in different contexts. Examples: * "How I use Haskell for oilfield simulations." * "How I replaced /sbin/init by a Scheme program." * "How I hooked up my home appliances to an Erlang control system." * "How I got an SML program to drive my BMW." General language tutorials Half-day general language tutorials for specific functional languages, given by recognized experts for the respective languages. Technology tutorials Half-day tutorials on techniques, technologies, or solving specific problems in functional programming. Examples: * How to make the best use of specific FP programming techniques * How to inject FP into a development team used to more conventional technologies * How to connect FP to existing libraries / frameworks / platforms * How to deliver high-performance systems with FP * How to deliver high-reliability systems with FP Remember that your audience will include computing professionals who are not academics and who may not already be experts on functional programming. Presenters of tutorials will receive free registration to CUFP 2009. Submission guidelines Submit a proposal of 150 words or less for either a 45-minute talk with a short Q&A session at the end, or a 300-word-or-less proposal for a 3-hour tutorial, where you present your material, but also give participants a chance to practice it on their own laptops. Some advice: * Give it a simple and straightforward title or name; avoid fancy titles or puns that would make it harder for attendees to figure out what you'll be talking about. * Clearly identify the level of the talk: What knowledge should people have when they come to the presentation or tutorial? * Explain why people will want to attend: o Is the language or library useful for a wide range of attendees? o Is the pitfall you're identifying common enough that a wide range of attendees is likely to encounter it? * Explain what benefits attendees are expected to take home to their own projects. * For a tutorial, explain how you want to structure the time, and what you expect to have attendees to do on their laptops. List what software you'll expect attendees to have installed prior to coming. Submit your proposal in plain text electronically to defun-2009-submissions(a)serpentine.com by the beginning of Friday, June 5 2009, Universal Coordinated Time. Organizers * Yaron Minsky (Jane Street Capital) * Ulf Wiger (Erlang Training and Consulting) * Mike Sperber - co-chair (DeinProgramm) * Bryan O'Sullivan - co-chair (Linden Lab)

1 0

Call for Contributions - Haskell Communities and Activities Report, May 2009 edition
by Janis Voigtlaender 01 Apr '09

01 Apr '09

Dear Haskellers, so much has happened in the Haskell world in the past months. Therefore, I would very much like to collect contributions for the 16th edition of the ================================================================ Haskell Communities & Activities Report http://www.haskell.org/communities/ Submission deadline: 1 May 2009 (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. 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 me, so that I 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 six months. If you have only recently been exposed to Haskell, it might be a good idea to browse the November 2008 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! Looking forward to your contributions, Janis (current editor) FAQ: Q: What format should I write in? A: The required format is a LaTeX source file, adhering to the template that is available at: http://haskell.org/communities/05-2009/template.tex There is also a LaTeX style file at http://haskell.org/communities/05-2009/hcar.sty that you can use to preview your entry. If you do not know LaTeX, then use plain text. If you modify an old entry that you have written for an earlier edition of the report, you should receive your old entry as a template soon (provided I have your valid email address). Please modify that template, rather than using your own version of the old entry as a template. Q: Can I include images? A: Yes, you are even encouraged to do so. Please use .jpg format, then. Q: How much should I write? A: Authors are asked to limit entries to about one column of text. This corresponds to approximately one page, or 40 lines of text, with the above style and template. A general introduction is helpful. Apart from that, you should focus on recent or upcoming developments. Pointers to online content can be given for more comprehensive or ``historic'' overviews of a project. Images do not count towards the length limit, so you may want to use this opportunity to pep entries up. There 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 is only a few lines long. 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 do not 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 editor. 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: If I do not update my entry, but want to keep it in the report, what should I do? A: Tell the editor that there are no changes. The old entry will be reused in this case, but it might be dropped if it is older than a year, to give more room and more attention to projects that change a lot. Do not resend complete entries if you have not changed them. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

1 0