April 2007 - Haskell-Cafe

Obscure instances for Obscure types
by Neil Mitchell 26 Apr '07

26 Apr '07

Hi I currently maintain two libraries, TagSoup which defines the Tag data type, and BinaryDefer, which defines the BinaryDefer class. If I wanted to include an instance for BinaryDefer Tag, where would I put it? Putting it in either library introduces an artificial dependency on the other. Putting it in a separate libary makes the library about 4 lines long and is just annoying. Putting it in the individual application(s) is exactly what libraries were designed to avoid. Is there a solution? Thanks Neil

4 4

ANN: London Haskell User Group
by Neil Bartlett 26 Apr '07

26 Apr '07

I am delighted to announce the first meeting of the London Haskell User Group on Wednesday 23rd May from 6:30PM. The meeting will be held at City University's main campus in central London, and Simon Peyton Jones will be coming to give a talk. Please see the announcement on the web page for more details and to register: http://www.londonhug.net/2007/04/26/announcement-first-meeting-of-the- london-haskell-user-group/ Many thanks to Simon, and to Ross Paterson at City University for organising the room. Regards, Neil

1 0

Stack overflow with my Trie implementation
by Pete Kazmier 26 Apr '07

26 Apr '07

I've modified my Norvig spelling corrector to use a trie instead of Data.Map in the hopes of improving performance. Plus, this is fun and a great learning exercise for me. Unfortunately, when I load my trie with a large amount of data, I get a stack overflow. It's unclear to me why this is happening. I specifically use foldl' to avoid this situation when building my trie. Could someone shed some light on the situation for me? Here is the code: > module Main where > > import Data.List (foldl') > import Data.Maybe (maybe, fromMaybe) > import Prelude hiding (lookup) > import qualified Data.Map as M > > data Trie a = T (Maybe a) (M.Map Char (Trie a)) deriving (Show) > > main = do > -- big.txt is a large file of words: http://www.norvig.com/big.txt > c <- readFile "big.txt" > let freqTrie = foldl' incWordCount empty (words c) > print $ lookup "evening" freqTrie > where > incWordCount m w = insertWith (+) w 1 m > > empty :: Trie a > empty = T Nothing M.empty > > lookup :: String -> Trie a -> Maybe a > lookup ([]) (T Nothing m) = Nothing > lookup ([]) (T (Just v) m) = return v > lookup (k:ks) (T _ m) = case M.lookup k m of > Nothing -> Nothing > Just trie -> lookup ks trie > > findWithDefault :: a -> String -> Trie a -> a > findWithDefault v k t = fromMaybe v (lookup k t) > > member :: String -> Trie a -> Bool > member k t = maybe False (const True) (lookup k t) > > insertWith :: (a -> a -> a) -> String -> a -> Trie a -> Trie a > insertWith fn ([]) v (T Nothing m) = T (Just v) m > insertWith fn ([]) v (T (Just v') m) = T (Just $ fn v v') m > insertWith fn (k:ks) v (T mv m) = T mv (M.insertWith const k newtrie m) > where > oldtrie = M.findWithDefault empty k m > newtrie = insertWith fn ks v oldtrie > > {-- I also tried to use this line instead of the one above to see > if this had any impact. Unfortunately, I obtained the same > results. > > insertWith fn ([]) v (T (Just v') m) = let x = fn v v' in seq x T (Just x) m > --}

2 2

Haskell Job Opportunity
by S. Alexander Jacobson 26 Apr '07

26 Apr '07

HAppS LLC has part-time and full-time positions open for haskell programmers to: * improve the open source haskell codebase at HAppS.org * implement infrastructure to make it work well in Amazon S3/EC2 environments * make http://pass.net reliable enough to be used by live apps * build the mass market apps we want to run on top of the HAppS/Pass.net platform We are looking for people who: * have substantial experience programming Haskell * have experience building Internet apps (not necessarily in Haskell but would be good), and * live in any of these places: * the Internet (with comfort working entirely over email,skype,tightVNC etc.) * New York * San Francisco * Los Angeles If you qualify and are interested, please send an email with your cv/resume to me or to <opportunity> AT <happs.org>. -Alex-

1 0

Re: [Haskell] Newbie: what are the advantages of Haskell?
by Joel Reymont 26 Apr '07

26 Apr '07

The biggest advantage of Haskell to me is that it helps me write better programs in other languages. For one reason or another Haskell never turns out to be my final implementation language my my programs gain in the process. Joel -- http://wagerlabs.com/

1 0

On reflection
by Greg Meredith 25 Apr '07

25 Apr '07

Oleg, Simon, Thanks for your help. If i understand it correctly, the code below gives a reasonably clean first cut at a demonstration of process calculi as polymorphically parametric in the type of name, allowing for an instantiation of the type in which the quoted processes play the role of name. This is much, much cleaner and easier to read than the OCaml version. Best wishes, --greg {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} module Core( Nominal ,Name ,Locality ,Location ,CoreProcessSyntax ,CoreAgentSyntax ,MinimalProcessSyntax ,MinimalAgentSyntax ,ReflectiveProcessSyntax -- ,make_process ) where -- What's in a name? class Nominal n where nominate :: i -> n i -- newtype Name i = Nominate i deriving (Eq, Show) newtype Name i = Name i deriving (Eq, Show) instance Nominal Name where nominate i = Name i -- Where are we? class Locality a where locate :: (Eq s, Nominal n) => s -> (n i) -> a s (n i) name :: (Eq s, Nominal n) => a s (n i) -> (n i) -- data Location s n = Locate s n deriving (Eq, Show) data Location s n = Location s n deriving (Eq, Show) instance Locality Location where locate s n = Location s n name (Location s n) = n -- Constraints class CoreProcessSyntax p a x | p -> a x where zero :: p sequence :: a -> x -> p compose :: [p] -> p class CoreAgentSyntax x p n | x -> p n where bind :: [n] -> p -> x offer :: [n] -> p -> x -- Freedom (as in freely generated) data MinimalProcessSyntax l x = Null | Sequence l x | Composition [MinimalProcessSyntax l x] data MinimalAgentSyntax n p = Thunk (() -> p) | Abstraction ([n] -> p) | Concretion [n] p -- Responsibility : constraining freedom to enjoy order instance CoreProcessSyntax (MinimalProcessSyntax l x) l x where zero = Null sequence l a = Sequence l a compose [] = zero compose ps = Composition ps instance CoreAgentSyntax (MinimalAgentSyntax n p) p n where bind [] proc = Thunk (\() -> proc) -- -- TODO : lgm : need to substitute m for name in proc bind (name:names) proc = Abstraction (\m -> comp $ bind names proc) where comp (Thunk fp) = fp () -- comp (Abstraction abs) = abs name offer names proc = Concretion names proc data ReflectiveProcessSyntax = Reflect (MinimalProcessSyntax (Location [(Name ReflectiveProcessSyntax)] (Name ReflectiveProcessSyntax)) (MinimalAgentSyntax (Name ReflectiveProcessSyntax) ReflectiveProcessSyntax)) -- instance (CoreProcessSyntax p a x) => -- CoreProcessSyntax -- (MinimalProcessSyntax -- (Location -- [(Name (MinimalProcessSyntax a x))] -- (Name (MinimalProcessSyntax a x))) -- (MinimalAgentSyntax -- (Name (MinimalProcessSyntax a x)) -- (MinimalProcessSyntax a x))) -- (Location -- [(Name (MinimalProcessSyntax a x))] -- (Name (MinimalProcessSyntax a x))) -- (MinimalAgentSyntax -- (Name (MinimalProcessSyntax a x)) -- (MinimalProcessSyntax a x)) -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

2 1

Talking to the serial (RS232) port from Haskell
by Dan Piponi 25 Apr '07

25 Apr '07

What's the easiest way, from Haskell, to open a serial port (under Windows, say) with the correct baud rate and parity, and send data through it? Is there a serial library for Haskell? -- Dan

2 1

Programming Languages and Mechanised Mathematics -- deadline extension
by Jacques Carette 25 Apr '07

25 Apr '07

[Extended deadline: submissions now due May 2nd, 2007] Programming Languages for Mechanized Mathematics Workshop As part of Calculemus 2007 <http://www.risc.uni-linz.ac.at/about/conferences/Calculemus2007/> Hagenbergs, Austria June 29-30, 2007. The intent of this workshop is to examine more closely the intersection between programming languages and mechanized mathematics systems (MMS). By MMS, we understand computer algebra systems (CAS), [automated] theorem provers (TP/ATP), all heading towards the development of fully unified systems (the MMS), sometimes also called universal mathematical assistant systems (MAS) (see Calculemus 2007 <http://www.risc.uni-linz.ac.at/about/conferences/Calculemus2007/>). There are various ways in which these two subjects of /programming languages/ and /systems for mathematics/ meet: * Many systems for mathematics contain a dedicated programming language. For instance, most computer algebra systems contain a dedicated language (and are frequently built in that same language); some proof assistants (like the Ltac language for Coq) also have an embedded programming language. Note that in many instances this language captures only algorithmic content, and /declarative/ or /representational/ issues are avoided. * The /mathematical languages/ of many systems for mathematics are very close to a functional programming language. For instance the language of ACL2 is just Lisp, and the language of Coq is very close to Haskell. But even the mathematical language of the HOL system can be used as a functional programming language that is very close to ML and Haskell. On the other hand, these languages also contain very rich specification capabilities, which are rarely available in most computation-oriented programming languages. And even then, many specification languages (B, Z, Maude, OBJ3, CASL, etc) can still teach MMSes a trick or two regarding representational power. * Conversely, functional programming languages have been getting "more mathematical" all the time. For instance, they seem to have discovered the value of dependent types rather recently. But they are still not quite ready to 'host' mathematics (the non-success of docon <http://www.haskell.org/docon/> being typical). There are some promising languages on the horizon (Epigram <http://www.e-pig.org/>, Omega <http://web.cecs.pdx.edu/%7Esheard/Omega/index.html>) as well as some hybrid systems (Agda <http://agda.sourceforge.net/>, Focal <http://focal.inria.fr/site/index.php>), although it is unclear if they are truly capable of expressing the full range of ideas present in mathematics. * Systems for mathematics are used to prove programs correct. (One method is to generate "correctness conditions" from a program that has been annotated in the style of Hoare logic and then prove those conditions in a proof assistant.) An interesting question is what improvements are needed for this both on the side of the mathematical systems and on the side of the programming languages. We are interested in all these issues. We hope that a certain synergy will develop between those issues by having them explored in parallel. These issues have a very colourful history. Many programming language innovations first appeared in either CASes or Proof Assistants, before migrating towards more mainstream languages. One can cite (in no particular order) type inference, dependent types, generics, term-rewriting, first-class types, first-class expressions, first-class modules, code extraction, and so on. However, a number of these innovations were never aggressively pursued by system builders, letting them instead be developped (slowly) by programming language researchers. Some, like type inference and generics have flourished. Others, like first-class types and first-class expressions, are not seemingly being researched by anyone. We want to critically examine what has worked, and what has not. Why are all the current ``popular''[1] computer algebra systems untyped? Why are the (strongly typed) proof assistants so much harder to use than a typical CAS? But also look at question like what forms of polymorphism exists in mathematics? What forms of dependent types exist in mathematics? How can MMS regain the upper hand on issues of 'genericity'? What are the biggest barriers to using a more mainstream language as a host language for a CAS or an ATP? This workshop will accept two kinds of submissions: full research papers as well as position papers. Research papers should be nore more than 15 pages in length, and positions papers no more than 3 pages. Submission will be through _EasyChair_. An informal version of the proceedings will be available at the workshop, with a more formal version to appear later. We are looking into having the best papers completed into full papers and published as a special issue of a Journal (details to follow). Important Dates May 02, 2007: Submission Deadline (Extended!) May 30, 2007: Notification June 29-30, 2007: Workshop Program Committee Lennart Augustsson [Credit Suisse] Wieb Bosma [Radboud University Nijmegen, Netherlands] Jacques Carette (co-Chair) [McMaster University, Canada] David Delahaye [CNAM, France] Jean-Christophe Filliâtre [CNRS and Université de Paris-Sud, France] John Harrison [Intel Corporation, USA] Josef Urban [Charles University, Czech Republic] Markus (Makarius) Wenzel [Technische Universität München, Germany] Freek Wiedijk (co-Chair) [Radboud University Nijmegen, Netherlands] Wolfgang Windsteiger [University of Linz, Austria] Location and Registration Location and registration information can be found on the Calculemus <http://www.risc.uni-linz.ac.at/about/conferences/Calculemus2007/> web site. ----------------------------------------------------------------------------- [1] by popular we mean > 1 million users.

1 0

Program optimisation
by Andrew Coppin 25 Apr '07

25 Apr '07

I have *no idea* if this is an appropriate place to put this, but here goes... I have a (presumably) common problem. I have a nice Haskell program. It's compute-bounded, and I'd like to make it go faster. To that end, I've been trying to optimise it. Without going into great detail, the program basically revolves around processing a list and dumping the results into a file. Notable things about this structure: it's *big*, and I only need to *map* over it. Anyway, here's what I did... I wrote a simplified, cut down version of the program so I would have a fixed test case. I compiled it with GHC 6.6 and ran it. It takes 40 seconds to complete. Next, I read the GHC manual. Apparently there's a command-line switch "-O2" which makes GHC try harder to optimise the program. (I had stupidly assumed it always tries to make good code...) The result? The program now does the same job in 30 seconds. That's quite a big speedup just for typing 3 characters! (Gee... I wonder what it does differently? I did notice that the compilation time went from 5 seconds up to 20 seconds. And the *.exe got smaller.) Next I played with profiling. If I'm reading this correctly, the "-s" profile is telling me that my program spends 72% CPU time doing GC. o_O Er... that's really suboptimal. Also - and this is really weird - the "-p" profile tells me that 82% of the program's time is spent in the quant8 function. The source code for this function is precisely quant8 :: Double -> Word8 quant8 x = floor $ x * 0xFF Why that should take 82% CPU when the program is also doing heavy-metal complex number arithmetic and trig functions I have no idea! (Since I took those measurements, I have come up with a theory. When I ask for all these computations to be done... Haskell doesn't actually *do* them. It just stores them up until "needed". It just occurred to me that quant8 is the *last* thing I ask it to do before the code hits a strict ByteString... So is the profiler just misappropriating all the work to quant8 when it's really elsewhere?) OK, so to recap: currently my program takes 30 seconds to run. Next, I changed the 2D lists (i.e., [[x]]) into 1D lists (that is, [x]). The new runtime? 30 seconds. Right, that seems to be no-op. Next I replaced lists with immutable boxed arrays. New runtime: 33 seconds. Ooops. Now, I would have thought an array would make the GC's life *much* easier by replacing tens of thousands of cons cells with one nice big array. But, apparently, no. The profiler output says GC is almost identical. Hmm... weird! Next, I switched to IO-mutable boxed arrays. (With in-place updates.) New runtime: 35 seconds. Da hell...? The more I optimise this program, the slower it goes! :'( Finally, in a fit of desperation, I changed it to *unboxed* arrays. For some reason, you can't have an unboxed array of complex numbers. So I had to make *two* unboxed arrays of doubles, and manually split/join myself. Similar problems happened elsewhere too. Suffice it to say, my program is now vomit-inducingly ugly. It doesn't even *function* correctly any more! (There's a byte alignment issue somewhere... I can't track it down.) New runtime: 15 seconds. I say again: 15 seconds. Changing to an unboxed array has *doubled* the speed. Not only that, the GC report now shows GC as using 7% CPU time, and peak RAM usage has been reduced from 25 MB to 4 MB. The memory graph is now utterly flat, whereas even with IO-mutable arrays with in-place update, it was still fluctuating all over the place. I will mention that the ByteString module was the only thing I would find in all of Haskell for doing binary I/O. The final (fast) program uses an IOUArray Int Word8 to do the binary I/O instead. (What's the difference BTW? Is there one? Other than the name anyway.) Perhaps part of the speed was in avoiding an array type conversion? I don't know. Certainly this is the messiest part, and the part where I suspect my bug is hiding. Finally, in the fast version, quant8 uses way less CPU (more like 50%), and the complex number math uses much more. Really goes look like the profiler being counterintuitive to me... Personally, I find it quite worrying that I had to manually mutilate my program to unbox everything when the compiler is supposed to be able to do such things automatically. Does GHC "know" about the array types? Or are they just a bunch of FFI calls that some 3rd party wrote? When I talk to other people about Haskell, they all say "immutable sucks; that must be SO slow!" and I tell them "yeah, but the compiler can strip almost all of it out automatically". Well, my experience with this program suggests very differently. I do wonder if the program went faster just because unboxed arrays are strict. I couldn't think of any way to make a boxed array be strict. (I tried for ages!) Next task: Attempt to make the program use both cores on my dual-core monster machine for even more speed... A short program synopsys: module Main where init_frame :: [[Complex Double]] next_frame :: [[Complex Double]] -> [[Complex Double]] process :: [[Complex Double]] -> [[Colour]] save_file :: FilePath -> [[Colour]] -> IO () main = do work 0 init_frame work n xss = do save_file ("Frame" ++ show n) (process xss) if n < 500 then work (n+1) (next_frame xss) else return ()

3 2

Re: release plans
by Chad Scherrer 25 Apr '07

25 Apr '07

> What do you think of this plan? Are there features/bug-fixes that you really want to see in 6.8? I'm most anxious for parallel GC - do you think it will be another release or two before this is a reality? Thanks, Chad

3 2