- Haskell-Cafe - Haskell.org

Horner's Rule, foldl, and direct recursion
by R J 11 Mar '09

11 Mar '09

Given a list of decimal digits represented by Integers between 0 and 9--for example, the list [1,2,3, 4]--with the high-order digit at the left, the list can be converted to a decimal integer n using the following formula, an instance of Horner's rule: n = 10 * 10 * 10 * 1 + 10 * 10 * 2 + 10 * 3 + 4 = 10 * (10 * 10 * 1 + 10 * 2 + 3) + 4 = 10 * (10 *(10 * 1 + 2) + 3) + 4 In Haskell, the foldl function neatly captures this pattern: horner :: [Integer] -> Integer horner = myFoldl timesPlus 0 where timesPlus x y = 10 * x + y What is the direct recursive calculation of this function without using the call to foldl? In other words, what's the second equation of: horner2 :: [Integer] -> Integer horner2 [] = 0 horner2 (x : xs) = ? Given that we've already got the definition using foldl, it ought to be easy to express the second equation, but it's eluding me. Thanks. _________________________________________________________________ Windows Live™ Groups: Create an online spot for your favorite groups to meet. http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009

2 1

TASE 2009 - CALL FOR POSTER PRESENTATIONS
by CRACIUN F. 10 Mar '09

10 Mar '09

TASE 2009 - CALL FOR POSTER PRESENTATIONS ****************************************** * 3rd IEEE International Symposium on * Theoretical Aspects of Software Engineering * (TASE 2009) * 29-31 July 2009, Tianjin, China * http://www.dur.ac.uk/ieee.tase2009 * * For more information email: IEEE.TASE2009(a)durham.ac.uk ********************************************************** TASE 2009 will include a poster session during the conference. The session aims to give students and researchers an opportunity to present their research to the community, and to get responses from other researchers. SCOPE: Poster presentations are sought in all theoretical aspects of software engineering, including (but not limited to): * Requirements Engineering * Specification and Verification * Program Analysis * Software Testing * Model-Driven Engineering * Software Architectures and Design * Aspect and Object Orientation * Embedded and Real-Time Systems * Software Processes and Workflows * Component-Based Software Engineering * Software Safety, Security and Reliability * Reverse Engineering and Software Maintenance * Service-Oriented Computing * Semantic Web and Web Services * Type System and Theory * Program Logics and Calculus * Dependable Concurrency * Software Model Checking SUBMISSION PROCESS: A Poster proposal consists of: - a 50 word or less short abstract that summarizes the content of the poster - a set of keywords describing the technical area of the work - a two-page extended abstract, suitable for inclusion in the TASE 2009 conference proceedings. All abstracts must adhere to the two-column IEEE format. All Poster proposals are to be submitted by email to IEEE.TASE2009(a)durham.ac.uk. The file containing the two-page extended abstract must be in .pdf or .ps format. Upon acceptance, at least one of the authors must register with the TASE2009 conference in order to have their extended abstract included in the conference proceedings. Once registered, a bulletin board space of A1 paper size (594 mm wide and 841 mm high) will be provided for each presentation. In addition to the camera-ready version of the extended abstract, the authors are also requested to submit their poster of A1 paper size (594 mm wide and 841 mm high) for backup. An A1 poster sample template is available at http://www.dur.ac.uk/ieee.tase2009/poster.a1.ppt for authors to download. The authors can prepare 8 individual slides, save them in .jpg format and then place them on the above A1 sample. The Poster presenter will need to print out their Poster in advance and bring it to the conference for the Poster session. POSTER CONTENT: A small selection committee led by the Poster Chair will evaluate the poster proposals based on their contributions and on how effectively they communicate those contributions. All posters should include the following information: - The purpose and goals of the work. - Any background and motivation information needed to understand the work. - A summary of the contribution and/or results, in sufficient detail for a viewer to understand the work and/or results; especially key details, results and contributions, or the anticipated contributions if the work is at an early stage. - The relationship to other related efforts, where appropriate. - Where to find additional information. This should include (but is not restricted to): a web site where viewers can go to find additional information about the work, how to contact the authors (including email addresses), citations for any papers, books, or other materials that provide additional information. POSTER COMPETITION: A poster competition will be organised during the poster session. A panel of experts will be formed as referees for the competition. Awards will be given to the winners of the competition. IMPORTANT DATES: Poster proposals submission: April 22, 2009 Acceptance/rejection notification: May 6, 2009 Camera-ready version and Poster due: May 13, 2009 TASE 2009 Conference: July 29-31, 2009 CONTACT: For questions or requests, please contact the TASE 2009 poster chair, Florin Craciun (IEEE.TASE2009(a)durham.ac.uk) Please mention "poster session" in the subject of your email.

1 0

Haskell Logo Voting will start soon!
by Eelco Lempsink 10 Mar '09

10 Mar '09

Hi there! It's been quiet for a while around the 'new logo' competition, but here is how it is going to work: The list with options can be found here (for now): http://community.haskell.org/~eelco/poll.html Notice that some (very) similar logos are grouped as one option (thanks to Ian Lynagh) All submissions compete, so that still makes more than a 100 options! The voting system we'll use is the Condorcet Internet Voting System (http://www.cs.cornell.edu/andru/civs.html ). The poll won't be public, but every subscriber to Haskell-Cafe will get a (private) voting ballot by email. The poll will (probably) start March 16 and run for about a week (don't worry, there will be a strict deadline communicated). When the poll is over, the results will be viewable by everybody. The CIVS allows easy grouping and ordering, so the task of ordering 100 options should be doable within 5-10 minutes. If you're in a hurry you can do it a lot faster, just pick your favorite and put it first. If you want to learn more about condorcet voting, the CIVS site and Wikipedia are your friends. I'll supervise the poll and make sure it's started, stopped and all Haskell-Cafe subscribers get a ballot (Simon Marlow provided the email addresses). Since I'm going on a (probably internet deprived) holiday for a week _and_ to make sure I haven't overlooked anything, I'm announcing it now but won't start the poll till March 16. Of course, I'd love to hear about anything that I missed and/or that might influence the voting process in a significant way. (There are probably some people subscribed with multiple addresses, but I'll be using the subscriber list from yesterday, so signing up now with lots of addresses won't get you more ballots ;) -- Regards, Eelco Lempsink

18 28

digest and zlib on Windows
by Tillmann Rendel 10 Mar '09

10 Mar '09

Hi Eugene, I run into some troubles with the digest package on Windows. On unix, digest binds to zlib, but on Windows, the relevant c files from zlib are included. However, in digest-0.0.0.4, two header files were missing which were needed for compilation on my machine. With these header files added (from digits-0.0.0.3), digest compiles fine. Unfortunately, the zlib package has the same approach of including c files from zlib on Windows. That means that I could not use both zlib and digest together, because they contained conflicting symbols. Unfortunately, pandoc requires both zlib and digest. I solved the problem by removing the cbits from digest, and instead require the zlib on Windows. In other words, I deleted the cbits subdirectory, and changed the last few lines of digest.cabal from if !os(windows) extra-libraries: z else c-sources: cbits/adler32.c cbits/crc32.c include-dirs: cbits install-includes: zlib.h to the following: if !os(windows) extra-libraries: z else build-depends: zlib With this change, everything seems to work fine for me. Tillmann

1 0

ANNOUNCE: torch-0.1
by Yusaku Hashimoto 10 Mar '09

10 Mar '09

Hello, I have wrote and uploaded my unit test library (or framework) torch-0.1 on Hackage. With torch, We can write simple unit test and run like this: > import Test.Torch > > main = run $ do > ok (odd 1) "assertion" > is 42 (7*6) "equality assertion" > isBottom (error undefined) "check whether value is bottom" > ans <- liftIO (putStr "\n5 + 7 = " >> readLn) > is ans 12 "sanity check :)" Despite QuickCheck and HUnit, Why I wrote unit test library now? There is two reasons. 1. QuickCheck is not all-round QuickCheck is awesome. But I often can't write Property when I want to test things, like not pure function. Even for pure function, I can't write Property by thinking _laws_ behind that with probability about 0.5. When I can't write Property, I want to write unit test using HUnit. But for me, HUnit does not fit to my hands. Because it is annoying that writing list of test literally in source code and confusing operators (I still can't remember distinction between (@=?) and (@?=)) This means when I read test written in HUnit, I can't read this without Documentation. And I got an idea for expressing structure of tests from a blog post about Monoid and Writer Monad. 2. Try to realize an idea that Writer monad can be treated as Monoid (and list of Test is Monoid) I read sigfpe's great blog post (http://blog.sigfpe.com/2009/01/ haskell-monoids-and-their-uses.html) and hit upon the idea that considering Writer as Monoid, list of tests can be expressed with Monad. And I tried to realize it, and want to sympathize this idea with Haskellers. I think almost complete realizing this idea in the library. Those is why I wrote this library. And It is my first package on Hackage, I apologize for any wrong about packaging. I hope you'll enjoy this! Thanks, nonowarn

1 1

ANN: sparsebit 0.5 - Sparse Bitmaps for Pattern Match Coverage
by Ahn, Ki Yung 10 Mar '09

10 Mar '09

sparsebit - Sparse Bitmaps for Pattern Match Coverage http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sparsebit This library packages the functional peal paper 'Sparse Bitmaps for Pattern Match Coverage' submitted to ICFP 2009 by Ki Yung Ahn and Tim Sheard. You can look up the tutorial-like paper and the talk slides, which are availabel at: http://kyagrd.dyndns.org/wiki/SparseBitmapsForPatternMatchCoverage Abstract: Pattern matching coverage over Algebraic Data Types(ADTs) has most often been studied in the context of pattern compilation algorithms. However, it is worth considering the pattern matching coverage problem in isolation, since general solutions will be independent of the specifics of any implementation or language. We define an intuitive and mathematically well-established bit masking semantics for pattern match coverage. We design and implement a sparse bitmap data structure, which realizes this semantics in a compact and flexible manner. This bitmap data structure supports computing coverage solutions of large programs incrementally from coverage solutions of sub-programs. It can also be used as a common data representation for pattern coverage shared between different tools (e.g., compilers, linting tools, software analysis tools) that need pattern match coverage information. Additional source files Type.hs and TestType.hs packaged with this library provides the examples and QuickCheck extracted from the paper to demonstrate how to use this library. ==================================================================== Some additional notes: Personally, I am very happy to upload my first project on Hackage. If you are looking for simple and elegant way of describing pattern match coverage or testing exhaustiveness of pattern matching, we hope this may give you a better insight. This is a reference implementation, but I think it is still usable to some extent. One might want to define monadic version of the library functions and operators since the type representation in the program analysis tools might be monadic for implementation reasons (easy to generate fresh type variables) and performance reasons (to exploit sharing while unification of type variables). And in such cases, more optimized implementation of tensor product may be possible as well. And there are some other issues discussed in the paper as well. I was not able to make the haddock documentation appear in Hackage, although I have no problem generating documentation using "cabal haddock" locally. It would be nice if there is a way to see some diagnose of warning or error messages why haddock failed on Hackage. -- Ahn, Ki Yung

2 1

Re: [Haskell-cafe] Sugestion for a Haskell mascot
by Gregory Michael Travis 10 Mar '09

10 Mar '09

Maur??cio <briqueabraque(a)yahoo.com> sed: > Hi, > > Here in Brazil we have a forest animal we name 'preguiça' -- literally, > lazyness. What better mascot we could have for Haskell? It lives (and > sleeps) in trees, and if you see the main picture in wikipedia articles > you can easily imagine the tree branch beeing replaced by a lambda: > > http://en.wikipedia.org/wiki/Sloth > > http://pt.wikipedia.org/wiki/Bicho-pregui%C3%A7a Perfect!

1 0

Re: [Haskell] Google Summer of Code 2009
by Johan Tibell 10 Mar '09

10 Mar '09

On Tue, Feb 10, 2009 at 3:26 PM, Malcolm Wallace <Malcolm.Wallace(a)cs.york.ac.uk> wrote: > Gentle Haskellers, > > The Google Summer of Code will be running again this year. Once again, > haskell.org has the opportunity to bid to become a mentoring > organisation. (Although, as always, there is no guarantee of > acceptance.) > > If you have ideas for student projects that you think would benefit the > Haskell community, now is the time to start discussing them on mailing > lists of your choice. We especially encourage students to communicate > with the wider community: if you keep your ideas private, you have a > much worse chance of acceptance than if you develop ideas in > collaboration with those who will be your "customers", end-users, or > fellow-developers. This is the open-source world! > > The timeline is that Haskell.org will apply for GSoC membership between > 9-13 March, and if we are successful, students can submit applications > between 23 March - 3 April. Google is now accepting applications: http://google-opensource.blogspot.com/2009/03/google-summer-of-code-applica…

2 2

Mystified by Cabal
by Colin Paul Adams 10 Mar '09

10 Mar '09

I have just attempted Cabal-izing my program (splitting it into a library and main program as well), and I'm mystified by some problems I am having. First, when I try to build the library I get: [colin@susannah game-tree]$ runhaskell Setup build Preprocessing library game-tree-1.0.0.0... Building game-tree-1.0.0.0... Data/Tree/Game/Negascout.hs:31:0: Unrecognised pragma [1 of 2] Compiling Data.Tree.Game.Tree ( Data/Tree/Game/Tree.hs, dist/build/Data/Tree/Game/Tree.o ) Data/Tree/Game/Tree.hs:1:0: Failed to load interface for `Prelude': it is a member of package base-3.0.3.0, which is hidden That mystifies me. Googling, it appears to be a common error in the past, but none of the reasons apparently apply to my case. Incidentally, Tree.hs imports nothing. It just looks like: -- | Nodes in game trees -- Copyright 2009 Colin Adams -- -- This file is part of game-tree. -- -- Game-tree is free software: you can redistribute it and/or modify -- it under the terms of the GNU General Public License as published by -- the Free Software Foundation, either version 3 of the License, or -- (at your option) any later version. -- Game-tree is distributed in the hope that it will be useful, -- but WITHOUT ANY WARRANTY; without even the implied warranty of -- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -- GNU General Public License for more details. -- You should have received a copy of the GNU General Public License -- along with game-tree. If not, see <http://www.gnu.org/licenses/>. module Data.Tree.Game.Tree where -- | Nodes in a game search tree class Tree a where -- | Is this a game-terminating node (e.g. checkmate)? is_terminal :: a -> Bool -- | Heuristic value of node node_value :: a -> Int -- | Child nodes in the game tree (positions more deeply searched) children :: a -> [a] So I couldn't build my program using runhaskell, as I couldn't install the library. Instead, i tried ghc --make instead with the -idir option. It looks in the right place, but still doesn't recognise the module: Chasing modules from: *Chu-shogi.hs Generator.hs:27:7: Could not find module `Data.Tree.Game.Tree': locations searched: Data/Tree/Game/Tree.hs Data/Tree/Game/Tree.lhs dirs=../game-tree/Data/Tree/Game/Tree.hs dirs=../game-tree/Data/Tree/Game/Tree.lhs What am I doing wrong? Perhaps Cabal should be named Caballa instead. -- Colin Adams Preston Lancashire

7 12

ANN: Future 1.1.0 concurrency library
by ChrisK 10 Mar '09

10 Mar '09

Hello, As a side effect of the discussion of the new C++ future/promise features at http://lambda-the-ultimate.org/node/3221 I have implemented a Haskell package called "future" at http://hackage.haskell.org/cgi-bin/hackage-scripts/package/future This ought to do what C++ standard futures/promises do, plus a bit more. The main operation is > forkPromise :: IO a -> IO (Promise a) This sets the "IO a" operation running in a fresh thread. The eventual result can be accessed in many ways (non-blocking, blocking, blocking with timeout). > let one :: Int; one = 1 > p <- forkPromise (return (one+one)) > x <- get > y <- wait x is an Int with value 2. y is an (Either SomeException Int) with value (Right 2). The useful thing about futures, as opposed to various IVar packages, is handling the case where the forked operation ends with an exception. The exception becomes the return value of the promise. The "get" operation rethrows it, the "wait" operation returns it as (Left ...). There is also an "abort" command to kill a promise. The dead promise may then have an exceptions as its value. The "plus a bit more" than C++ is the nonblocking "addTodo" feature. This takes a continuation function from the "Either SomeException a" to an IO operation. These continuation functions get queued and they are run immediately after the the forked operation completes. Once completed any new "addTodo" continuations run immediately. These continuations allow you to race a list of action and take the first one done, or to collect the answers as they complete into a Chan. Both of those options are demonstrated in Future.hs as racePromises and forkPromises. It should be safe to use "unsafePerformIO . get" or "unsafePeformIO . wait" to get lazy access to the result, which is itself immutable once set. Cheers, Chris

3 4