- Haskell-Cafe - Haskell.org

Re: Monads and constraint satisfaction problems (CSP)
by Greg Meredith 31 May '07

31 May '07

Brandon, Jeremy, et al, Thanks for the pointers. The paper by OlegK, et al, articulates exactly the structure i was noticing, except that i was coming at it from the other end. i was noticing that a wide range of these CSP-style problems could be decomposed into a trivial monad (e.g., list, multiset, set) and some additional search machinery (over which a good solution should be parametric). They show how to add a reasonable upper limit on the search machinery to any monad. Best wishes, --greg Date: Thu, 31 May 2007 11:36:55 -0700 > From: "Jeremy Shaw" <jeremy.shaw(a)linspireinc.com> > Subject: Re: [Haskell-cafe] Monads and constraint satisfaction > problems (CSP) > To: "Greg Meredith" <lgreg.meredith(a)biosimilarity.com> > Cc: haskell-cafe <haskell-cafe(a)haskell.org> > Message-ID: <ejkwj0vs.wl%25jeremy.shaw(a)linspireinc.com> > Content-Type: text/plain; charset=US-ASCII > > At Thu, 31 May 2007 10:42:57 -0700, > Greg Meredith wrote: > > > BTW, i think this could have a lot of bang-for-buck because the > literature i > > read exhibited two basic features: > > > > - the "standard" treatments (even by CS-types) are decidedly not > > compositional > > - the people in the field who face industrial strength csp problems > > report that they have to take compositional approaches because the > problems > > are just too large otherwise (both from a human engineering problem > as well > > as a computational complexity problem) > > This paper describes a non-monadic, compositional method for solving CSPs: > > > http://www.cse.ogi.edu/PacSoft/publications/2001/modular_lazy_search_jfp.pdf > > There is also the LogicT monad transformer: > > http://okmij.org/ftp/Computation/monads.html > > j. > -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

1 0

New book: Real-World Haskell!
by dons＠cse.unsw.edu.au 31 May '07

31 May '07

Bryan O'Sullivan, Don Stewart and John Goerzen are pleased, and frankly, very excited to announce that were developing a new book for O'Reilly, on practical Haskell programming. The working title is Real-World Haskell. The plan is to cover the major techniques used to write serious, real-world Haskell code, so that programmers can just get to work in the language. By the end of the book readers should be able to write real libraries and applications in Haskell, and be able to: * design data structures * know how to write, and when to use, monads and monad transformers * use Haskells concurrency and parallelism abstractions * be able to write parsers for custom formats in Parsec. * be able to do IO and binary IO of all forms * be able to bind Haskell to foreign functions in C * be able to do database, network and gui programming * know how to do exception and error handling in Haskell * have a good knowledge of the core libraries * be able to use the type system to track and prevent errors * take advantage of tools like QuickCheck, Cabal and Haddock * understand advanced parts of the language, such as GADTs and MPTCs. That is, you should be able to just write Haskell! The existing handful of books about Haskell are all aimed at teaching programming to early undergraduate audiences, so they are ill-suited to people who already know how to code. And while theres a huge body of introductory material available on the web, you have to be both tremendously motivated and skilled to find the good stuff and apply it to your own learning needs. The time has come for the advanced, practical Haskell book. Heres the proposed chapter outline: 1. Why functional programming? Why Haskell? 2. Getting started: compiler, interpreter, values, simple functions, and types 3. Syntax, type system basics, type class basics 4. Write a real library: the rope data structure, cabal, building projects 5. Typeclasses and their use 6. Bringing it all together: file name matching and regular expressions 7. All about I/O 8. I/O case study: a DSL for searching the filesystem 9. Code case study: barcode recognition 10. Testing the Haskell way: QuickCheck 11. Handling binary files and formats 12. Designing and using data structures 13. Monads 14. Monad case study: refactoring the filesystem seacher 15. Monad transformers 16. Using parsec: parsing a bioinformatics format 17. Interfacing with C: the FFI 18. Error handling 19. Haskell for systems programming 20. Talking to databases: Data.Typeable 21. Web client programming: client/server networking 22. GUI programming: gtk2hs 23. Data mining and web applications 24. Basics of concurrent and parallel Haskell 25. Advanced concurrent and parallel programming 26. Concurrency case study: a lockless database with STM 27. Performance and efficiency: profiling 28. Advanced Haskell: MPTCs, TH, strong typing, GADTs 29. Appendices We're seeking technical reviewers from both inside and outside the Haskell community, to help review and improve the content, with the intent that this text will become the standard reference for those seeking to learn serious Haskell. If you'd like to be a reviewer, please drop us a line at book-review-interest(a)realworldhaskell.org, and let us know a little about your background and areas of interest. Finally, a very exciting aspect of this project is that O'Reilly has agreed to publish chapters online, under a Creative Commons License! Well be publishing chapters incrementally, and seeking feedback from our reviewers and readers as we go. You can find more details and updates at the following locations: * The web site, http://www.realworldhaskell.org/blog/welcome/ * The authors, http://www.realworldhaskell.org/blog/about/ * The blog, http://www.realworldhaskell.org/blog/ -- Bryan O'Sullivan, Don Stewart and John Goerzen.

36 51

Frisby grammars that have context
by Mark.Carroll＠Aetion.com 31 May '07

31 May '07

I've been playing with Text.Parsers.Frisby to see how it stacks against other options and, while it's been great so far, I am finding that I can't encode a grammar where what's acceptable depends on what's already been parsed in some nontrivial way. To take a simple example, imagine a grammar where the only lower-case letters that are acceptable are those where their upper-case equivalent occurred earlier in the text. In Parsec I'd code this sort of thing as, nextChar = do allowed <- getState char <- oneOf $ ['A'..'Z'] ++ allowed updateState (union [toLower char]) return char test = runParser (many1 nextChar) [] "" Is this supposed to not be possible in Frisby, or (quite likely) am I missing something that allows me to? I've thought about things like trying to fmap further calls to apply runPeg to rest, but I've not figured out a trick that will actually work. -- Mark

6 11

Monads and constraint satisfaction problems (CSP)
by Greg Meredith 31 May '07

31 May '07

All, All this talk about Mathematica and a reference to monadic treatments of backtracking reminded me that a year ago i was involved in work on a Mathematica-like widget. At the time i noticed that a good deal of the structure underlying LP, SAT and other solvers was terribly reminiscent of comprehension-style monadic structure. i think i asked Erik Meijer if he knew of any work done on this and posted to LtU, but nobody seemed to have understood what i was mumbling about. So, let me try here: does anybody know of references for a monadic treatment of constraint satisfaction? BTW, i think this could have a lot of bang-for-buck because the literature i read exhibited two basic features: - the "standard" treatments (even by CS-types) are decidedly not compositional - the people in the field who face industrial strength csp problems report that they have to take compositional approaches because the problems are just too large otherwise (both from a human engineering problem as well as a computational complexity problem) Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

3 3

Parse error on input "|"
by Akijmo 31 May '07

31 May '07

Hi everyone. I am new to this Forum, Haskell and i am german, so i am sorry for "noob" failures or spelling mistakes. I am currently learning for an informatic exam (11th class) and i tried to code a function to sum a polynom with a pair of polynoms... (I actually want to to code a polynomdivision in which i need this) But I get the parse error mentioned in the headline. It is referring to the first line of the case differentiation. Hopefully you can help me, here's the code: polyplusd :: Polynom -> (Polynom, Polynom) -> Polynom polyplusd [] p = p polyplusd p [] = p polyplusd p@((g1,e1):p1) (n, (q@((g2,e2):p2)) | g1>g2 = (g1,e1):(polyplusd p1 (n,q)) | g2>g1 = (g2,e2):(polyplusd p (n,p2)) | g1==g2 && e1+e2 /=0 =(g1, e1+e2):(polyplusd p1 (n,p2)) | otherwise = polyplusd p1 (n,p2) -- View this message in context: http://www.nabble.com/Parse-error-on-input-%22%7C%22-tf3847082.html#a108958… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 3

Network.HTTP+ByteStrings Interface--Or: How to shepherd handles and go with the flow at the same time?
by Thomas Schilling 31 May '07

31 May '07

Hello Cafe! I'd greatly appreciate any ideas/comments on the design of the interface to the Network.HTTP library with a LazyByteString (LBS) backend. As has been discussed previously on this list [1] lazy evaluation can complicate resource management, which is especially critical if resources are seriously limited--in this case network sockets and/or file handles. In [2] Oleg shows how we can use left folds as a general mechanism to traverse collections and shows that this is superior to cursors, generators or streams. I agree with his arguments, however, I still don't see that this can be a good interface for the http library. For a start, what should the collection type be? Word8, Char8, (strict) ByteString (BS)? Unless we get some kind of fusion for the first two we're pretty much stuck with the latter. The interface could look like this (untested): import Data.ByteString (ByteString) -- i.e., strict BSs import qualified Data.ByteString as BS handleRequest :: MonadIO m => Request -> a -> (ByteString -> a -> m (Either a a)) -> m a Ignoring error handling for now, this might be implemented as: handleRequest req seed processor = do a <- iter seed bodySize closeConnection req return a where iter seed 0 = return seed iter seed n = do let c = min chunkSize n bs <- liftIO $ readBlock req c -- calls BS.hGet handle c next <- processor bs seed case next of Left rslt -> return rslt Right seed' -> iter seed' (n-c) -- insert catchError stuff here (requires signature change, of course) This should work fine and if the 'processor' function does not hold on to the chunk would run in constant space. Unfortunately, this has a big disadvantage. Most operations on the returned data will probably be stream-like functions, such as parsing the data into some kind of tree. [2] shows a method how to convert enumerators to streams, but the used stream type data MyStream m a = MyNil (Maybe a) | MyCons a (m (MyStream m a)) is incompatible with [a] which is used by lazy ByteStrings due to the embedding of m. I also don't know if fusion can work on monads. My current suggestion would therefore be a less "save"[*] solution (again, untested and modulo error handling). -- | Execute the request and call @f@ with the returned response body. -- The socket will be closed immediately after @f@ terminates. You must therefore -- make sure that any data you might want to returned has to be forced, e.g. using -- (length . take) lbs withRequest :: MonadIO => Request -> a -> (LazyByteString -> a -> m a) -> m a The implementation would lazily read the contents (implemented as described in [3]) and forcing it would be left to the function parameter. E.g. getHTML :: String -> IO HTMLParseTree getHTML addr = do r <- mkRequest addr tree <- withRequest r emptyTree parseHTML seq tree $ return tree -- ! (I'm afraid this is necessary) tricky :: LazyByteString -> String -> IO LazyByteString -- result will not really be lazy trickyt str addr = do r <- mkRequest addr withRequest r L.empty dropNTake -- we might have to force the result here where dropNTake s _ = L.take 100000 . L.drop 100000 If these 'seq's are really necessary, then this would be a pretty hard to use interface. So, any ideas / suggestions ? / Thomas [*] .. "save" in the sense that it does not enforce certain behavior by means of the type signature or API design. [1] .. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/20528/focus=20635 [2] .. http://okmij.org/ftp/papers/LL3-collections-enumerators.txt [3] .. http://nominolo.blogspot.com/2007/05/networkhttp-bytestrings.html -- "Remember! Everytime you say 'Web 2.0' God kills a startup!" - userfriendly.org, Jul 31, 2006

7 8

Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
by Al Falloon 31 May '07

31 May '07

Mark T.B. Carroll wrote: > I don't know what the infamous "expression problem" is, nor am I > familiar with polymorphic variants or structural subtyping, but have you > looked at the Data.Generics.* stuff and Scrap Your Boilerplate papers? > They may be relevant. > The expression problem is "a new name for an old problem", basically being able to extend a data type and functions over the data type in seperate modules with no knowledge of each other. Here is a link to (I think) the original description: http://www.daimi.au.dk/~madst/tool/papers/expression.txt Structural subtyping is something like "duck typing" in dynamic languages, but checked at compile time. For records, it means that if you only access two labels then the function will work on any record that has those labels with those types, even if it may have more labels. For variants (or sum-types, or tagged unions, or whatever they are called in Haskell) it means that if your function can handle certain cases, then it can also handle values that range over less cases. So in pseudo-Haskell with imaginary subtyping: data Vertical a = U a | D a data Horizontal a = L a | R a data Direction a = #Vertical a | #Horizontal a -- borrowing ocaml syntax: this means that Direction shares constructors with Vertical and Horizontal getData :: Direction a -> a getData (U a) = a getData (D a) = a getData (L a) = a getData (R a) = a getLeftStick :: IO (Vertical Int) getRightStick :: IO (Horizontal Int) main = do { accel <- getLeftStick; print (getData accel) } So getData doesn't care that accel is Horizontal and not Direction because Horizontal is a sub-type of direction. Of course, in this syntax since you named the subtyping relationship its more technically nominal subtyping (like in traditional static OO languages) not structural subtyping (which figures out the subtype relationship from the structure automatically, so if we just reused the U,D,L, and R constructors in Direction). I have looked into SYB briefly. I will probably end up using it to keep the amount of code to a minimum, but it won't save me from having to define a different data type for each version of the AST if I want to preserve type safety.

1 0

equations and patterns
by mingli yuan 31 May '07

31 May '07

Hi, buddies. I am a newbie on Haskell. Recently I want to implement a simple Lattice in Haskell, but I met some difficulties. Scrap of the code is as below, but I met syntax error: > class Lattice e where > join :: e -> e -> e > meet :: e -> e -> e > > -- associative law > join x (join y z) = join (join x y) z > join (join x y) z = join x (join y z) The main problem is that mathematic equations is bi-directed, but in Haskell the pattern matching is only in one direction - from left to right. And only variables and constructors could be occur in the right side of the pattern matching. Seems mathematic axioms and pattern matching are different things. So how could I rewrite the equations to pattern matching? Which technique should I learn? Thanks for your help. Regards, Mingli

6 7

Building error Gtk2Hs under GHC 6.6.1 on Solaris 10 x86
by lebed 31 May '07

31 May '07

Hi, haskell-caffe! I'm trying to build Gtk2Hs 0.9.11 under GHC 6.6.1 on Solaris 10 x86: ./configure --with-hcflags=-O0 --disable-split-objs OK! gmake ........................ ........................ ........................ if test -f glib/libHSglib_a.deps; then touch glib/libHSglib_a.deps; else touch glib/libHSglib_a.deps; gmake glib/System/Glib/FFI.hs glib/System/Glib/UTFString.hs glib/System/Glib/Types.hs glib/System/Glib/GType.hs glib/System/Glib/GValue.hs glib/System/Glib/GValueTypes.hs glib/System/Glib/GObject.hs glib/System/Glib/Properties.hs glib/System/Glib/GError.hs glib/System/Glib/GList.hs glib/System/Glib/Signals.hs glib/System/Glib/MainLoop.hs glib/System/Glib/GTypeConstants.hs glib/System/Glib/GParameter.hs glib/System/Glib/StoreValue.hs glib/System/Glib.hs glib/System/Glib/Attributes.hs glib/System/Glib/Flags.hs; /usr/local/bin/ghc -M -optdep-f -optdepglib/libHSglib_a.deps -fglasgow-exts -O0 -fffi -iglib -package-conf package.conf.inplace -hide-all-packages -ignore-package glib -package base -package haskell98 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include glib/System/Glib/FFI.hs glib/System/Glib/UTFString.hs glib/System/Glib/Types.hs glib/System/Glib/GType.hs glib/System/Glib/GValue.hs glib/System/Glib/GValueTypes.hs glib/System/Glib/GObject.hs glib/System/Glib/Properties.hs glib/System/Glib/GError.hs glib/System/Glib/GList.hs glib/System/Glib/Signals.hs glib/System/Glib/MainLoop.hs glib/System/Glib/GTypeConstants.hs glib/System/Glib/GParameter.hs glib/System/Glib/StoreValue.hs glib/System/Glib.hs glib/System/Glib/Attributes.hs glib/System/Glib/Flags.hs; fi; gmake[1]: Entering directory `/usr/export/home/lebed/tmp/gtk2hs-0.9.11' ./mk/chsDepend -iglib:gtk:sourceview sourceview/Graphics/UI/Gtk/SourceView/Types.chs could not find {#import.chs on search path glib gtk sourceview gmake[1]: *** [sourceview/Graphics/UI/Gtk/SourceView/Types.dep] Error 1 gmake[1]: Leaving directory `/usr/export/home/lebed/tmp/gtk2hs-0.9.11' <no location info>: can't find file: glib/System/Glib/FFI.hs gmake: *** [glib/libHSglib_a.deps] Error 1 gmake: *** Deleting file `glib/libHSglib_a.deps' Where is my mistake? (I've got the same error under GHC 6.6 on Solaris 10 sparc.) -- View this message in context: http://www.nabble.com/Building-error-Gtk2Hs-under-GHC-6.6.1-on-Solaris-10-x… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 3

updating packages
by jeff p 31 May '07

31 May '07

Hello, I just moved to ghc-6.6.1and was wondering if there is an automatic way to update the various packages I had installed previously. thanks, jeff

2 1