November 2008 - Haskell-Cafe

Need help with VXML again (fun deps and forall types)
by Marc Weber 02 Nov '08

02 Nov '08

Some time I've announced that I'm working on VXML, a validating xml library. The use case which makes trouble is elem+ (one or more) <!ELEMENT root (a|b|(c,d+))*> This example is encoded in this way: root -> St 1 id :1 endable : True a -> St 1 b -> St 1 c -> St 12 id :11 endable : True (a|b|c) -> St 1 d -> St 11 id :12 endable : False d -> St 11 to be read as: When creating a new root element start with state 1, then expect one of a,b,c subelemnts. If subelement c is added continue with state 12. The element may not be finalized (endable false because a "d" is expected). Following that we end in a loop at state 11 which is endable when only adding more d subelemnts. in VXML it looks like this print $ fStr $ runRoot $ vdo -- forceElements c e d e -- first, result has state 12 A d e -- second, result has state 11 X d e -- thrd, result has state 11 d e -- fourth, result has state 11 Y -- ... Now I'd like to do something convinient such as foldr1 (>>) print $ [1..10] I've called the corresponding function in VXML vxmlgtgt because it can be used like a monad and even do notation is supported using the vdo cpp macro rebinding (>>), (>>=) and return. Obviously I can only use foldr from X up to Y because A has a different return type. If you download the latest version of the library (git clone git://mawercer.de/vxml; git checkout fc160ab # is master branch ) you see that it actually works quite fine -- helper function: vxmlSeqPlus_ (f,fl) = f `vxmlgtgt` (foldr1 vxmlgtgt fl) -- usage example from testSimple.hs, note that both (d e) have different types vxmlSeqPlus_ ((d e), replicate 9 (d e)) d is actually a function creating the d element requiring a function as first argument which adds attrubutes and subelemnts (e is a nop here) This all makes d having a type which looks rather complicated: el*: the result type (String only in the current implementation) data VXML st el_ st2 el2_ st3 el3_ a = VXML { runVVXML :: (PT st el_ -> PT st2 el2_) -- [1] -> (a, PT st el_ -> PT st3 el3_) -- [2] } [1] : st -> st2 : The function which is passed [2] : st -> st3 : The type of function which is returned taking a function modyfiying the parent and adding "d" resulting in st3 (st3 is either State12 in A, or State11 in Y talking about the example given above) Its even getting more interesting now: Because I'd like to use different result types (String, ByteString, ...) I've used a type var to represent that type. I've called them el el2 el3 etc. When finally creating the document by using runRoot the result types propagates through the xml tree by functional dependencies. An example is the AddElT class which actually does add a subelement: class AddElT est el_ estc elc_ est2 el2_ | est estc -> est2 -- result state is determined by parent and child element state , est est2 estc el2_ -> el_ -- the result type of child and parent privious sibling are determined by the el2_ return type and the element states , est est2 estc el2_ -> elc_ where addElT :: PT est el_ -> PT estc elc_ -> PT est2 el2_ The instance has constraints like this determining el_ elc_ and st2 instance ( , DetermineElAddEl (NYV (Element elType AttrsOk st hchs)) el2 cest2 elc2 (NYV (Element elType AttrsOk st2 HTrue)) el3 , Consume st (Elem celType) st2 [..] ) => AddElT [..] Determining states form leafs to the root then propagating String or ByteString result type form the root to the leaf depending on states works fine until I start trying to use shortcut for the foldr1 example above. Instead of vxmlSeqPlus_ ((d e), replicate 9 (d e)) I'd like to write this. Of course the lamba here is polymorphic because it must return State 12 the first time and State 11 in the following cases. vxmlMapSeqPlus_ (\_ -> d e) [1..10] -- Ex I It's implementation is straight forward: vxmlMapSeqPlus_ f (x:xs) = vxmlSeqPlus_ (f x, map f xs) vxmlMapSeqPlus_ _ [] = error "vxmlSeqPlus has been called with empty list" My attempt to assign a type looks like this: vxmlMapSeqPlus_ :: ( VXMLMonad m st el st2 el2 st3 el3 st3 el3 , VXMLMonad m st el st3 el3 st3 el3 st3 el3 ) => (forall st' elA st'' elB . t -> m st el st' elA st'' elB ()) -> [t] -> m st el st2 el2 st3 el3 () vxmlMapSeqPlus_ f (x:xs) = vxmlSeqPlus_ (f x , map f xs) vxmlMapSeqPlus_ _ [] = error "vxmlSeqPlus has been called with empty list" where class VXMLMonad m st el_ st2 el2_ st3 el3_ st4 el4_ where vxmlgtgt :: m st el_ st2 el2_ st3 el3_ a -> m st el_ st3 el3_ st4 el4_ b -> m st el_ st2 el2_ st4 el4_ b vxmlgtgt a b = vxmlbind a $ const b vxmlbind :: m st el_ st2 el2_ st3 el3_ a -> (a -> m st el_ st3 el3_ st4 el4_ b) -> m st el_ st2 el2_ st4 el4_ b However when compiling the example (Ex I) there are a bunch of errors telling me that ghc can't find the matching instances caused by missing specialization of st.. That is ghc does no longer determine the resulting state based on parent and previous childs. Without state it can't propagate the el type ... You can see both examples in testSimple.hs vxmlSeqPlus_ ((d e), replicate 9 (d e)) vxmlMapSeqPlus_ (\n -> d e ) [1..10] So my question is: The second line does work fine, the first one dosen't. How to write vxmlMapSeqPlus_ so that I can compile the example? vxmlMapSeqPlus_ (\n -> d e ) [1..10] (d e) `vxmlgtgt` (foldr1 vxmlgtgt $ map (const $ d e) [2..10]) If you want to try this with ghc older than 6.10 you'll have to rewrite the vdo notation using vxmlbind and vxmlgtgt.. Do you have any idea how to make this work as expected? That's the last issue preventing me from trying to use it in real life projects. Sincerly Marc Weber

1 0

Newbie on instance of Monad
by Mauricio 02 Nov '08

02 Nov '08

Hi, After a lot of thinking, I can't get what I am doing wrong in this code: ------ data ( RandomGen g ) => RandomMonad g a = RandomMonad (g -> a) instance Monad (RandomMonad g) where return = RandomMonad . const RandomMonad f1 >>= f2 = RandomMonad f3 where f3 a = f2f1 a (next a) RandomMonad f2f1 = f2 . f1 ------ I get this error message: Could not deduce (RandomGen g) from the context (Monad (RandomMonad g)) arising from a use of `RandomMonad' at src/encherDB.hs:10:11-21 Possible fix: add (RandomGen g) to the context of the type signature for `return' In the first argument of `(.)', namely `RandomMonad' In the expression: RandomMonad . const In the definition of `return': return = RandomMonad . const but I'm not smart enough to understand what it means. Thanks a lot, Maurício

3 4

Memory efficiency questions for real-time graphics
by T Willingham 01 Nov '08

01 Nov '08

As my first Haskell exposure, I've been working through Real World Haskell. I am considering converting some of my C++ graphics libraries to Haskell. I've done a fair amount of googling on the subject, however I haven't quite been able to find clear answers to some of following issues. (1) Using an OpenGL vertex array (a contiguous chunk of memory which is handed to the graphics card) is important. I see the source code of Frag does this, so it looks like we're good. Check. (2) In-place modification of the vertex array is important. Every vertex changes on each frame update. And we always want more vertices. (3) Growing and shrinking the vertex array efficiently is important. Here the behavior of C++ std::vector happens to be ideal. When growing, extend the array in-place if possible (using reserved space if any), otherwise allocate a new chunk ("amortized constant time"). When shrinking, do nothing but record the smaller size; the unused memory chunk is reserved for possible future growth. (4) Doing little to no allocations each frame update is important. In the current C++ version, zero allocations occur during a normal frame update. When the vertex array changes, that is the only allocation which happens. To give a context for all of this, I am applying a non-linear transformation to an object on every frame. (Note: non-linear, so a matrix transform will not suffice.) The object is described by a certain function, and is generated from a 3D domain grid. The user can change the resolution of the grid on the fly, while the object is moving. (Hence the need for grow/shrink efficiency.) Given that (1) is out of the way, what's the best I expect from Haskell concerning (2)-(4)? Thanks, T. Willingham

5 11

An irritating Parsec problem
by Andrew Coppin 01 Nov '08

01 Nov '08

I like Parsec. I use it for everything. But it does have one irritating problem. Consider the following parser: expressions = many1 expression Suppose this is the top-level parser for my language. Now suppose the user supplies an expression with a syntax error half way through it. What I *want* to happen is for an error to be raised. What *actually* happens is that Parsec just ignores all input after that point. So if "+" is not a valid token, but the user writes x = 1; y = 2; z = 3 + z; w = 4; then what my program receives back is "x = 1; y = 2; z = 3", as if everything parsed successfully. But actually it has ignored half the input! o_O Does anybody know how to fix this irratiting quirk? I can see why it happens, but not how to fix it.

6 11

Haskell Weekly News: Issue 91 - November 1, 2008
by Brent Yorgey 01 Nov '08

01 Nov '08

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20081101 Issue 91 - November 01, 2008 --------------------------------------------------------------------------- Welcome to issue 91 of HWN, a newsletter covering developments in the [1]Haskell community. Announcements blas version 0.6. Patrick Perry [2]announced a [3]new version of the Haskell BLAS bindings, now with support for the ST monad! darcs hacking sprint #1 (report). Eric Y. Kow [4]summarized the [5]progress made during the darcs hacking sprint last weekend. Looks like exciting stuff! Much more detail and links can be found in Eric's original email. LAST CALL: Haskell Communities and Activities Report. Janis Voigtlaender [6]is extending the submission deadline for the 15th edition of the Haskell Community and Activities Report by a few days. If you haven't already, please [7]write an entry for your new project or update your old entry. Data.TCache 0.5.1. Alberto G. Corona [8]announced the release of [9]Data.TCache, which implements a transactional cache with configurable persistence. It tries to simulate Hibernate for Java or Rails for Ruby; the main difference is that transactions are done in memory trough STM. multirec-0.1. Andres Loeh [10]announced the release of the [11]multirec package, which provides a mechanism to talk about fixed points of systems of datatypes that may be mutually recursive. On top of this representations, generic functions such as the fold or the Zipper can then be defined. Making 'Super Nario Bros.' in Haskell. Korcan Hussein [12]linked to a [13]super mario brothers clone which was [14]written in Haskell! Chart-0.9. Tim Docker [15]announced the 0.9 release of the [16]Chart library, a library for drawing 2D charts. Publication of InputYourData.com + Project Announcement. Enzo Haussecker [17]announced the publication of [18]InputYourData.com, an online tool, written in Haskell, for financial, mathematical and scientific calculations. Enzo also described an idea to create a similar website where web applications are created by the user. If you are intrigued by this project and have substantial experience in designing Haskell-based web applications, please send Enzo your resume and a brief summery of why you are interested. Blog noise [19]Haskell news from the [20]blogosphere. * Mark Jason Dominus: [21]Atypical Typing. Mark describes his OOPSLA talk about Haskell's type system. * Eric Kow (kowey): [22]official darcs blog!. * Ben Moseley: [23]2 Minute intro to Associated Types / Type Families. * Ivan Lazar Miljenovic: [24]Honours + LXDE. Ivan discusses the status of his Haskell-oriented Mathematics Honours thesis. * Jason Dagit: [25]Darcs Hacking Sprint - Summary from Portland Team. * Eric Kow (kowey): [26]darcs hacking sprint - Team Brighton Day 2. * Dan Piponi (sigfpe): [27]Operads and their Monads. Quotes of the Week * lispy: I just wanted to make sure that this was illegal first * quicksilver: it doesn't entirely help that SQL is a series of broken standards layered over very poor decisions by large corporations * Baughn: SingInTime> hello world <Baughn> SingInTime: Type mismatch: Expected type: IRC [a], inferred type: IO () About the Haskell Weekly News New editions are posted to [28]the Haskell mailing list as well as to [29]the Haskell Sequence and [30]Planet Haskell. [31]RSS is also available, and headlines appear on [32]haskell.org. To help create new editions of this newsletter, please see the information on [33]how to contribute. Send stories to byorgey at cis dot upenn dot edu. The darcs repository is available at darcs get [34]http://code.haskell.org/~byorgey/code/hwn/ . References 1. http://haskell.org/ 2. http://article.gmane.org/gmane.comp.lang.haskell.cafe/47117 3. http://quantile95.com/2008/10/31/ann-blas-bindings-for-haskell-version-06/ 4. http://article.gmane.org/gmane.comp.lang.haskell.cafe/47114 5. http://blog.darcs.net/2008/10/darcs-hacking-sprint-1-report.html 6. http://article.gmane.org/gmane.comp.lang.haskell.cafe/47078 7. http://www.haskell.org/pipermail/haskell/2008-October/020651.html 8. http://article.gmane.org/gmane.comp.lang.haskell.cafe/47016 9. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/TCache 10. http://article.gmane.org/gmane.comp.lang.haskell.general/16574 11. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/multirec 12. http://article.gmane.org/gmane.comp.lang.haskell.general/16572 13. http://uk.youtube.com/watch?v=gVLFGQGRsDw 14. http://svn.coderepos.org/share/lang/haskell/nario/ 15. http://article.gmane.org/gmane.comp.lang.haskell.general/16570 16. http://dockerz.net/software/chart.html 17. http://article.gmane.org/gmane.comp.lang.haskell.general/16550 18. http://inputyourdata.com/ 19. http://planet.haskell.org/ 20. http://haskell.org/haskellwiki/Blog_articles 21. http://blog.plover.com/talk/atypical-typing.html 22. http://koweycode.blogspot.com/2008/10/official-darcs-blog.html 23. http://nattermorphisms.blogspot.com/2008/10/2-minute-intro-to-associated-ty… 24. http://ivanmiljenovic.wordpress.com/2008/10/29/honours-lxde/ 25. http://blog.codersbase.com/2008/10/28/darcs-hacking-sprint-summary-from-por… 26. http://koweycode.blogspot.com/2008/10/darcs-hacking-sprint-team-brighton-da… 27. http://sigfpe.blogspot.com/2008/10/operads-and-their-monads.html 28. http://www.haskell.org/mailman/listinfo/haskell 29. http://sequence.complete.org/ 30. http://planet.haskell.org/ 31. http://sequence.complete.org/node/feed 32. http://haskell.org/ 33. http://haskell.org/haskellwiki/HWN 34. http://code.haskell.org/~byorgey/code/hwn/

1 0

ANN: blas version 0.6
by Patrick Perry 01 Nov '08

01 Nov '08

New version of BLAS bindings out. Now with support for the ST monad! This breaks backwards compatibility, unfortunately. More info (and some sample code) here: http://quantile95.com/2008/10/31/ann-blas-bindings-for-haskell-version-06/ Also, if you want to help, please let me know. There is plenty of work to do. Patrick

2 1

Why 'round' does not just round numbers ?
by L.Guo 31 Oct '08

31 Oct '08

Hi all: I just read about definitions of Prelude [1], and noticing that. In 6.4.6 Coercions and Component Extraction, it discribes like this: "round x returns the nearest integer to x, the even integer if x is equidistant between two integers." I think this is unresonable. then try it in GHC 6.8.3. Prelude> round 3.5 4 Prelude> round 2.5 2 Is there any explanation about that ? [1] The Haskell 98 Report: Predefined Types and Classes http://haskell.org/onlinereport/basic.html Regards -------------- L.Guo 2008-10-27

23 50