August 2012 - Haskell-Cafe

Data.Text UTF-8 question
by jeff p 31 Aug '12

31 Aug '12

Hello, I have a sample file (attached) which I cannot read into Text: Prelude Control.Applicative> Data.Text.IO.readFile "foo" *** Exception: utf8.txt: hGetContents: invalid argument (invalid byte sequence) Prelude Control.Applicative> Data.Text.Encoding.decodeUtf8 <$> Data.ByteString.Char8.readFile "foo" "*** Exception: Cannot decode byte '\x6e': Data.Text.Encoding.decodeUtf8: Invalid UTF-8 stream So it seems that foo doesn't contain valid UTF-8. However, System.IO.UTF8 has no problem reading the data: Prelude Control.Applicative> System.IO.UTF8.readFile "foo" "3591,,,dihigma99h,1905,5,25,CUBA,,Matanzas,1971,5,20,CUBA,,Cienfuegos,Martin,Dihigo,,Mart\65533n Magdaleno Dihigo (Llanos),,190,74,R,R,,,,dihigma99,dihigma99,dihim001,dihigma99,dihigma99\r\n" Shouldn't these all have the same behavior? I am running on Mac OS X 10.8.1, with GHC 7.4.2 and text-0.11.2.3. thanks for any insight, Jeff

3 2

Is it worth adding Gaussian elimination and eigenvalues to REPA?
by KC 31 Aug '12

31 Aug '12

I realize if one wants speed you probably want to use the hMatrix interface to GSL, BLAS and LAPACK. Worth it in the sense of have a purely functional implementation. -- -- Regards, KC

2 1

Code review request - using ErrorT
by C K Kashyap 31 Aug '12

31 Aug '12

Dear gentle Haskellers, I'd appreciate it very much if you could please take a look the my code here and give me some feedback - https://github.com/ckkashyap/haskell-websocket/blob/master/src/lib/Net/WebS… I am particularly looking for advice around what would be a good type for a server handler function that does IO and needs to short circuit if it fails at any point also needs to thread a state along. I am considering this - ErrorT String (StateT Int IO) Data Regards, Kashyap

1 0

why do I need class context in declaring data constructor?
by Paul Liu 31 Aug '12

31 Aug '12

I had a toy program that encodes simply typed lambda in types. It used to work fine with GHC prior to 7.2. But now it no longer compiles. Here is a minimal fragment that demonstrates this problem. > {-# LANGUAGE GADTs, > MultiParamTypeClasses, > FlexibleInstances, > FlexibleContexts #-} > > data Abs env t v where > Abs :: g (a, env) h v -> Abs env (g (a, env) h v) (a -> v) > > class Eval g env t v where > eval :: env -> g env t v -> v > > instance Eval g (a, env) h v => > Eval Abs env (g (a, env) h v) (a -> v) where > eval env (Abs e) = \x -> eval (x, env) e The type Abs has 3 parameters: its environment, sub term (encoded in types), and type. The constructor Abs has 1 parameter: its sub term. The code loads fine in GHC 7.0.3. Here is the error reported by GHC 7.2.2 (and later): test.lhs:14:30: Could not deduce (Eval g1 (a1, env) h1 v1) arising from a use of `eval' from the context (Eval g (a, env) h v) bound by the instance declaration at test.lhs:(12,12)-(13,49) or from (g (a, env) h v ~ g1 (a1, env) h1 v1, (a -> v) ~ (a1 -> v1)) bound by a pattern with constructor Abs :: forall env (g :: * -> * -> * -> *) a h v. g (a, env) h v -> Abs env (g (a, env) h v) (a -> v), in an equation for `eval' at test.lhs:14:15-19 Possible fix: add (Eval g1 (a1, env) h1 v1) to the context of the data constructor `Abs' or the instance declaration or add an instance declaration for (Eval g1 (a1, env) h1 v1) In the expression: eval (x, env) e In the expression: \ x -> eval (x, env) e In an equation for `eval': eval env (Abs e) = \ x -> eval (x, env) e However, if I move the class context to the data constructor of definition, then it compiles fine in GHC 7.2.2 (and later): > data Abs env t v where > Abs :: Eval g (a, env) h v => g (a, env) h v -> Abs env (g (a, env) h v) (a -> v) But this is very troublesome because for every new class instance I want to make Abs of, I have to make a new class context to the data constructor. It totally defeats the purpose of making class instances to extend usage of data types. Did I missed a language extension when moving code from GHC 7.0.3 to GHC 7.2.2? What can I do to fix it for newer GHCs? -- Regards, Paul Liu

2 2

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 31 Aug '12

31 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