July 2009 - Haskell-Cafe

Python vs Haskell in tying the knot
by Cristiano Paris 17 Jul '09

17 Jul '09

Hi, as pointed out in this list, it seems that a "tying the knot" example would be the one better explaining the power of Haskell's lazy-by-default approach against Python+Iterator's approach to laziness. So, in these days I'm trying to grasp the meaning of this "tying the knot" concept which seems to be quite hard to understand for me (at least as much as Monads and Delimited Continuations were). Specifically, I was looking for a very basic example of TTK and came up with this implementation of Fibonacci (again!) which might possibly be a TTK-flavored way for generation: fib = 1:1:fib `plus` (tail fib) where plus = zipWith (+) Of course, this was something I already encountered when exploring the Y-combinator. Anyhow, I tried to translate this implementation to Python using Iterators and this is what I wrote: def fib(): yield 1 yield 1 p = plus(fib(),tail(fib())) while True: yield p.next() def plus(x,y): while True: yield x.next() + y.next() print take(5,fib()) I've omitted the implementation for tail() and take() for brevity. Apart from the iterator machinery, this is an direct translation of the Haskell's fib implementation. More, it's quite modular because fib lives by itself and is composed with take to get the final result. The only caveat in the Python code is that it maintains an O(n^2) Iterator's states, thus making it a very poor implementation. So my considerations are: 1 - The Fibonacci generator is not an example of TTK at all and then it can be translated to Python. 2 - The Fibonacci generator is a too simple example of TTK, easy to be translated to Python. 3 - The O(n^2) state caveat is THE point making the difference between Haskell and Python, for which Haksell is much more efficient that Python while remaining very expressive and idiomatic (but that may not be the case for other TTK examples). I'm trying to implement myself the doubly linked list example from the Wikipage, which is "certified" to be a TTK example, but I'd like to have your comments on this. Thank you. Cristiano

6 6

Parsec for C or C++
by Roy Lowrance 17 Jul '09

17 Jul '09

I am working on a research language that is a variant of C. I'd like to use Parsec as the parser. Is there an existing Parsec parser for C or C++ (or Java) that could serve as a starting point? Thanks, Roy

4 6

Parallellizing array-based function
by Jon Harrop 17 Jul '09

17 Jul '09

Is it possible to parallelize array-based functions such as in-place quicksort in Haskell? If so, does anyone have a working implementation? -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e

1 0

PEPM'10 - Call for Papers (Deadline: 6 Oct 09) - Invited Speakers announced
by Janis Voigtlaender 17 Jul '09

17 Jul '09

=============================================================== CALL FOR PAPERS ACM SIGPLAN 2010 Workshop on Partial Evaluation and Program Manipulation (PEPM'10) Madrid, January 18-19, 2010 (Affiliated with POPL'10) http://www.program-transformation.org/PEPM10 =============================================================== INVITED SPEAKERS: * Lennart Augustsson (Standard Chartered Bank, UK) * Jeremy Siek (University of Colorado at Boulder, USA) IMPORTANT DATES: * Paper submission: Tue, October 6, 2009, 23:59, Apia time * Author notification: Thu, October 29, 2009 * Camera-ready papers: Mon, November 9, 2009 To facilitate smooth organization of the review process, authors are asked to submit a short abstract by October 1, 2009. SUBMISSION CATEGORIES: * Regular research papers (max. 10 pages in ACM Proceedings style) * Tool demonstration papers (max. 4 pages plus max. 6 pages appendix) TRAVEL SUPPORT: Students and other attendants in need can apply for a SIGPLAN PAC grant to help cover expenses. For details, see http://www.sigplan.org/PAC.htm. SCOPE: The PEPM Symposium/Workshop series aims to bring together researchers and practitioners working in the areas of program manipulation, partial evaluation, and program generation. PEPM focuses on techniques, theories, tools, and applications of analysis and manipulation of programs. The 2010 PEPM workshop will be based on a broad interpretation of semantics-based program manipulation in a continued effort to expand the scope of PEPM significantly beyond the traditionally covered areas of partial evaluation and specialization and include practical applications of program transformations such as refactoring tools, and practical implementation techniques such as rule-based transformation systems. In addition, it covers manipulation and transformations of program and system representations such as structural and semantic models that occur in the context of model-driven development. In order to reach out to practitioners, there is a separate category of tool demonstration papers. Topics of interest for PEPM'10 include, but are not limited to: * Program and model manipulation techniques such as transformations driven by rules, patterns, or analyses, partial evaluation, specialization, program inversion, program composition, slicing, symbolic execution, refactoring, aspect weaving, decompilation, and obfuscation. * Program analysis techniques that are used to drive program/model manipulation such as abstract interpretation, static analysis, binding-time analysis, dynamic analysis, constraint solving, type systems, automated testing and test case generation. * Analysis and transformation for programs/models with advanced features such as objects, generics, ownership types, aspects, reflection, XML type systems, component frameworks, and middleware. * Techniques that treat programs/models as data objects including meta-programming, generative programming, deep embedded domain-specific languages, program synthesis by sketching and inductive programming, staged computation, and model-driven program generation and transformation. * Application of the above techniques including experimental studies, engineering needed for scalability, and benchmarking. Examples of application domains include legacy program understanding and transformation, DSL implementations, visual languages and end-user programming, scientific computing, middleware frameworks and infrastructure needed for distributed and web-based applications, resource-limited computation, and security. We especially encourage papers that break new ground including descriptions of how program/model manipulation tools can be integrated into realistic software development processes, descriptions of robust tools capable of effectively handling realistic applications, and new areas of application such as rapidly evolving systems, distributed and web-based programming including middleware manipulation, model-driven development, and on-the-fly program adaptation driven by run-time or statistical analysis. PROCEEDINGS: There will be formal proceedings published by ACM Press. In addition to printed proceedings, accepted papers will be included in the ACM Digital Library. Selected papers may later on be invited for a journal special issue dedicated to PEPM'10. SUBMISSION GUIDELINES: Papers should be submitted electronically via the workshop web site. Regular research papers must not exceed 10 pages in ACM Proceedings style. Tool demonstration papers must not exceed 4 pages in ACM Proceedings style, and authors will be expected to present a live demonstration of the described tool at the workshop (tool papers should include an additional appendix of up to 6 extra pages giving the outline, screenshots, examples, etc. to indicate the content of the proposed live demo at the workshop). Authors using Latex to prepare their submissions should use the new improved SIGPLAN proceedings style (sigplanconf.cls). PROGRAM CO-CHAIRS: * John Gallagher (Roskilde University, Denmark, and IMDEA Software, Spain) * Janis Voigtländer (Technische Universität Dresden, Germany) PROGRAM COMMITTEE MEMBERS: * Wei-Ngan Chin (National University of Singapore, Singapore) * Michael Codish (Ben-Gurion University of the Negev, Israel) * Jim Cordy (Queen's University, Canada) * Nate Foster (University of Pennsylvania, USA) * Haifeng Guo (University of Nebraska at Omaha, USA) * Patricia Johann (University of Strathclyde, UK) * Oleg Kiselyov (FNMOC, USA) * Günter Kniesel (University of Bonn, Germany) * Viktor Kuncak (Ecole Polytechnique Fédérale de Lausanne, Switzerland) * Yanhong Annie Liu (State University of New York at Stony Brook, USA) * Andres Löh (Utrecht University, Netherlands) * Jan Midtgaard (Roskilde University, Denmark) * David Monniaux (National Center for Scientific Research (CNRS) and VERIMAG laboratory, France) * Akimasa Morihata (University of Tokyo, Japan) * Alberto Pettorossi (Università di Roma Tor Vergata, Italy) * João Saraiva (Universidade do Minho, Portugal) * Ganesh Sittampalam (Credit Suisse, UK) * Fausto Spoto (Università di Verona, Italy) * Harald Søndergaard (University of Melbourne, Australia) * Walid Taha (Rice University, USA)

1 0

A voyage of undiscovery
by Bernie Pope 17 Jul '09

17 Jul '09

2009/7/17 Andrew Coppin <andrewcoppin(a)btinternet.com>: > I've been working hard this week, and I'm stumbled upon something which is > probably of absolutely no surprise to anybody but me. > > Consider the following expression: > > (foo True, foo 'x') > > Is this expression well-typed? > > Astonishingly, the answer depends on where "foo" is defined. If "foo" is a > local variable, then the above expression is guaranteed to be ill-typed. > However, if we have (for example) > > foo :: x -> x > > as a top-level function, then the above expression becomes well-typed. Some useful reading material: Section 22.7 of the book "Types and Programming Languages" by Benjamin Pierce. The classic paper "Basic Polymorphic Typechecking" by Luca Cardelli: http://lucacardelli.name/Papers/BasicTypechecking.pdf Both of these are very readable introductions to the let-style polymorphism found in the Hindley/Milner type system. Haskell's type system is essentially an elaboration of that idea. Pierce's book shows how to achieve let-polymorphism by inlining non-recursive let bindings during type checking/inference, which is a nice way to understand what is going on.

1 0

Atom resources
by Thomas DuBuisson 16 Jul '09

16 Jul '09

The wiki [1] where Atom [2] once lived has been gone for some time now. The only resources I know for Atom are a couple blog posts, the haddock docs, and the Atom source on patchtag. Is anyone aware of other resources? Tom [1] http://funhdl.org/wiki/doku.php [2] http://hackage.haskell.org/package/atom

3 3

another laziness blowup (this one unsolved)
by Thomas Hartman 16 Jul '09

16 Jul '09

Is it possible to fix alternate' (the second version), or otherwise define a fast stepwise alternate that doesn't blow up on long lists? alternate just breaks up [1,2,3,4,5] into ([1,3,5],[2,4]) Thanks! {-# LANGUAGE BangPatterns #-} import Data.List import Control.Arrow import Control.Parallel.Strategies t = (last *** last) $! alternate $ [1..(10^6)] t' = (last *** last) $! alternate' $ [1..(10^6)] t'' = (last *** last) $! alternate'' $ [1..(10^6)] -- finishes reasonably fast, but does a separate computation for the list and its tail rather than just rip through it alternate x = (skip1 x,(skip1 $ tail x)) skip1 = skip 1 skip n xs = let (a,b) = splitAt (n+1) xs in case a of [] -> [] x:_ -> x : skip n b -- this one overflows on million element list, even after fiddling with strictness on input args. can this be fixed? alternate' xs = let f3 :: Int -> (([Int],[Int]),Int) -> (([Int],[Int]),Int) f3 x ((a,b),n) = -- rnf (x,((a,b),n)) `seq` let nxtn = n+1 in if n `mod` 2 == 0 then ((x:a,b),nxtn) else ((a,x:b),nxtn) in fst . foldr f3 (([],[]),0) $ xs -- no overflow, goes through the list stepwise, but it's actually slightly slower than the first alternate because of the reverses alternate'' xs = let f3 ((a,b),n) x = (let nxtn = n+1 in if n `mod` 2 == 0 then ((x:a,b),nxtn) else ((a,x:b),nxtn) ) in (reverse *** reverse) . fst . foldl' f3 (([],[]),0) $ xs

1 1

Re: [Haskell-cafe] Leaner Haskell.org frontpage
by haskell＠kudling.de 16 Jul '09

16 Jul '09

I never said we should only expose 7 links. Take for example the task "Find out more about this Haskell i heared about". You would need to scan the right half of the front page and you need to scan the left part of the page. There you need to scan "About", it could be explained under "Why use Haskell?" or "Language definition" or "Haskell in 5 steps" or "Learning Haskell" or "Wiki articles" or "Blog articles and news". Where should i look? I have to scan a lot of text, i have to keep a lot of options in mind and for my taste the load is too much. Be my limit 7 or 20 links. haskell(a)kudling.de wrote: > Most people feel overwhelmed when confronted with more than 7+-2 items: > http://www.smashingmagazine.com/2007/10/09/30-usability-issues-to-be-aware-… This refers to the number of items/things people can remember in their short-time memory. This has nothing to do with the maximum number of menu items you should use. There is of course a limit, but there is no reason to limit it to 7+-2. Cheers, -- Jochem Berndsen | jochem(a)functor.nl GPG: 0xE6FABFAB

11 16

Applying different functions to different types for lists
by Szekeres István 16 Jul '09

16 Jul '09

Hi, I want to build a framework to apply different functions to different types of lists and I want to generalize the solution as much as possible but my Haskell knowledge is not really enough to do this (I'm a haskell novice). The problem has two dimensions: 1. Lets say I have two functions: r13, ul : Char -> Char where r13 returns the rot13ed character, and ul converts upper case chars to lower case and vice versa. Later I want a rot13 function that can operate on different types of lists and an uxl function that can also operate on different types of lists. 2. Lets say I have two kinds of lists to handle: String and Data.ByteString.Lazy as L. For Strings I want the updater function to be used for each character and for L I want all items to be converted to Char, the updater function to be updated and the result to be converted back to the original item type. Therefore I define a common class for handling these lists: class ListUpdater a where updateFn :: Char -> Char update :: a -> a so I can define the update function for the different types of lists: instance ListUpdater String where update = map updateFn instance ListUpdater L.ByteString where update = L.pack . (map updateFn) . L.unpack But now how should I glue these 2 dimensions together? How to say that I want a rot13 function that applies to any data type instantiated from ListUpdater and that is using the r13 function to do the update? And also that I want an uxl function that also applies to any data type instantiated from ListUpdater and that is using the ul function to do the update? Thanks, Istvan

2 1

IFL 2009: Third Call for Papers
by IFL 2009 16 Jul '09

16 Jul '09

1 0