February 2008 - Haskell-Cafe

a general question on Arrows
by Steve Lihn 15 Feb '08

15 Feb '08

In John Hughes' paper [1], Programming with Arrows, p. 20, "The truly interesting arrow types are those which do not correspond to a monad, because it is here that arrows give us real extra generality. Since we know that stream functions cannot be represented as a monad, then they are one of these "interesting" arrow types. So are the arrows used for functional reactive programming, for building GUIs, and the arrows for discrete event simulation we present in Section 5. And since these arrows cannot be represented by a monad, we know that they cannot support a sensible definition of app either." He described a few things that "cannot" be represented as a monad, they are: 1. Stream 2. FRP 3. GUI (request/response?) 4. Event Driven System (like circuits, robots?) My first question is: Are they "absolutely" outside of the realm of function + monad, therefore, arrows are indispensable? Or it is simply because the haskell program would be very cumbersome without arrows in these areas? (I mean without utilizing FFI to rescue.) The second question is: Other than the 4 areas above, are there more? Just want to get a sense of how useful arrows are. Not really a theoretical question. Thanks, Steve [1] http://www.cs.chalmers.se/~rjmh/afp-arrows.pdf

2 3

Best way to find an "undefined" error?
by Scott West 14 Feb '08

14 Feb '08

Hello all, Does anyone favourite technique to track down an "undefined" call? I'm 99% sure that my code is not the offender (I've grepped for undefined occurrences and turned them all into "error" calls). Supposing that this is happening in some other package or library that I'm using, what is the best way to find out where it is? I have profiling enabled on all libraries that I use, so I'm ok there I think. Any magic combination of +RTS .. -RTS? Scott

3 6

ANN: Leksah 0.1 - Haskell IDE written in Haskell
by Jürgen Nicklisch-Franken 14 Feb '08

14 Feb '08

I'm pleased to announce the first release of Leksah, an IDE for Haskell written in Haskell. Leksah is intended as a practical tool to support the Haskell development process. This is an unfinished pre-release with bugs and open ends. However, I decided to make a first announcement, hoping that Leksah may already be interesting and useful. Leksah uses GTK+ as GUI Toolkit with the gtk2hs binding. It is platform independent and should run on any platform where GTK+, gtk2hs and GHC can be installed. I have tested it on Windows and Linux. It only supports GHC. Features: * jumping to code every and anywhere * integration of cabal build * source candy * keymaps * configurable window * ... Some rudimentary documentation can be found in the doc/ subdirectory. Author and availability: Leksah is written by me and published under a GPL-2 license. Leksah can be optained via Hackage: http://hackage.haskell.org/ Darcs development repository: http://code.haskell.org/leksah Juergen

8 9

ANN: ctemplate, SSL server support in HsOpenSSL, network-minihttp, binary parsing, network-dns
by Adam Langley 14 Feb '08

14 Feb '08

Binary parsing: binary-strict now has support for combinator parsing[1] with <|> and friends. This works both for the strict Get and the IncrementalGet. (The latter was more complex than I expected) binary-strict also gained a very fast byte set module[2] (used for scanning ranges of valid bytes) and a surprisingly useful hexDump[3] function (because I kept having to write it in lots of places) [1] http://hackage.haskell.org/packages/archive/binary-strict/0.3.0/doc/html/Da… [2] http://hackage.haskell.org/packages/archive/binary-strict/0.3.0/doc/html/Da… [3] http://hackage.haskell.org/packages/archive/binary-strict/0.3.0/doc/html/Da… DNS: network-dns contains a DNS client library[4] in pure Haskell. The ADNS library (for which a wrapper already exists) is GPL, not BSD. This code is also halfway to being a DNS server should anyone so wish. This is very similar to the DNS client library in libevent (because I wrote them both). HTTP: ctemplate is a wrapping of the template library which Google uses for most of their sites. There are several template systems already in Hackage, but I like ctemplate because escaping is so easy and well supported. Generally the power of a template system doesn't interest me (in fact, it can be a bad thing), but stopping XSS attacks is a big deal. HsOpenSSL now has rudimentary support for writing SSL servers[5] (clients coming soon). In terms of blocking IO, this /should/ work the way you would hope (i.e. like a Haskell function w.r.t. forkIO). network-minihttp is a small HTTP server. Currently it serves files from the disk (with caching and range support), but it's most of the way to being a HTTP client also. Don't do anything too serious with it yet, however. It needs a few limits to stop DoS attackers from, for example, sending an infinite header and using up all the memory :) [4] http://hackage.haskell.org/packages/archive/network-dns/0.1.1/doc/html/Netw… -- Adam Langley agl(a)imperialviolet.org http://www.imperialviolet.org 650-283-9641

1 0

Re: [Haskell-cafe] Re: A question about "monad laws"
by Thorkil Naur 14 Feb '08

14 Feb '08

Hello, On a tangent, probably: On Thursday 14 February 2008 10:24, Roman Leshchinskiy wrote: > ... > Hmm. Personally, I've never seen an algorithm where comparing for exact > equality was algorithmically necessary. Sometimes (rarely) it is > acceptable but necessary? Do you know of one? Finding the "machine epsilon", perhaps, that is, the smallest (floating point, surely) number for which 1.0+machine_eps==1.0 would be a candidate? > ... Best regards Thorkil

2 1

Haskell wiki is searched by google.
by Daniil Elovkov 14 Feb '08

14 Feb '08

Hello I remember there was a problem with haskell wiki pages not being indexed and searched. Now it seems to work perfectly. Actually typing 'monomorphism restriction' in google I see the appropriate wiki page as the first result. I must have missed the moment when it was fixed. Just sharing my observations. Thanks.

4 6

threads + IORefs = Segmentation fault?
by David Roundy 14 Feb '08

14 Feb '08

Hi all, I'm working on some new progress-reporting code for darcs, and am getting segmentation faults! :( The code uses threads + an IORef global variable to do this (with lots of unsafePerformIO). So my question for the gurus who know more about this than I do: is this safe? I thought it would be, because only one thread ever modifies the IORef, and the others only read it. I don't really care if they read a correct value, as long as they don't segfault. The code (to summarize) looks like: {-# NOINLINE _progressData #-} _progressData :: IORef (Map String ProgressData) _progressData = unsafePerformIO $ newIORef empty updateProgressData :: String -> (ProgressData -> ProgressData) -> IO () updateProgressData k f = when (progressMode) $ modifyIORef _progressData (adjust f k) setProgressData :: String -> ProgressData -> IO () setProgressData k p = when (progressMode) $ modifyIORef _progressData (insert k p) getProgressData :: String -> IO (Maybe ProgressData) getProgressData k = if progressMode then lookup k `fmap` readIORef _progressData else return Nothing The key function is beginTedious :: String -> IO () beginTedious k = do tid <- forkIO $ handleProgress k debugMessage $ "Beginning " ++ k setProgressData k $ ProgressData { sofar = 0, latest = Nothing, total = Nothing, handler = Just tid } which is called before an action that may be so tedious for our users that they need their day brightened by messages such as "Applying patch 137/1436". The handleProgress function alternates between threadDelay and reading the progress data to see whether any progress has been made and printing messages. Meanwhile the main thread calls functions that update _progressData. Anyhow, the point is that I'm getting segfaults, even after recompiling everything from scratch! Is this in fact that unsafe? Do I really need to switch to MVars, even though no locking is required? -- David Roundy Department of Physics Oregon State University

6 9

Designing DSL with explicit sharing [was: I love purity, but it's killing me]
by oleg＠okmij.org 14 Feb '08

14 Feb '08

Tom Hawkins wrote: ] My DSLs invariably define a datatype to capture expressions; something ] like this: ] ] data Expression ] = Add Expression Expression ] | Sub Expression Expression ] | Variable String ] | Constant Int ] deriving Eq ] The problem comes when I want to generate efficient code from an ] Expression (ie. to C or some other target language). The method I use ] invovles converting the tree of subexpressions into an acyclic graphic ] to eliminate common subexpressions. The nodes are then topologically ] ordered and assigned an instruction, or statement for each node. For ] example: ] ] let a = Add (Constant 10) (Variable "i1") ] b = Sub (Variable "i2") (Constant 2) ] c = Add a b ] The process of converting an expression tree to a graph uses either Eq ] or Ord (either derived or a custom instance) to search and build a set ] of unique nodes to be ordered for execution. In this case "a", then ] "b", then "c". The problem is expressions often have shared, ] equivalent subnodes, which dramatically grows the size of the tree. ] For example: ] ] let d = Add c c ] e = Add d d -- "e" now as 16 leaf nodes. ] ] As these trees grow in size, the equality comparison in graph ] construction quickly becomes the bottleneck for DSL compilation. We show the design of the same sort of DSL that explicitly maintains sharing information and where node comparisons are quick, because we are comparing hashes rather than trees themselves. Our approach is assuredly safe, pure, and Haskell98 (save for disabling of the monomorphism restriction, which is done solely to avoid writing signatures). No GHC-specific behavior is relied upon. > {-# OPTIONS_GHC -fno-monomorphism-restriction #-} > > module DSL where > > import Data.IntMap as IM > import Control.Monad.State The approach is based on the final tagless representation. Here is our DSL: > class Exp repr where > constant :: Int -> repr Int > variable :: String -> repr Int > add :: repr Int -> repr Int -> repr Int > sub :: repr Int -> repr Int -> repr Int Tom Hawkins' test expressions now look as follows > a = add (constant 10) (variable "i1") > b = sub (variable "i2") (constant 2) > c = add a b > d = add c c > e = add d d which is the same as before modulo the case of the identifiers: everything is in lower case. We can show the expressions as before: showing is one way of evaluating things > newtype S t = S{unS :: String} > > instance Exp S where > constant x = S $ show x > variable x = S x > add e1 e2 = S( unS e1 ++ " + " ++ unS e2) > sub e1 e2 = S( unS e1 ++ " - " ++ unS e2) > > test_showe = unS e *DSL> test_showe "10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2" We can write an evaluator for the expressions > type REnv = [(String,Int)] > newtype R t = R{unR :: REnv -> t} -- A reader Monad, actually > > instance Exp R where > constant x = R $ const x > variable x = R ( \env -> maybe (error $ "no var: " ++ x) id $ > Prelude.lookup x env) > add e1 e2 = R(\env -> unR e1 env + unR e2 env) > sub e1 e2 = R(\env -> unR e1 env - unR e2 env) > test_vale = unR e [("i1",5),("i2",10)] -- 92 We stress: we are using exactly the same expression e as before. We are only evaluating it differently. The gist of the final tagless approach is to write an expression once and evaluate it many times. Now, we chose a different representation: to make sharing explicit We chose not to rely on GHC; we don't care if in (add c c), the two c are shared or copied. It is not observable in pure Haskell, and we don't care. We build our acyclic graph nevertheless. > type ExpHash = Int We stress: ACode is NOT a recursive data structure, so the comparison of ACode values takes constant time! > data ACode = AConst ExpHash | > AVar ExpHash | > AAdd ExpHash | > ASub ExpHash > deriving (Eq,Show) > data ExpMaps = ExpMaps{ hashcnt :: ExpHash, -- to generate new Hash > ctmap :: IntMap Int, > vrmap :: IntMap String, > admap :: IntMap (ACode,ACode), > sumap :: IntMap (ACode,ACode)} > deriving Show > exmap0 = ExpMaps 0 IM.empty IM.empty IM.empty IM.empty > > > newtype A t = A{unA :: State ExpMaps ACode} Granted, the following could be done far more efficiently: we need bimaps. > loookupv :: Eq v => v -> IntMap v -> Maybe Int > loookupv v = IM.foldWithKey > (\k e z -> maybe (if e == v then Just k else Nothing) (const z) z) > Nothing > > record con prj upd x = do > s <- get > maybe (do let s' = upd (s{hashcnt = succ (hashcnt s)}) > (IM.insert (hashcnt s) x (prj s)) > put s' > return (con $ hashcnt s)) > (return . con) $ loookupv x (prj s) > instance Exp A where > constant x = A(record AConst ctmap (\s e -> s{ctmap = e}) x) > variable x = A(record AVar vrmap (\s e -> s{vrmap = e}) x) > add e1 e2 = A(do > h1 <- unA e1 > h2 <- unA e2 > record AAdd admap (\s e -> s{admap = e}) (h1,h2)) > sub e1 e2 = A(do > h1 <- unA e1 > h2 <- unA e2 > record ASub sumap (\s e -> s{sumap = e}) (h1,h2)) Again, we are using the very same expression e we wrote at the very beginning: > test_sme = runState (unA e) exmap0 *DSL> test_sme (AAdd 8, ExpMaps {hashcnt = 9, ctmap = fromList [(0,10),(4,2)], vrmap = fromList [(1,"i1"),(3,"i2")], admap = fromList [(2,(AConst 0,AVar 1)),(6,(AAdd 2,ASub 5)), (7,(AAdd 6,AAdd 6)),(8,(AAdd 7,AAdd 7))], sumap = fromList [(5,(AVar 3,AConst 4))]}) We retain all the information about expression 'e'. In addition, all sharing is fully explicit. As we can see, the evaluation process finds common subexpressions automatically.

4 5

Re: [Haskell-cafe] ANN: nano-hmac 0.2.0
by Don Stewart 13 Feb '08

13 Feb '08

Ok, I'll leave it up there as a separate package then. :) -- Don hitesh.jasani: > Don, > > It's tempting, but I would really hate to lose nano-md5 as it is > today. I thought your concept was a great idea to inspire people to > start small to get a feel for developing Haskell libraries. The > current nano-md5 serves as a really good example. > > In the Ruby community there are many small libraries that do one, > simple focused task. There are times when this is a virtue over > libraries that try to be all encompassing. It's weird but I would > have thought the Haskell community would have more embraced small > libraries also since they may be more composable. > > - Hitesh > > > On Feb 11, 2008 4:29 PM, Don Stewart <dons(a)galois.com> wrote: > > hitesh.jasani: > > > nano-hmac provides bindings to OpenSSL's HMAC interface. With this release the > > > set of hashing functions supported is: MD5, SHA, SHA1, SHA224, SHA256, SHA384, > > > SHA512. > > > > > > If you're unfamiliar with HMAC's then you may want to check out the second link > > > below where I explain a little bit about them in a blog entry. > > > > > > The hackage pages mentioned that they're not running haddock 2.0, so I don't > > > know if the docs will generate. If not, you can see the docs online at the > > > third link below. > > > > > > * http://hackage.haskell.org/cgi-bin/hackage-scripts/package/nano-hmac-0.2.0 > > > * http://www.jasani.org/2008/02/nano-hmac-020-released.html > > > * http://docs.jasani.org/nano-hmac/0.2.0/ > > > > > > Any and all comments/suggestions/criticisms/fortune-cookie-proverbs are welcome. > > > > > > > Shall we merge nano-md5 into this lib, and deprecate nano-md5 itself? > > Seems like a good time to consolidate, and produce a single openssl > > binding. > > > > -- Don > >

3 2

Re: [Haskell-cafe] existential types
by Jake McArthur 13 Feb '08

13 Feb '08

From: Jake McArthur <jake.mcarthur(a)gmail.com> Date: February 13, 2008 7:04:49 PM CST To: Felipe Lessa <felipe.lessa(a)gmail.com> Subject: Re: [Haskell-cafe] existential types On Feb 13, 2008, at 11:15 AM, Felipe Lessa wrote: > On Feb 13, 2008 2:41 PM, Jake McArthur <jake.mcarthur(a)gmail.com> > wrote: >> Now we can have NumericLists like [1 :: Int, 5.7 :: Double, 4%5 :: >> Rational]. > > No, we can't =). Using > > data NumericList = forall a . Num a => N [a] > [etc.etc.etc.] Oops again. Maybe I just shouldn't say anything to anybody on the Internet within an hour of waking up in the morning! ;) - Jake

1 0