July 2011 - Haskell-Cafe

ANN: unification-fd: simple generic unification
by wren ng thornton 12 Jul '11

12 Jul '11

-------------------------------------------- -- unification-fd 0.5.0 -------------------------------------------- The unification-fd package offers generic functions for first-order structural unification (think Prolog programming or Hindley--Milner type inference). I've had this laying around for a few years, so I figured I might as well publish it. An effort has been made to try to make this package as portable as possible. However, because it uses the ST monad and the mtl-2 package it can't be H98 nor H2010. However, it only uses the following common extensions which should be well supported[1]: Rank2Types MultiParamTypeClasses FunctionalDependencies FlexibleContexts FlexibleInstances UndecidableInstances [1] With the exception of fundeps which are notoriously difficult to implement. However, they are supported by Hugs and GHC 6.6, so I don't feel bad about requiring it. Once the API stabilizes a bit more I plan to release a unification-tf package which uses type families instead, for those who feel type families are easier to implement or use. -------------------------------------------- -- Description -------------------------------------------- The unification API is generic in the type of the structures being unified and in the implementation of unification variables, following the two-level types pearl of Sheard (2001). This style mixes well with Swierstra (2008), though an implementation of the latter is not included in this package. That is, all you have to do is define the functor whose fixed-point is the recursive type you're interested in: -- The non-recursive structure of terms data S a = ... -- The recursive term type type PureTerm = Fix S And then provide an instance for Unifiable, where zipMatch performs one level of equality testing for terms and returns the one-level spine filled with pairs of subterms to be recursively checked (or Nothing if this level doesn't match). class (Traversable t) => Unifiable t where zipMatch :: t a -> t b -> Maybe (t (a,b)) The choice of which variable implementation to use is defined by similarly simple classes Variable and BindingMonad. We store the variable bindings in a monad, for obvious reasons. In case it's not obvious, see Dijkstra et al. (2008) for benchmarks demonstrating the cost of naively applying bindings eagerly. There are currently two implementations of variables provided: one based on STRefs, and another based on a state monad carrying an IntMap. The former has the benefit of O(1) access time, but the latter is plenty fast and has the benefit of supporting backtracking. Backtracking itself is provided by the logict package and is described in Kiselyov et al. (2005). In addition to this modularity, unification-fd implements a number of optimizations over the algorithm presented in Sheard (2001)--- which is also the algorithm presented in Cardelli (1987). * Their implementation uses path compression, which we retain. Though we modify the compression algorithm in order to make sharing observable. * In addition, we perform aggressive opportunistic observable sharing, a potentially novel method of introducing even more sharing than is provided by the monadic bindings. Basically, we make it so that we can use the observable sharing provided by the previous optimization as much as possible (without introducing any new variables). * And we remove the notoriously expensive occurs-check, replacing it with visited-sets (which detect cyclic terms more lazily and without the asymptotic overhead of the occurs-check). A variant of unification which retains the occurs-check is also provided, in case you really need to fail fast for some reason. * Finally, a highly experimental branch of the API performs *weighted* path compression, which is asymptotically optimal. Unfortunately, the current implementation is quite a bit uglier than the unweighted version, and I haven't had a chance to perform benchmarks to see how the constant factors compare. Hence moving it to an experimental branch. I haven't had a chance to fully debug these optimizations, though they pass some of the obvious tests. If you find any bugs, do be sure to let me know. Also, if you happen to have a test suite or benchmark suite for unification on hand, I'd love to get a copy. -------------------------------------------- -- References -------------------------------------------- Luca Cardelli (1987) /Basic polymorphic typechecking/. Science of Computer Programming, 8(2):147--172. Atze Dijkstra, Arie Middelkoop, S. Doaitse Swierstra (2008) /Efficient Functional Unification and Substitution/, Technical Report UU-CS-2008-027, Utrecht University. <http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-027.pdf> Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry (2005) /Backtracking, Interleaving, and/ /Terminating Monad Transformers/, ICFP. <http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf> Tim Sheard (2001) /Generic Unification via Two-Level Types/ /and Paramterized Modules/, Functional Pearl, ICFP. <http://web.cecs.pdx.edu/~sheard/papers/generic.ps> Tim Sheard & Emir Pasalic (2004) /Two-Level Types and/ /Parameterized Modules/. JFP 14(5): 547--587. This is an expanded version of Sheard (2001) with new examples. <http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps> Wouter Swierstra (2008) /Data types a la carte/, Functional Pearl. JFP 18: 423--436. <http://www.cs.ru.nl/~wouters/Publications/DataTypesALaCarte.pdf> -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/unification-fd Darcs: http://community.haskell.org/~wren/unification-fd Haddock (Darcs version): http://community.haskell.org/~wren/unification-fd/dist/doc/html/unification… -- Live well, ~wren

1 0

Re: [Haskell-cafe] [Haskell] Call for GUI examples - Functional Reactive Programming
by Paul Liu 12 Jul '11

12 Jul '11

Hi James, I think you meant to reply to the list. For one, I wouldn't consider GUI programming based on HTML as declarative, since more often than not, the format says nothing about its behavior, and when it does, it's through javascript, which is hardly declarative. Regards, Paul Liu On Tue, Jul 12, 2011 at 5:17 AM, James Deng <cnjamesdeng(a)gmail.com> wrote: > These days, more and more GUI programming are done in declarative, such as > HTML(jQuery), Mozilla XUL, android UI XML. > > Haskell is an excellent declarative language, so should have the advantages > of constructing GUI in declarative, intuitive and powerful way. But so far, > there is not such a GUI library intuitive like Html, powerful like XUL. > > I expect something like html to layout GUI, and a haskell GUI engine would > render the user interfaces files. > Where is the gap lying? > > On 07/12/2011 05:51 AM, Paul Liu wrote: > > You guys might want to checkout the recent work on Euterpea at Yale > CS. In particular: > > 1. Paul Hudak is writing a new book. > http://plucky.cs.yale.edu/cs431/reading.htm > 2. It uses FRP and arrows for sound synthesis. > 3. It combines FRP signals with monadic (which recently gets > re-written in arrows) GUI composition. > 4. New novel techniques is being developed to handle I/O within arrows > framework. > > The code can be obtained through darcs, details at > http://plucky.cs.yale.edu/cs431/software_resources.htm > > Notably, the way it handles GUI is that the composition of widgets are > static, but the signals flowing between them are dynamic. This closely > follows Conal Elliott's Phooey approach, and greatly reduces the > complexity of GUI programming. > > Disclaimer: I was an ex-student who worked on this project. > > Regards, > Paul Liu > > On Thu, Jul 7, 2011 at 11:08 PM, Heinrich Apfelmus > <apfelmus(a)quantentunnel.de> wrote: > > Dear Haskellers, > > Can GUI programming be liberated from the IO monad? > > > Regards, > -- > James Deng > http://cnjdeng.appspot.com -- Regards, Paul Liu

1 0

Inconsistent trailing comma in export list and record syntax
by L Corbijn 12 Jul '11

12 Jul '11

Hello, I'm wondering why the trailing comma is allowed in export syntax, but not in record syntax, here an example module Foo ( export1, -- is allowed ) where data Type = Type { record1 :: Foo, -- is not allowed } To me this seems quite inconsistent and sometimes quite frustrating, imagine the case that you want to temporarily remove the last record: data Type = Type { record1 :: Foo, -- record2 :: Bar } this would fail due to an extra comma that has to be commented out. You could of course say that I'm using a bad style, but it remains that it seems to be inconsistent to allow a trailing comma in one place and not in the other. So is there an reason for this? Lars Corbijn

8 7

External system connections
by Richard Wallace 11 Jul '11

11 Jul '11

Hello all, I'm trying to understand how to properly structure a connection to an external system. I'm writing an application that processes requests (it's an IRC bot - ya, I've looked at lambabot but it's a bit beyond my current understanding and I'm really trying to learn this stuff and find the best way to do that is to write it myself) and sends requests to an external system, via SOAP. The SOAP requests should be sent on separate threads. The SOAP server requires an initial request for authentication be made to obtain a token used on subsequent requests. There are three ways I can structure this. One is to do the authentication with the SOAP server when the application starts up and just use that token for all subsequent requests. This will fall over if the token times out and I'd have to restart the application. Another way is to do authenticate with the server and get a new token for each request. This is obviously really inefficient. What I'd like to do is something a bit smarter. When a request to the SOAP server is to be made, if we have a token then we try and use it. If it fails, we reauthenticate and get a new token. When establishing a new token, other threads trying to send SOAP requests should block until a new token is available. There are other conditions that should be handled - such as an exponential back-off when the SOAP server can't be reached - but I feel like reestablishing the authentication token is really the key concern here. Unfortunately, I have no idea right now how to write this in Haskell. Any pointers would be awesome. Thanks! Rich

9 12

Fwd: The Typeable class is changing
by Alberto G. Corona 11 Jul '11

11 Jul '11

What to do when the data has been defined in other package and provides no Typeable instance? 2011/7/11 Yitzchak Gale <gale(a)sefer.org> > Simon Marlow has announced[1] on the Haskell Libraries > list that the Typeable class is changing. > > The standard way to create a Typeable instance is > just to derive it. If you do that, you will not be affected > by this change. > > But it seems that many packages create Typeable > instances by explicitly using mkTyCon. If your package > does this, it will eventually break, after a deprecation > period. > > Please respond to this thread if you own a package > that will be affected by this change. > > Can someone who has quick access to the entire contents > of Hackage please do a grep and find out exactly which > packages on Hackage will be affected? Thanks. > > -Yitz > > [1] http://www.haskell.org/pipermail/libraries/2011-July/016546.html > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

Re: [Haskell-cafe] Inconsistent trailing comma in export list and record syntax
by Johan Tibell 11 Jul '11

11 Jul '11

On Mon, Jul 11, 2011 at 3:54 PM, Henning Thielemann <thunderbird(a)henning-thielemann.de> wrote: > Johan Tibell wrote: >> I've found this quite annoying, especially when using CPP to >> conditionally include something in a list, as it might force you to >> reorder the list to make the commas appear correctly when the >> conditional section is enabled/disabled. > > In this case I use the colon like a terminator. > > http://www.haskell.org/haskellwiki/List_notation Sorry, I wasn't being clear. I meant for import/export lists. Johan

2 1

Monad.Reader #19 call for copy -- special issue on parallelism and concurrency
by Brent Yorgey 11 Jul '11

11 Jul '11

Call for Copy: The Monad.Reader - Issue 19 SPECIAL ISSUE on parallelism and concurrency -------------------------------------------- Whether you're an established academic or have only just started learning Haskell, if you have something to say, please consider writing an article for The Monad.Reader! Issue 19 will be a special issue focusing on parallelism and concurrency, construed broadly. The submission deadline for Issue 19 will be: **Tuesday, August 16** The Monad.Reader ~~~~~~~~~~~~~~~~ The Monad.Reader is a electronic magazine about all things Haskell. It is less formal than journal, but somehow more enduring than a wiki- page. There have been a wide variety of articles: exciting code fragments, intriguing puzzles, book reviews, tutorials, and even half-baked research ideas. Submission Details ~~~~~~~~~~~~~~~~~~ Get in touch with me if you intend to submit something -- the sooner you let me know what you're up to, the better. Please submit articles for the next issue to me by e-mail (byorgey at cis.upenn.edu) Articles should be written according to the guidelines available from http://themonadreader.wordpress.com/contributing/ Please submit your article in PDF, together with any source files you used. The sources will be released together with the magazine under a BSD license. If you would like to submit an article, but have trouble with LaTeX please let me know and we'll work something out.

1 0

Re: [Haskell-cafe] IterIO: How to write use my inumReverse
by Maciej Wos 11 Jul '11

11 Jul '11

Sorry, my previous message got truncated. I was trying to say that many iteratees like iterReverse can be defined nicely using combinators from Control.Applicative. You end up with much cleaner code. Also, iterLines doesn't work as the name would suggest. It only consumes one line from the input stream and returns it inside a singleton list. Instead, iterLines can be defined like this: iterLines :: (Monad m) => Iter L.ByteString m [L.ByteString] iterLines = do el <- tryBI lineI case el of -- no more "full" lines left, return the remaining data Left (e :: SomeException) -> (:[]) <$> dataI -- read one line; add it to the list and read more Right line -> (line:) <$> iterLines enumPure "line1\nline2\nline3" |$ iterLines [Chunk "line1" Empty,Chunk "line2" Empty,Chunk "line3" Empty] However, the above returns the resulting list only after consuming the whole stream, which is something to avoid. In case of iterReverse it is better to read and accumulate characters until \n is found and then return the reversed string. One way to do this is to read one character at a time: reverseLineSlow :: Iter L.ByteString IO L.ByteString reverseLineSlow = iter "" where iter acc = do c <- headI case c of 10 -> return $ L.reverse acc _ -> iter (acc `mappend` L.singleton c) But this will be really slow. Instead, the data should be read one chunk at a time: reverseLine :: Iter L.ByteString IO L.ByteString reverseLine = iter "" where iter acc = do -- read the data from the stream one chunk at a time Chunk c eof <- chunkI -- check if there is any \n, i.e. if we read a whole line let (a,b) = L.break (==10) c if b == "" -- haven't found any \n yet; append all data to the accumulator then iter (acc `mappend` a) -- have found \n else do -- put the data after \n back (while removing \n itself) ungetI $ L.tail b -- return reversed accumulator plus the data up to \n return $ L.reverse $ acc `mappend` a Hope this helps! -- Maciej On Tue, Jul 12, 2011 at 12:47 AM, Maciej Wos <maciej.wos(a)gmail.com> wrote: > Don't forget Applicative instance! > iterReverse = L.reverse <$> lineI > > On Monday, 4 July 2011 at 22:54, dm-list-haskell-cafe(a)scs.stanford.edu > wrote: > > At Mon, 4 Jul 2011 20:36:33 +1000, > John Ky wrote: > > Hi Haskell Cafe, > > enum |$ inumLines .| inumReverse .| inumUnlines .| iter > ... > > iterLines :: (Monad m) => Iter L.ByteString m [L.ByteString] > iterLines = do > line <- lineI > return [[line] > > iterUnlines :: (Monad m) => Iter [L.ByteString] m L.ByteString > iterUnlines = (L.concat . (++ [C.pack "\n"])) `liftM` dataI > > iterReverse :: (Monad m) => Iter [L.ByteString] m [L.ByteString] > iterReverse = do > lines <- dataI > return (map L.reverse lines) > > inumLines = mkInum iterLines > inumUnlines = mkInum iterUnlines > inumReverse = mkInum iterReverse > > It all works fine. > > My question is: Is it possible to rewrite inumReverse to be this: > > iterReverse :: (Monad m) => Iter L.ByteString m L.ByteString > iterReverse = do > line <- dataI > return (L.reverse line) > > inumReverse = mkInum iterReverse > > And still be able to use it in the line: > > enum |$ inumLines .| {-- inumReverse goes in here somehow --} .| > inumUnlines .| iter > > The reason I ask is that the Haskell function reverse has the type [a] -> > [a], > not [[a]] -> [[a]]. > > I thought perhaps the alternative inumReverse is cleaner than the original > as > it behaves more similarly to Haskell's own reverse function. > > I'm not sure what you are trying to achieve. If you want an iter that > works on L.ByteStrings, then you can say: > > iterReverse :: (Monad m) => Iter L.ByteString m L.ByteString > iterReverse = do > line <- lineI > return (L.reverse line) > > In that case you don't need inumLines and inumUnlines. If, however, > you want the type to be [L.ByteString], and you would rather do this > one line at a time, instead of calling map, then you could do > something like the following: > > iterReverse :: (Monad m) => Iter [L.ByteString] m [L.ByteString] > iterReverse = do > line <- headI > return [L.reverse line] > > But the code you have above should also work, so it all depends on > what you are trying to achieve. > > David > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

1 0

Good XML-Enumerator Examples
by Michael Xavier 11 Jul '11

11 Jul '11

Hi Cafe. I'm writing a library which will be parsing XML data from a web API. I'm fairly well versed at this point in parsing JSON (aeson being my library of choice). For XML, I like the API of xml-enumerator over hxt because it appears to be nice and simple .The problem is that the example in the documentation isn't really sufficient for me to get a grasp of how to traverse XML and parse elements with multiple child nodes into a record. My first question: Am I barking up the wrong tree using xml-enumerator for anything beyond fairly flat, basic XML? If not, can anyone direct me to some good code samples using xml-enumerator to parse more complicated data? If I am indeed barking up the wrong tree, what would you all suggest? Thanks, -- Michael Xavier http://www.michaelxavier.net LinkedIn <http://www.linkedin.com/pub/michael-xavier/13/b02/a26>

2 1

Re: [Haskell-cafe] External system connections
by Richard Wallace 10 Jul '11

10 Jul '11

On Sun, Jul 10, 2011 at 2:54 PM, Brandon Allbery <allbery.b(a)gmail.com> wrote: > On Sun, Jul 10, 2011 at 17:34, Richard Wallace > <rwallace(a)thewallacepack.net> wrote: >> Rather than a single separate thread that makes requests I was hoping to >> make several soap requests concurrently, rather than have them be made >> serially. I would only want to block other threads making soap request if >> one of them returns a response indicating the token they were using is no >> longer valid. > > Is there one shared token, or one per requesting thread, or some other > arrangement? There should be one shared token. > In either case, separation of concerns makes me think > the token handling belongs on the other end: a thread writes a > request down a Chan, a queue dispatcher thread reads it if there are > available workers and the token is available (with callers blocking > otherwise), dispatcher sends request to available worker. If the > worker finds the token is invalid, it calls back in to the dispatcher > with a token renewal request, which causes anything else that needs > that token to block as above, and itself blocks until a valid token is > returned. Ahhh... I see. That sounds like a much better plan. It also keeps the fact that the token is "mutable" confined to a single thread, the dispatcher thread. One thing I'd have to be careful to handle is iIf multiple worker threads find that the token is now invalid. In that case they would all send the token renewal request to the dispatcher and they would each try and do the re-auth. To avoid that, part of the token renewal request could be the used token. When the dispatcher does the token renewal, it checks if the used token is the same as the current token. If so, it does the token renewal. If not, it dispatches to the SOAP worker thread with the new token. > Another advantage of this is that adding more workers is > done in an obvious place (the queuer thread). > > That said, I still don't know enough details to say if that token > management implementation actually makes sense. I'd still go with the > worker/queuer thread setup, which is I think what you were pointed to > (the pool hackage). > Ok, I still don't see how the Pool package helps. I had assumed the pooled resource would be the token, so the size of the pool would be 1. Now that I rethink it, it seems like you are suggesting the resource is the worker threads. Is that right? When I read what you were talking about above with the dispatcher thread I had thought it would use forkIO to start the worker threads. The worker threads would read from a Chan that the dispatcher wrote to. In that way, the dispatcher doesn't have to worry about worker threads being available. Am I misunderstanding something? Thanks, Rich > -- > brandon s allbery allbery.b(a)gmail.com > wandering unix systems administrator (available) (412) 475-9364 vm/sms >

2 4