April 2008 - Haskell-Cafe

searching via zipper over a tree
by Graham Fawcett 25 Apr '08

25 Apr '08

Hi folks, I'm studying zippers (and by extension, the State monad), and have written a function for finding the first node-location in a 'zippered' tree that satisfies a predicate: http://paste.lisp.org/display/59636 (The code uses Krasimir Angelov's Data.Tree.Zipper.) My code works, but I suspect that I'm working too hard. I would appreciate any comments! Regards, Graham

1 1

Fw: I have a problem
by cetin tozkoparan 24 Apr '08

24 Apr '08

I have a problem which i can'tsolve. Is there any one who has an idea? Two lists is sent as parameter to a function. If second list contains first list, return true, else return false. This comparision must be in order of first list. You can look at examples. function type as follows: sublist:: [a] -> [a] -> Bool examples: For instance [2,4,5]list is sub list of [3,7,2,4,5,9] list but not of[3,7,4,2,5,9] list. sublist [2,8][1,5,6,2,4,7,8,2] False sublist [1,2,3][0,1,2,3,4,5,6] True sublist [5,4] [1,4,5,7,8,3,5,4] True sublist [1,2,4,3,4,5,7,8,9,5] [8,2,3,1,2,4,3,4,5,7,8,9,5,1,6,2] True ____________________________________________________________________________________ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ

3 2

mapM vs mapM_ performance
by Ben 24 Apr '08

24 Apr '08

Hello Haskellers, I'm running ghc 6.8.2 on vista 64. Consider the following program, which is compiled with -02 -prof -auto-all: module Main where import System.IO (openFile, IOMode(..), hPutStr) testlst = let ls = [(i, [(j, (fromIntegral j)::Float) | j <- [1..5]::[Int]]) | i <- [1..500000]::[Int]] in ls main2 = do h <- openFile "bardump" WriteMode mapM_ ((hPutStr h) . show) testlst main = do h <- openFile "bardump2" WriteMode mapM ((hPutStr h) . show) testlst return () main and main2 are different in only that mapM_ versus mapM_ are used. But the mapM version runs about 20x slower! I'm running with +RTS -p -hc -RTS and I see that the amount of memory allocated is about the same, and I think the resident memory is about the same too. But the mapM_ version runs in about 8.7 seconds, and the mapM version takes 167 seconds. You may ask, why use mapM if you're discarding the values? Unfortunately in my real app I need the values, which are more interesting than IO (). ? Take care, Ben

2 1

Re: [Haskell] How to define tail function for Even/Odd GADT lists?
by David Roundy 24 Apr '08

24 Apr '08

2008/4/23 Martijn Schrage <martijn(a)cs.uu.nl>: > It depends a bit on what you want to use these lists for, but the following > encoding works for your examples and doesn't need the type class. > > data E > data O > > type Even = (E,O) > type Odd = (O,E) That's a nice little trick! I like how you achieve type signatures relating two distinct types just by sticking them in a tuple. :) David

3 3

Hackage being too strict?
by John Goerzen 24 Apr '08

24 Apr '08

When I went to make my upload of MissingH 1.0.1, Hackage rejected it, saying: Instead of 'ghc-options: -XPatternSignatures' use 'extensions: PatternSignatures' It hadn't rejected MissingH 1.0.0, even though it had the same thing. Now, my .cabal file has this: -- Hack because ghc-6.6 and the Cabal the comes with ghc-6.8.1 -- does not understand the PatternSignatures extension. -- The Cabal that comes with ghc-6.8.2 does understand it, so -- this hack can be dropped if we require Cabal-Version: >=1.2.3 If impl(ghc >= 6.8) GHC-Options: -XPatternSignatures which was contributed by Duncan Coutts. It seems arbitrary that Hackage would suddenly reject this valid usage. Thoughts?

7 15

compressed pointers?
by Ketil Malde 24 Apr '08

24 Apr '08

One of the downsides of a 64-bit environment is the increased size of pointers. This means that the cost of a String increases from something like 12 bytes per char to something like 24. I notice BEA uses something called "compressed pointers" to get the 64-bit (more registers, etc) benefits without paying the (cache-thrashing) cost. http://e-docs.bea.com/jrockit/releases/5026x/relnotes/relnotes.html#wp10797… Something for GHC? -k -- If I haven't seen further, it is by standing in the footprints of giants

6 6

zipper for rose trees? (Data.Tree)
by Graham Fawcett 24 Apr '08

24 Apr '08

Hi folks, Is there a common zipper implementation for the "Tree a" datatype, defined in Data.Tree? The wiki gives examples for binary trees and B-trees, but not for these. Thanks, Graham

2 2

Re: [Haskell] Matrix multiplication
by Sebastian Sylvan 24 Apr '08

24 Apr '08

On Wed, Apr 23, 2008 at 5:01 PM, Tillmann Vogt <Tillmann.Vogt(a)rwth-aachen.de> wrote: > 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? > > Yes, in the C version you use unboxed arrays, in the Haskell version you use a linked list of linked lists. Naturally the latter will take up more space, require more work to index, and will thrash the cache quite a bit.

3 2

PLMMS - Last call for papers
by Jacques Carette 24 Apr '08

24 Apr '08

LAST CALL FOR PAPERS Second Workshop on Programming Languages for Mechanized Mathematics (PLMMS 2008) http://events.cs.bham.ac.uk/cicm08/workshops/plmms/ As part of CICM / Calculemus 2008 Birmingham, UK, 28-29 July 2008 This workshop is focused on the intersection of programming languages (PL) and mechanized mathematics systems (MMS). The latter category subsumes present-day computer algebra systems (CAS), interactive proof assistants (PA), and automated theorem provers (ATP), all heading towards fully integrated mechanized mathematical assistants that are expected to emerge eventually (cf. the objective of Calculemus). The two subjects of PL and MMS meet in the following topics, which are of particular interest to this workshop: * Dedicated input languages for MMS: covers all aspects of languages intended for the user to deploy or extend the system, both algorithmic and declarative ones. Typical examples are tactic definition languages such as Ltac in Coq, mathematical proof languages as in Mizar or Isar, or specialized programming languages built into CA systems. Of particular interest are the semantics of those languages, especially when current ones are untyped. * Mathematical modeling languages used for programming: covers the relation of logical descriptions vs. algorithmic content. For instance the logic of ACL2 extends a version of Lisp, that of Coq is close to Haskell, and some portions of HOL are similar to ML and Haskell, while Maple tries to do both simultaneously. Such mathematical languages offer rich specification capabilities, which are rarely available in regular programming languages. How can programming benefit from mathematical concepts, without limiting mathematics to the computational worldview? * Programming languages with mathematical specifications: covers advanced "mathematical" concepts in programming languages that improve the expressive power of functional specifications, type systems, module systems etc. Programming languages with dependent types are of particular interest here, as is intentionality vs extensionality. * Language elements for program verification: covers specific means built into a language to facilitate correctness proofs using MMS. For example, logical annotations within programs may be turned into verification conditions to be solved in a proof assistant eventually. How need MMS and PL to be improved to make this work conveniently and in a mathematically appealing way? These issues have a very colorful history. Many PL innovations first appeared in either CA or proof systems first, before migrating into more mainstream programming languages. Some examples include type inference, dependent types, generics, term-rewriting, first-class types, first-class expressions, first-class modules, code extraction etc. However, such innovations were never aggressively pursued by builders of MMS, but often reconstructed by programming language researchers. This workshop is an opportunity to present the latest innovations in MMS design that may be relevant to future programming languages, or conversely novel PL principles that improve upon implementation and deployment of MMS. We also want to critically examine what has worked, and what has not. Why are all the languages of mainstream CA systems untyped? Why are the (strongly typed) proof assistants so much harder to use than a typical CAS? What forms of polymorphism exist in mathematics? What forms of dependent types may be used in mathematical modeling? How can MMS regain the upper hand on issues of "genericity" and "modularity"? What are the biggest barriers to using a more mainstream language as a host language for a CAS or PA/ATP? Invited Talk ------------ Conor McBride (Alta Systems, Northern Ireland) will give an invited talk "Theorem Proving for the Lazy Programmer" Submission ---------- Submission works through EasyChair http://www.easychair.org/conferences/?conf=plmms2008 Two kinds of papers will be considered: * Full research papers may be up to 12 pages long. Authors of accepted papers are expected to present their work on the workshop in a regular talk. * Position papers may be up to 4 pages long. The workshop presentation of accepted position papers consists of two parts: a stimulating statement of certain issues or challenges by the author, followed by a discussion in the plenum. Papers should use the usual ENTCS style http://www.entcs.org/prelim.html (11 point version), and will be reviewed by the program committee. Informal workshop proceedings will be circulated as a technical report. Moreover there will be post-workshop proceedings of improved research papers, or position papers that have been completed into full papers, to appear in a special issue of the Journal of Automated Reasoning. There will be a separate submission and review phase for this, where papers from both PLMMS 2007 and 2008 will be considered. Programme Committee ------------------- Jacques Carette (Co-Chair) (McMaster University, Canada) John Harrison (Intel Corporation, USA) Hugo Herbelin (INRIA, Ecole polytechnique, France) James McKinna (Radboud University Nijmegen, Netherlands) Ulf Norell (Chalmers University, Sweden) Bill Page Christophe Raffalli (Universite de Savoie, France) Josef Urban (Charles University, Czech Republic) Stephen Watt (ORCCA, University of Western Ontario, Canada) Makarius Wenzel (Co-Chair) (Technische Universitaet Muenchen, Germany) Freek Wiedijk (Radboud University Nijmegen, Netherlands) Important Dates --------------- * Submission deadline - 5 May 2008 * Notification of acceptance - 6 June 2008 * Final version - 7 July 2008 (approximately) * Workshop - 28-29 July 2008

1 0

announcing franchise 0.0
by David Roundy 24 Apr '08

24 Apr '08

I'm pleased to announce the existence (not release, properly) of franchise, a new configuration/build system for Haskell programs and packages. Franchise ========= Franchise is a configuration and build system for Haskell projects. The configure system employed in franchise is designed to be easily forward and backward compatible, meaning that you shouldn't need to change your Setup.hs file in order to compile with a new version of ghc, and if you *do* need to make a change in your Setup.hs file, it shouldn't force users who have an older version of franchise and/or ghc to upgrade either their compiler or their copy of franchise. The latter goal is really only going to be realized if and when a stable version of franchise is released... as it is currently is something of a pre-alpha state (but useable, for instance, for compiling darcs). One goal of franchise is to not require developers to provide redundant information. For instance, you've already listed all the modules you use, and ghc already knows which modules are present in which packages, so there's in general no need for you to list the packages that you require, much less their versions. This enhances both forwards and backwards compatibility, and just plain makes your life easier. If a particular module is provided by more than one package, you may need to disambiguate, but that's not the common case. Perhaps also worth mentioning is that franchise supports parallel builds similar to make -j. Currently the number of simultaneous builds is fixed at four. Franchise does not, however, compute an optimized parallel build order, with the result that on the darcs repository a franchise build is a few percent slower than make -j4. Franchise is currently ghc-specific and won't run on Windows, but patches to extend either of these limitations would be welcome. It also currently won't work when any flags contain space characters (e.g. with --prefix="/home/user/My stuff"), but the fix for lack of space support is the same as the fix for Windows support, so far as I can tell. The package name "franchise" stands for "Fun, relaxing and calming Haskell into Saturday evening." It is also something of an antonym of "cabal," since "franchise" means the right to vote. Which also fits in with the concept of allowing the code to decide on its own dependencies. Franchise is made up of some pretty ugly code, with a small amount of pretty beautiful code. But it was all code that was fun and relaxing to write. It you want to have argumentative, stressful conversations, please don't do so on the subject of fun, relaxing and calming code. Note: franchise is almost entirely undocumented. It does only export a couple of dozen functions, but still might be hard to learn to use. This is because writing documentation is not as fun, relaxing or calming as writing Haskell. Also, franchise is not yet at the stage where it's likely to be useful to you without any features added, unless you've got a very simple project, in which case you should be able to pretty easily copy and modify an existing franchise Setup.hs file. To get franchise, run darcs get http://darcs.net/repos/franchise (note that this will require darcs 2.0.0) To build and install franchise, simply execute runghc Setup.hs install --user --prefix=$HOME if you don't want to actually install it, just run runghc Setup.hs build I think that's all (and obviously, in no particular order). I hope you enjoy franchise, or if you don't enjoy franchise, I hope you don't tell me about it. David Roundy P.S. A franchise build file for darcs is included below. This is a work-in-progress. It doesn't build the documentation, doesn't allow the user to configure on the command-line which packages they want to use (e.g. bytestring/curl/libwww) and doesn't build the Workaround.hs module which codes replacements for missing or broken library functions. But it *is* able to build darcs, and if these features are added, it will be able to replace darcs' configure and build system without loss of features or compatibility. #!/usr/bin/runhaskell import Distribution.Franchise configure = do findPackagesFor "src/darcs.lhs" addEnv "GHC_FLAGS" "-DPACKAGE_VERSION=\"2.0.0\"" addEnv "GHC_FLAGS" "-O2 -Wall -Werror" addEnv "CFLAGS" "-DPACKAGE_VERSION=\"2.0.0\"" -- look for libz checkLib "z" "zlib.h" "gzopen(\"temp\",\"w\")" -- look for libwww do systemOut "libwww-config" ["--cflags"] >>= addEnv "CFLAGS" systemOut "libwww-config" ["--libs"] >>= addEnv "LDFLAGS" addEnv "GHC_FLAGS" "-DHAVE_LIBWWW" putStrLn "Found libwww" `catch` \_ -> putStrLn "Libwww isn't present!" -- look for libcurl do systemOut "curl-config" ["--cflags"] >>= addEnv "GHC_FLAGS" systemOut "curl-config" ["--cflags"] >>= addEnv "CFLAGS" systemOut "curl-config" ["--libs"] >>= addEnv "LDFLAGS" addEnv "GHC_FLAGS" "-DHAVE_CURL" putStrLn "Found libcurl" `catch` \_ -> putStrLn "Libcurl isn't present!" -- look for libcurses do checkLib "curses" "term.h" "tgetnum(\"hello world\")" checkLib "curses" "curses.h" "" addEnv "GHC_FLAGS" "-DHAVE_CURSES" `catch` \_ -> putStrLn "Couldn't find libcurses." -- look for http packages do requireModule "Network.HTTP ()" addEnv "GHC_FLAGS" "-DHAVE_HTTP" `catch` \_ -> putStrLn "Couldn't find http package." findPackagesFor "src/darcs.lhs" main = build configure $ executable "darcs" "src/darcs.lhs" ["src/c_compat.c", "src/maybe_relink.c", "src/atomic_create.c", "src/fpstring.c", "src/umask.c", "src/hslibwww.c", "src/Crypt/sha2.c", "src/hscurl.c"] -- David Roundy Department of Physics Oregon State University

3 3