December 2010 - Haskell-Cafe

Question: mime-mail and base64 encoding
by Michael Snoyman 07 Dec '10

07 Dec '10

Hi all, I've gotten a request for the mime-mail package that I'd like some input on. Right now, there's the ability to fully specify whether or not to base64-encode each part in a message, but the included simpleMail function defaults to non-encoded parts for both its HTML and plain text alternatives. This has apparently caused some issues where long HTML strings have been word-wrapped at bad locations, causing breakage in the meaning of the markup. The request is to make both the HTML and plain text parts use base64 encoding by default. This *seems* to me to make a lot of sense, since it will ensure that your message arrives exactly as you intended it, and will ensure that any non-ASCII code points don't get killed somewhere along the way. On the other hand, I'm not sure what client support is like for base-64 encoding. Don't we need to leave *some* form of non-encoded data for less sophisticated email clients? Thanks, Michael

5 5

Fwd: second call for papers: LDTA 2011 / ETAPS
by Paul Brauner 07 Dec '10

07 Dec '10

---------- Forwarded message ---------- From: Emilie Balland <emilie.balland(a)inria.fr> Date: Tue, Dec 7, 2010 at 10:35 PM Subject: second call for papers: LDTA 2011 / ETAPS To: "Paul.Brauner" <Paul.Brauner(a)loria.fr> LDTA 2011 Call for Papers and Tool Challenge Submissions 11th International Workshop on Language Descriptions, Tools, and Applications www.ldta.info Saarbrucken, Germany March 26 & 27, 2011 an ETAPS workshop LDTA is an application and tool-oriented workshop focused on grammarware - software based on grammars in some form. Grammarware applications are typically language processing applications and traditional examples include parsers, program analyzers, optimizers and translators. A primary focus of LDTA is grammarware that is generated from high-level grammar-centric specifications and thus submissions on parser generation, attribute grammar systems, term/graph rewriting systems, and other grammar-related meta-programming tools, techniques, and formalisms are encouraged. LDTA is also a forum in which theory is put to the test, in many cases on real-world software engineering challenges. Thus, LDTA also solicits papers on the application of grammarware to areas including, but not limited to, the following: - program analysis, transformation, generation, and verification, - implementation of Domain-Specific Languages, - reverse engineering and re-engineering, - refactoring and other source-to-source transformations, - language definition and language prototyping, and - debugging, profiling, IDE support, and testing. This year LDTA will also be putting theory, as well as techniques and tools, to the test in a new way - in the LDTA Tool Challenge. Tool developers are invited to participate in the Challenge by developing solutions to a range of language processing tasks over a simple but evolving set of imperative programming languages. Tool challenge participants will present highlights of their solution during a special session of the workshop and contribute to a joint paper on the Tool Challenge and proposed solutions to be co-authored by all participants after the workshop. Note that LDTA is a well-established workshop similar to other conferences on (programming) language engineering topics such as SLE and GPCE, but is solely focused on grammarware. Paper Submission ---------------- LDTA solicits papers in the following categories. - research papers: original research results within the scope of LDTA with a clear motivation, description, analysis, and evaluation. - short research papers: new innovative ideas that have not been completely fleshed out. As a workshop, LDTA strongly encourages these types of submissions. - experience report papers: description of the use of a grammarware tool or technique to solve a non-trivial applied problem with an emphasis on the advantages and disadvantages of the chosen approach to the problem. - tool demo papers: discussion of a tool or technique that explains the contributions of the tool and what specifically will be demonstrated. These papers should describe tools and applications that do not fit neatly into the specific problems in the Tool Challenge. Each submission must clearly state in which of these categories it falls and not be published or submitted elsewhere. Papers are to use the standard LaTeX article style and the authblk style for affiliations; a sample of which is provided at www.ldta.info. Research and experience papers are limited to 15 pages, tool demonstration papers are limited to 10 pages, and short papers are limited to 6 pages. The final version of the accepted papers will, pending approval, be published in the ACM Digital Library and will also be made available during the workshop. Please submit your abstract and paper using EasyChair at http://www.easychair.org/conferences/?conf=ldta2011. The authors of each submission are required to give a presentation at LDTA 2011 and tool demonstration paper presentations are intended to include a significant live, interactive demonstration. The authors of the best papers will be invited to write a journal version of their paper which will be separately reviewed and, assuming acceptance, be published in journal form. As in past years this will be done in a special issue of the journal Science of Computer Programming (Elsevier Science). Invited Speaker --------------- Rinus Plasmeijer, Radboud University Nijmegen, The Netherlands Important Dates --------------- Abstract submission: Dec. 15, 2010 Full paper submission: Dec. 22, 2010 Author notification: Feb. 01, 2011 Camera-ready papers due: TBD LDTA Workshop: March 26-27, 2011 LDTA Tool Challenge ------------------- The aim of the LDTA Tool Challenge is to foster a better understanding, among tool developers and tool users, of relative strengths and weaknesses of different language processing tool techniques as well as different implementations and realizations of those techniques. Tool developers are invited to participate in the Tool Challenge and demonstrate their solution to the problems during a special session of LDTA 2011. The problems in the LDTA Tool Challenge Problem Set can be viewed as points in a two dimensional space: one dimension specifying language processing tasks and the second dimension specifying the set of languages to which these tasks are to be applied. Along the task dimension are several traditional language processing tasks such as parsing, pretty printing, semantic analysis, optimization, and code generation. The language dimension is comprised of a simple, but evolving, suite of imperative programming languages. These two dimensions form a problem space in which various techniques and implementations will find problems in which they excel and others in which they find some challenges; no single technique or tool is expected to be optimal for all problems. Thus, this is a challenge and not a competition; no winner is declared. The full description of the problem set can be found in the LDTA Tool Challenge Problem Set document on the LDTA web page at ( http://www.ldta.info ). The Tool Challenge is open to developers of all kinds of grammarware tools and techniques. To participate, tool developers must submit the following by March 5, 2011. Names of participants and the name of their tool or technique. Presentation title and abstract. The short abstract should specify on what aspects of the problem set the tool was applied, where it excelled and where no solution was offered and/or the solution was considered less than optimal. We expect these to be only a few paragraphs in length. This information is used for scheduling purposes only and is not used for evaluation; as all tool developers interested in participating are welcome and will be given an opportunity to present their solution at the workshop. Submission of this information indicates a commitment to attend LDTA and to participate in the workshop. This information will be listed in the program. Authors of submissions that appear to be outside of the scope of LDTA will be contacted to discuss the relevance of their work to the workshop. Of course tool developers who question whether their work falls with the scope of LDTA are encouraged to contact the PC chairs early on for clarification. After the workshop a joint paper will be written by participants and submitted to a journal, most likely Science of Computer Programming. It is separate from the proceedings of the workshop and any special journal issue for the workshop. Program Committee ----------------- Emilie Balland, INRIA, France Anya Helene Bagge, University of Bergen, Norway, Paulo Borba, Federal University of Pernambuco, Brazil John Boyland, University of Wisconsin, USA Claus Brabrand, IT University of Copenhagen, Denmark, (co-chair), brabrand(a)itu.dk Jim Cordy, Queen's University, Canada Kyung-Goo Doh, Hanyang University, Ansan, South Korea Giorgios Robert Economopoulos, University of Southampton, UK Laurie Hendren, McGill University, Canada Nigel Horspool, University of Victoria, Canada Roberto Ierusalimschy, Pontifícia Universidade Católica do Rio de Janeiro, Brazil Johan Jeuring, Utrecht University, The Netherlands Shane Markstrum, Bucknell University, USA Sukyoung Ryu, Korea Advanced Institute of Science and Technology, Korea Joao Saraiva, Universidade do Minho, Portugal Sylvain Schmitz, Ecole Normale Superieure de Cachan, France Sibylle Schupp, Hamburg University of Technology, Germany Eli Tilevich, Virginia Tech, USA Eric Van Wyk, University of Minnesota, USA (co-chair), evw(a)cs.umn.edu Eelco Visser, Delft University of Technology, The Netherlands Organizing Committee -------------------- Emilie Balland, INRIA, France Giorgios Robert Economopoulos, University of Southampton, UK

1 0

An Haskell implementation of a sweep line algorithm for the detection of segments intersection
by vince vegga 07 Dec '10

07 Dec '10

Hi, Here is my Haskell implementation of the Shamos and Hoey algorithm for detecting segments intersection in the plane: http://neonstorm242.blogspot.com/2010/12/sweep-line-algorithm-for-detection… I'm new to Haskell, so any useful comments will be appreciated. - Eran

3 2

ANN: hledger 0.13
by Simon Michael 07 Dec '10

07 Dec '10

I've released hledger 0.13, with readline editing and tab completion from Judah Jacobson, more ledger compatibility, a more robust and installable web interface, bugfixes, and a much-deliberated package split. Docs and mac and 64-bit linux binaries are at http://hledger.org , and of course you can cabal update and cabal install hledger, cabal install hledger-web and so on. I didn't manage to build new windows or linux 32-bit binaries today, but they'll appear when I do. Let it be noted that maintaining a non-trivial cross-platform haskell app is currently quite hard. Release notes: * move web, vty, chart commands into separate hledger-web, hledger- vty, hledger-chart packages. This both simplifies (no more build flags) and complicates (more room for dependency hassles), but I hope overall it will be easier and more scalable. * all packages but chart are now marked "beta", ie "not finished but suitable for everyday use" * parsing: ledger compatibility: support D default commodity directive * parsing: ledger compatibility: ignore metadata tags on transactions and postings * parsing: ledger compatibility: ignore cleared flags at the start of postings * parsing: ledger compatibility: ignore C commodity conversion directives * parsing: price precisions no longer affect commodities' display precisions * add: readline-style editing * add: tab-completion for account names * add: add the default commodity, if any, to commodity-less amounts (#26) * add: misc. commodity/precision/defaults-related bugfixes * chart: give a meaningful error message for empty journals * chart: update for current Chart lib (0.14) * web: support files now live in ./.hledger/web/ and will be auto- created at startup * web: page layout is more robust with wide content * web: allow editing of included files * web: handle multiple filter patterns correctly * web: allow single- or double-quoted filter patterns containing spaces * web: update for current yesod lib (0.6.*) * transaction balancing is now based on display precision (#23) * briefer, more informative usage error messages Stats: 91 days and 117 commits since last release, now at 5997 lines of code with 151 tests. hledger is at a point where real-world user and developer input is needed to focus it; participants welcome. Best, -Simon

2 2

Help defining a Typeable polymorphic-state monad transformer
by Brandon Simmons 07 Dec '10

07 Dec '10

Hi all, I gave myself until this evening to figure this out on my own, and time is up! Hopefully this makes for a good discussion, though the idea could be dumb. What I'm trying to do is define a state monad in which the passed state can change type during the computation. The only constraint is that the state types must always be of the Typeable class (see: http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Typea… ). The idea is that the new monad would be something like 'StateT s Maybe a', but where the 's' type is not fixed (indeed is hidden in an existential type) and where any programmer errors in the chaining of the polymorphic state will be caught in the Maybe type (or really the 'fail' implementation of any monad). Here is how I imagine a computation might look: computation :: TypeableState Maybe String computation = do (c:cs) <- getTS putTS (length cs) return ("c" ++ " was the first letter of the string passed as initial state.") So TypeableState is very similar to StateT, except that the state type is not present as a type argument. In the example above 'Maybe' is the monad that catches Typeable errors, and String is the return type of the computation. getTS and putTS would be get and put functions that constrain their arguments to the Typeable class. Here is what I have so far (at least this is my most recent uncommented attempt): > {-# LANGUAGE ExistentialQuantification #-} > module Main > where > > import Control.Monad.State > import Data.Typeable > > -- we might have restricted our 'm' to MonadPlus and used the explicit > -- 'mzero', but decided instead to use Monad, with 'fail'. This is > -- more appropriate since we won't be using 'mplus'. See 'liftMaybe'. > data TypeableState m a = forall s0 sN. (Typeable s0, Typeable sN)=> > TypeableState (s0 -> m (a,sN)) > > -- this is probably one of the more non-sensical attempts I've made at > -- this... but I'm not sure: > runTypeableState :: (Monad m, Typeable s0, Typeable sN)=> TypeableState m a -> s0 -> m (a,sN) > runTypeableState (TypeableState st) s0 = (liftMaybe $ cast s0) >>= st > > -- copied from Control.Monad.StateT > instance (Monad m) => Monad (TypeableState m) where > return a = TypeableState $ \s -> return (a, s) > m >>= k = TypeableState $ \s -> do > ~(a, s') <- runTypeableState m s > runTypeableState (k a) s' > fail str = TypeableState $ \_ -> fail str > > -- I imagine using this with 'cast' to thread the type in our monad > -- transformer > liftMaybe :: (Monad m)=> Maybe a -> m a > liftMaybe = maybe (fail "Monadic failure") return So is this even feasible? Or do I not grok what we can and can't do with the Typeable class? Any thoughts on this are appreciated. Sincerely, Brandon Simmons http://coder.bsimmons.name

2 2

Ed Lambda: Functional programming meetup in Edinburgh
by Ollie Saunders 07 Dec '10

07 Dec '10

It's that time again... When: Monday the 13th of December at 7:00pm Where: 12a The Outhouse, Broughton Street Lane, Edinburgh This month Chris Yocum will be talking about some functional fundamentals with his talk: The Loopless Loop: Perl and Ocaml as functional programming languages Phil Scott may also be talking, we're not sure yet. Also I'm not sure if I'm going to be able to make it but I've made provisions if I can't so the show will definitely be going on. As always there will be plenty of beer and friendly banter. I think everyone who comes enjoys themselves and learns something. If you missed out on last month then you can see my talk on Vimeo: <http://vimeo.com/17343181> (2nd part isn't there yet but is uploading right now).

1 0

Categorical description of systems with dependent types
by Petr Pudlak 07 Dec '10

07 Dec '10

Hi, recently, I was studying how cartesian closed categories can be used to describe typed functional languages. Types are objects and morphisms are functions from one type to another. Since I'm also interested in systems with dependent types, I wonder if there is a categorical description of such systems. The problem (as I see it) is that the codomain of a function depends on a value passed to the function. I'd happy if someone could give me some pointers to some papers or other literature. Thanks, Petr

6 10

need help with syntax...
by Daryoush Mehrtash 07 Dec '10

07 Dec '10

I am having hard time understanding the following code. The code is from Applicative Parser library: http://hackage.haskell.org/packages/archive/uu-parsinglib/2.5.5.2/doc/html/… instance (Show a, loc `IsLocationUpdatedBy` a) => Provides (Str a loc) (a -> Bool, String, a) a where splitState (p, msg, a) k (Str tts msgs pos del_ok) = let ins exp = (5, k a (Str tts (msgs ++ [Inserted (show a) pos exp]) pos False)) del exp = (5, splitState (p,msg, a) k (Str (tail tts) (msgs ++ [Deleted (show(head tts)) pos exp]) (advance pos (head tts)) True )) in case tts of (t:ts) -> if p t then show_symbol ("Accepting symbol: " ++ show t ++ " at position: " ++ show pos ++"\n") (Step 1 (k t (Str ts msgs (advance pos t) True))) else Fail [msg] (*ins:* if *del_ok* then *[del*] else []) [] -> Fail [msg] [*ins*] Specifically I am having hard time understanding how the "ins exp" and "del exp" in the "let" is related to "ins:" "del_ok", [del], [ins]. I don't understand how given the "let" expression the following expressions are expanded Fail [msg] (*ins:* if *del_ok* then *[del*] else []) and Fail [msg] [*ins*] Appreciate any help. Thanks Daryoush

2 1

Bifold: a simultaneous foldr and foldl
by Noah Easterly 06 Dec '10

06 Dec '10

Somebody suggested I post this here if I wanted feedback. So I was thinking about the ReverseState monad I saw mentioned on r/haskell a couple days ago, and playing around with the concept of information flowing two directions when I came up with this function: bifold :: (l -> a -> r -> (r,l)) -> (l,r) -> [a] -> (r,l) bifold _ (l,r) [] = (r,l) bifold f (l,r) (a:as) = (ra,las) where (ras,las) = bifold f (la,r) as (ra,la) = f l a ras (I'm sure someone else has come up with this before, so I'll just say I discovered it, not invented it). Basically, it's a simultaneous left and right fold, passing one value from the start of the list toward the end, and one from the end toward the start. It lets you do some interesting stuff, like filter based on positionor other left-dependent information: evenIndexed :: [a] -> [a] evenIndexed = fst . bifold alternate (0,[]) where alternate 0 x xs = (x:xs, 1) alternate 1 _ xs = (xs, 0) maximums :: (Ord a) => [a] -> [a] maximums [] = [] maximums (a:as) = a : (fst $ bifold (\m a l -> if a > m then (a:l,a) else (l,m)) (a,[]) as) As long as you don't examine the left-to-right value, it can still work on infinite lists: ghci> take 20 $ evenIndexed [0..] [0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38] Also, it can be used for corecursive data (or, at least, doubly-linked lists): data DList a = Start { first :: DList a } | Entry { value :: a, next :: DList a, prev :: DList a } | End { last :: DList a } deriving (Eq) ofList :: [a] -> (DList a, DList a) ofList as = (start,end) where start = Start first end = End last (first,last) = bifold mkEntry (start,end) as mkEntry p v n = let e = Entry v n p in (e,e) It's just been running around my head all night, so I thought I'd share.

2 5

Trying out GHC 7
by Andrew Coppin 06 Dec '10

06 Dec '10

OK, so the other day I decided to take GHC 7.0.1 for a spin. Suffice it to say, it definitely compiles stuff. So far, I've only tried running it in a Windows XP virtual machine with a single core, so I haven't been able to test what multicore performance is like. One thing that did interest me is the conflicting information about whether or not dynamic linking is supported on Windows. Half the User Guide claims that this /is/ supported, and the other half still contains statements that it is /not/ supported. So I thought I'd just go physically try it and see if it works. Well... it compiles stuff. Hello World goes from being 518KB to being a piffling 13KB. Which is nice. I almost didn't bother actually trying to /run/ the resulting binary... But when I did, I discovered that it immediately crashes, whining that it can't find the DLL it wants. So, out of the box, the Windows setup is broken. (Obviously the Windows section of the User Guide makes no mention of how DLLs are located; it only explains the situation for Linux and Mac OS. I especially liked the bit where it says that there are "three modes", and then proceeds to list only two...) In the interests of science, I wanted to see if I could make it run by just putting the necessary DLLs into the same folder as the binary. But first I had to /find/ them. I had expected to find a folder somewhere with all the DLLs in it... but no, the installer appears to have sprinkled them around the filesystem more or less at random. Some of them are in folders named for the package, some of them just sit in the root folder. After about 20 minutes of searching, I found the RTS DLL. Running the program, it now instantly crashes because of a /different/ DLL. This one didn't take quite so long to find (now that I know roughly where to look). I fixed that, and now the binary crashes with yet another missing DLL. And so on and so forth. In the end, Hello World required 5 DLLs. Better still, together these totalled 8MB of data. (!) So the distribution package is now about 16x bigger than with static linking. Oh joy. Clearly if you just want to distribute one executable binary, you're going to use static linking. (E.g., darcs.exe will hopefully remain statically linked.) But I suppose if I had a whole heap of Haskell programs then the extra complexity of delivering half a dozen DLLs might may off in terms of space reductions. And of course, on /my/ development box, I don't need a zillion redundant copies of the RTS code, etc. (Or at least, I won't if I can figure out how to make the programs able to actually /find/ the necessary DLLs...) Actually, of all the DLLs, only "base" is actually large - it's approximately 6MB on its own. GHC-Prim is 0.5MB, and the others are all relatively tiny. It feels slightly irritating that I need to inclide the FFI DLL when I'm not doing and FFI - but of course, the entire Haskell I/O subsystem /is/ doing FFI. Similarly, I'm not using arbitrary-precision integers, but various I/O operations return file sizes as Integer, so GMP must also be included. Neither of these things are actually especially large. It's rather confusing that the User Guide is out of date in so many places. (And not just regarding dynamic linking on Windows. For example, one section claims that "+RTS -f" will tell you what options are supported, but that actually yields "unknown RTS opion: -f". It seems that "-?" is the correct option name.) If I can get a suitable Linux VM going, I might have a go at contributing some updates. Just for completeness, I tried asking for dynamic linking with an older version of GHC (6.10, IIRC) - one that supports it on Linux but not Windows. I was expecting to get either "dynamic linking is not supported on this platform", or at worst "unknown option -dynamic". In fact, what I got was "gcc: cannot find file Main.dyn_hi". Oh, that's graceful failure then. >_< I did also briefly see if the LLVM backend would work under Windows. I wasn't entirely sure if LLVM comes with the installer binary or you need to get it seperately. (You might say "obviously it's seperate", but the installer already contains the entire GCC system, for example.) Attempting to use this resulted in a summary error message ("cannot run: opt") which doesn't make it especially clear that the problem is that LLVM isn't installed. Perhaps there's no better way of detecting this condition, I don't know, but something more illuminating would be nice. I briefly had a look at how to install LLVM, but it appears that you have to build it from source. This is not my idea of a fun time, so given the minimal speed difference, I just won't bother. I haven't had time to play with any of the other new good stuff in GHC 7. (The multicore performance, the new GC stuff, etc.)

4 4