- Haskell-Cafe - Haskell.org

Sliding Window functional data structure
by Okasaki, Christopher D CIV USA USMA 31 Aug '12

31 Aug '12

One possibility would be a random-access list (http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.5156) which is a kind of list of trees. Then 'add' is trivially O(1) and 'since' is trivially O(length result). The only tricky operation is purge, which naively would be O(N), where N is the length of entries. But that can be reduced using a kind of lazy deletion. Pair the random-access list with a single k, meaning "everything <= k is considered deleted, even if it is still physically present in the data structure". Purge would update the k and scan the list of trees, removing any tree with a root <= k. There are only a logarithmic number of trees, so this scan would be O(log N). In fact, it could be made O(log #remaining entries) by noting that, when one such tree is found, the list can just be chopped off there because all later trees should also be removed. The downside of lazy deletion is that you might use a bit more space than you need, because a portion of the last tree in the list might be logically deleted but still present. I would expect this effect to be minor in practice. Taking this approach, there is one situation that would require clarification, and possibly special handling: If you call purge with a k that is larger than the most recent add, thereby purging everything, are you later permitted to add a k' that is smaller than the purged k? This might be disallowed by extending the precondition of add. But if it is allowed, then should the new k' be affected by the previous purge, or not? It's easy to implement either way; it just depends on how you want to specify the desired behavior.

1 0

Sliding Window functional data structure
by Richard O'Keefe 31 Aug '12

31 Aug '12

Consider the following interface type Ord k => Sliding_Window k v entries :: Sliding_Window k v -> [(k,v)] The cost is expected to be linear in the length of the result. The pairs are listed in increasing order of k. add :: Ord k => k -> v -> Sliding_Window k v -> Sliding_Window k v precondition: all (< k) [k' | (k',_) <- entries q] The cost should be at most O((log . length . entries) q). post: entries (add k v q) = entries q ++ [(k,v)] since :: Ord k => k -> Sliding_Window k v -> [(k,v)] answers [(k',v) | (k',v) <- entries q, k' > k] The cost should be at most O((log . length . entries) q + length result) purge :: Ord k => k -> Sliding_Window k v -> Sliding_Window k v answers q' such that entries q' = [(k',v) | (k',v) <- entries q, k' > k] The cost should be at most O((log . length . entries) q + length [k' | (k',v) <- entries q, k' <= k]) Ignoring costs, this can obviously be done trivially using a list of pairs. Paying some attention to costs, it can also be done using some sort of balanced search tree. The data structure is close to a priority queue, but subtly different. I believe I can see how to do this in an imperative language using a Dijkstra-style array of pairs: add is amortised O(1) using the well known doubling strategy, thanks to the strictly increasing key requirement; since is a binary search followed by a segment copy; purge is a binary search followed by nilling out the now unwanted elements. By adapting the back-to-back pair of lists implementation of queues, we can obviously do add in O(1) and purge in O(1+#deleted items) time in a pure functional language. Thing is, there's a baffling array of data structures to examine (AVL, RB, 2-3, 2-3-4, 1-2-brother, finger ... trees) and I wondered if anyone had any idea what would be particularly good for this rather asymmetric problem.

3 2

lambda.haskell.org is on an mxtools blacklist
by jims＠stuttard.org 31 Aug '12

31 Aug '12

I had my subscription to haskell-cafe deleted because of intermittent bounces. I raised a support ticket with my ISP bluehost.com and they suggested the bounces might be because 78.46.100.80 is on the mxtoolbox blacklist as reported here: http://www.mxtoolbox.com/SuperTool.aspx?action=blacklist%3a78.46.100.180 HTH.

1 0

ANNOUCE: monad-task-0.1.0, GLFW-task-0.1.0 and a tutorial on invert the inversion of control
by Paul Liu 31 Aug '12

31 Aug '12

Graphics program often relies on system frameworks such as GLUT or GLFW to handle window and user input. But such frameworks often impose a rigid style of callback programming, or inversion of control. It is no secret that continuation monad can deal with this issue [1]. It is also known that concurrency can be naturally expressed as continuation monads [2], and a hybrid model of event and threads [3] brings the best of both worlds. But then I'm a bit surprised to find no single library on HackageDB that can deal with this issue. Further more, I wanted something that can escape the IO monad imposed by callbacks (and FFI) and be flexible. (no, monad-control is not a solution here). So I wrote a monad-task library to handle both co-operative threads (or co-routines) and event processing in a TaskT transformer. To demonstrate its usage, I also uploaded a GLFW-task library that helps to program task monad with GLFW, which contains a sample application if you unpack its source. I documented the rationales behind this work in a (rather length but runnable literal Haskell) tutorial "Invert the Inversion of Control", and welcome any suggestions and feedbacks. monad-task: http://hackage.haskell.org/package/monad-task GLFW-task: http://hackage.haskell.org/package/GLFW-task tutorial: http://www.thev.net/PaulLiu/invert-inversion.html [1]: Quick and dirty reinversion of control, Dan Piponi. http://blog.sigfpe.com/2011/10/quick-and-dirty-reinversion-of-control.html [2]: Functional Pearls: A Poor Man's Concurrency Monad, Koen Claessen, 1999 [3]: Combining Events And Threads For Scalable Network Services. Peng Li and Steve Zdancewic. PLDI, 2007. -- Regards, Paul Liu

1 0

createProcess running non-existent programs
by Niklas Hambüchen 30 Aug '12

30 Aug '12

I just came across the fact that running createProcess (proc "asdfasdf" []) with non-existing command "asdfasdf" returns perfectly fine handles. I would expect an exception. You can even hGetContents on stdout: You just get "". I find this highly counter-intuitive. Is this intended? Thanks Niklas PS: I checked how some other programming languages do this: Python: import subprocess; subprocess.call("asdfasdf", shell=False) OSError: [Errno 2] No such file or directory Ruby: exec("asdfasdf") Errno::ENOENT: No such file or directory - asdfasdf

9 14

Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
by Facundo Domínguez 30 Aug '12

30 Aug '12

Hi, > upd_noupd n = > let l = myenum' 0 n > in last l + length l This could be rewritten as > upd_noupd n = > let l n = myenum' 0 n > in last (l n) + length (l n) Or a special form of let could be introduced to define locally-scoped macros: > upd_noupd n = > let# l = myenum' 0 n > in last l + length l What's the strength of the {-# NOUPDATE #-} approach? Regards, Facundo > Date: Wed, 29 Aug 2012 10:20:21 +0200 > From: Joachim Breitner <breitner(a)kit.edu> > Subject: Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} > pragma > To: haskell-cafe(a)haskell.org > Message-ID: <1346228421.4271.9.camel@kirk> > Content-Type: text/plain; charset="iso-8859-15" > > Hi, > > Am Dienstag, den 28.08.2012, 18:16 -0400 schrieb Carter Schonwald: >> On Tuesday, August 28, 2012, Yves Par?s wrote: >> Monad? Simple strictness anotation is enough in that case: >> >> upd_noupd n = >> let l = myenum' 0 n >> h = head l >> in h `seq` last l + h > > darn, I though I changed my examples before posting to: > > upd_noupd n = > let l = myenum' 0 n > in last l + length l > > ("head" was a bad example because actually due to strictness analysis > and worker/wrapper transformation, GHC would yield good code even > without "`seq`"). > > In this case (which is actually the benchmarked case), reordering or > strictness annotations do not help. > > Greetings and sorry for the confusion, > Joachim > > > -- > Dipl.-Math. Dipl.-Inform. Joachim Breitner > Wissenschaftlicher Mitarbeiter > http://pp.info.uni-karlsruhe.de/~breitner

4 5

happstack simpleHTTP & state monad
by Corentin Dupont 30 Aug '12

30 Aug '12

Hi all, I'm trying to make a web server that manages its own state. The user can issue commands that modifies the state. I did like below but unfortunatly the state is not keep after a command is issued... What is the right way to do it? Is there any example sites with an internal state with happstack? *data Game = (the state of my game) type NomicServer = ServerPartT (StateT Game IO) launchWebServer :: Game -> IO () launchWebServer initialState = do putStrLn "Starting web server...\nTo connect, drive your browser to \" http://localhost:8000/Login\"" d <- getDataDir simpleHTTP' unpackStateT nullConf $ server d server :: FilePath -> ServerPartT (StateT Game IO) Response server d sh = mconcat [fileServe [] d, do decodeBody (defaultBodyPolicy "/tmp/" 4096 4096 4096) html <- implSite "http://localhost:8000/" "" nomicSite return $ toResponse html] unpackStateT:: Game -> UnWebT (StateT Game IO) Response -> UnWebT IO Response unpackStateT g w = evalStateT w g --handler for web routes nomicSite :: Site PlayerCommand (NomicServer Html) nomicSite = setDefault (Noop 0) Site { handleSite = \f url -> unRouteT (routedNomicCommands url) f , formatPathSegments = \u -> (toPathSegments u, []) , parsePathSegments = parseSegments fromPathSegments }* Thanks a lot, Corentin

2 2

paths in .cabal/config
by Semen Trygubenko 30 Aug '12

30 Aug '12

Dear Haskell-Cafe, I am wondering if there is a way to use variables in paths that appear in .cabal/config file? I have written a custom config file that I would like to share. However, my config file contains full paths s.a. world-file: /home/semen/.cabal/world etc. Is there any way I could make it less personal, e.g. world-file: /home/${HOME}/.cabal/world Many thanks, Sem -- Семен Тригубенко

1 0

Problem with searching mailing-lists archives
by damodar kulkarni 30 Aug '12

30 Aug '12

Hi Cafe, I was trying to search for the following Haskell functions in the mailing list archives. Here is a summary of the responses I have had from various servers upon searching various "valid and normally used" Haskell function identifiers. Responses from the http://www.mail-archive.com >>=<http://www.mail-archive.com/search?l=haskell-cafe%40haskell.org&q=%3E%3E%3D>, It seems the script searched for the string "&*gt*; &*gt*;" * -> *<http://www.mail-archive.com/search?l=haskell-cafe%40haskell.org&q=*+-%3E+*>There are 0 results. and so on... Responses from the http://search.gmane.org >>=<http://search.gmane.org/search.php?group=gmane.comp.lang.haskell.cafe&query…> Here, too, it seems the script searched for the string "&*gt*; &*gt*;" * -> *<http://search.gmane.org/?query=*+-%3E+*&author=&group=gmane.comp.lang.haske…> Here it seems the script searched for the string "&*gt*;" and so on... *Note: google badly fails to search these functions identifiers.* My current solution to this problem is: download compressed text archives and do a simple grep on it on my machine. But the archives up to year 2000 only are found at http://www.haskell.org/pipermail/haskell-cafe/. So, as an aside: Where do I find the earlier messages for downloading? Thanks, Damodar

1 0

Darcs fetches too little files
by Ramana Kumar 29 Aug '12

29 Aug '12

On Aug 29, 2012 10:56 PM, "Henk-Jan van Tuyl" <hjgtuyl(a)chello.nl> wrote: > > On Wed, 29 Aug 2012 23:10:24 +0200, Stefan Monnier < monnier(a)iro.umontreal.ca> wrote: > >>> Albert Einstein said: >>> Insanity: doing the same thing over and over again and expecting >>> different results. >>> I repeated the command today and it worked! >> >> >> So, did you expect the result to be different, or did you re-try just to >> confirm that it doesn't work? > > > The day after I tried the command the first time, I thought the result might be different; I have the experience that my browser crashes, and starting it again results in an immediate crash. Logging off and on again solves the problem. This might be because of a corrupted DLL or a corrupted data area of a DLL. > > The command failure could have also been caused by a problem at the server side. > > In conclusion: repeating the same thing could give different results. This depends on what counts as "the same". (There is a nice book called "The Subtlety of Sameness".) I'm surprised that as users of a language that makes a big deal out of referential transparency none of you have said that neither invoking the same command at a different time nor invoking a browser after changing context (logging in again) is doing the same thing. > > > Regards, > Henk-Jan van Tuyl > > > -- > http://Van.Tuyl.eu/ > http://members.chello.nl/hjgtuyl/tourdemonad.html > Haskell programming > -- > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0