August 2007 - Haskell-Cafe

Re: [Haskell-cafe] IO within parser
by Sam Hughes 13 Aug '07

13 Aug '07

Malte Milatz wrote: > Sam Hughes <hughes(a)rpi.edu>, Sun, 12 Aug 2007 20:12:55 -0400: > [A parser like Parsec, with monad transformers:] >> $ darcs get http://samuelhughes.com/darcs/partran/ > > Is this related in any way to the following GSoC project? > > http://code.google.com/soc/2007/haskell/appinfo.html?csaid=B97EF4562EF3B244 > > No, I just wanted it for my own purposes. - Sam

1 0

Suffix tree
by Jon Harrop 13 Aug '07

13 Aug '07

Suffix trees are a data structure used to search for a substring of length "m" in a string of length "n" in O(m) time. Suffix trees can also be used for efficient approximate searches. This data structure is of particular importance in bioinformatics. Does anyone have any Haskell code implementing suffix trees? I'm particularly interested in high-performance construction. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

3 2

IO within parser
by Gregory Propf 12 Aug '07

12 Aug '07

I've been struggling with writing a parser that needs to parse include files within source files. So far I cannot get this to work (in reality to get work done I wrote a kludge that returns a list of include filenames to be run later in a pure IO function. I realized that this just amounted to creating my own half-assed monad system so I really don't want to use this approach). I have read the tutorials I could find on monad transformers but I still don't see what's going on. I'm using the Parsec parser library. Here's an simple example of what I've tried. I also tried using liftIO and got a message about needing to add an instance of MonadIO. This made more sense but the type of liftIO is baffling class Monad m => MonadIO m where liftIO :: IO a -> m a But how do you define this function? There is no constructor for "IO a" that you can "take apart". Anyway, here is the code that just uses lift. Keep in mind that the outer monad is just "GenParser Char st [Char]". I'm guessing this is wrong and I should have a transformer monad as the outer layer. But which one? and how to use it? pio = do { s <- many1 alphaNum; input <- lift (readFile s); return input; } go6 = runParser pio () "" "This is a test" ================================= ghc output from trying to load this is ================================= Couldn't match kind `* -> * -> *' against `(* -> *) -> * -> *' When matching the kinds of `GenParser Char :: * -> * -> *' and `t :: (* -> *) -> * -> *' Expected type: GenParser Char st Inferred type: t IO In a 'do' expression: lift (writeFile "Foo" s) ____________________________________________________________________________________ Fussy? Opinionated? Impossible to please? Perfect. Join Yahoo!'s user panel and lay it on us. http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7

4 3

Infinity v0.1
by Austin Seipp 12 Aug '07

12 Aug '07

Hello! Over the past couple of days I've been working on an IRC bot in the essence of lambdabot; that is, it should be extendable through plugins and plugins should be easy to write, modify and contribute. I also wanted the bot to be small in terms of LOC (as of 0.1, about ~360 including the two bundled plugins,) but still be usable. Well, now I have something to show for it, and I introduce infinity v0.1: http://austin.youareinferior.net/infinity-0.1.tar.gz (there is no darcs repo yet, although I have emailed someone about a possible account for darcs.haskell.org.) Everything from building to writing plugins should become fairly self evident from reading the README. You will need the hs-plugins to use it. As it stands, the bot is incredibly primitive and there are almost no plugins (I only wrote 'hello world' and 'goodbye world' plugins to test the code as it moved forward) as of yet, however, I had fun with this thing and I hope maybe someone could do something interesting with it. There're some parts of the code that I'm not particularly happy with. For the 0.2 release I have a couple of goals in mind: 1. To move the basic ad-hoc IRC parsing code (lots of drop and dropWhile and whatnot) to a more robust implementation such as parsec. This should hopefully clean up some of the code I'm not on good terms with. 2. To add support for in-situ reloading and re-compilation of modules, so you won't even have to restart the bot if you update a plugin. This will probably require some reworking of my threading code so that the environment stays safe and stable (STM?) 3. To move all of the built-in core commands to plugins as well; this will probably require encapsulating plugins in a monad (StateT) henceforth. I'm not exactly the most advanced haskell programmer ever born, but I enjoyed working on this code and while it isn't and probably won't ever be the next lambdabot, I hope someone can learn something from it or just have fun with it. If anybody would like to take the time to write a plugin or something for some interesting purpose, I would be happy to include it in the source tree (I'm sure you guys can come up with something more interesting than I can.) I would really appreciate any and all comments on the code. I still feel myself to be in an 'intermediate' area with Haskell, so anything you guys can add that would improve the code would be incredibly appreciated. PS: I've only tested this on an i386 linux box so if anybody here can confirm it works on other systems (bsd, solaris?) where hs-plugins is available, that would be awesome. Thanks! -- - Austin

2 1

howto install ghc-6.7.* ?
by Marc A. Ziegert 12 Aug '07

12 Aug '07

i just don't get it. please, can anybody explaim me how to do that? i tried it the last few days with ghc-6.7.20070807, ghc-6.7.20070809, and ghc-6.7.20070810. it always results in a broken library (without Prelude): # ghc-pkg list /usr/local/lib/ghc-6.7.20070810/package.conf: {ghc-6.7.20070810}, rts-1.0 i did this on my gentoo-i386-box (pretty old, takes 1h for quick build, 3.5h without mk/build.mk): T=20070810 tar xjf ghc-6.7.$T-src.tar.bz2 tar xjf ghc-6.7.$T-src-extralibs.tar.bz2 cd ghc-6.7.$T ( #echo BuildFlavour = quick #cat mk/build.mk.sample echo HADDOCK_DOCS = YES ) > mk/build.mk ./configure && ( time nice -n 19 make all install ) those extralibs seem to be installed in /usr/local/lib/ghc-6.7.20070810/lib/ but registered in ghc-6.7.20070810/driver/package.conf.inplace instead of /usr/local/lib/ghc-6.7.20070810/package.conf . - marc

4 3

towards a new foundation for set theory with atoms
by Greg Meredith 12 Aug '07

12 Aug '07

Haskellians, i have a particular interest in FM-set theory in that it simplifies a host of otherwise non-trivial aspects of programming language semantics, especially, fresh names. You can provide semantics without sets with atoms, but the functor category machinery is more than a little on the heavy side. The down side of FM-set theory is that it posits an infinite collection of atomic entities -- atomic in the sense that they have no observable internal structure. This poses a real problem for computational accounts. No where do we have an infinite supply of atomic entities. All our infinite collections need some finite presentation -- some basic starting structure and then a finite set of rules that say how to generate the rest. This is particularly important since the atoms have to come with a equality predicate. If the predicate cannot inspect internal structure, then the equality predicate is too big to hold in any finitely presentable computation. Thus, there's a little conundrum: how do you get all the conveniences of a set theory with atoms and still have a finite presentation? Here's one approach. The issue is that atoms cannot have internal structure observable by the set-theoretic operators, \in : Set -> Atom + Set -> Bool, and { - } : [Atom + Set] -> Set. That doesn't mean they can't have structure. Where would this structure come from? Well, it's related to another observation about sets: they're really collections of pointers. More specifically, the axiom of extensionality says that two sets are equal iff they have exactly the same members. Thus, wherever we see the set { } it's the same. Therefore, in { { }, { { } } } we see the very same set occurring in two locations. This is not very physical. These notions of location or identity must be more logical notions. And, one obvious way to resolve this is that what's "inside" the braces are references or pointers. We can start to formalize this naively using a simple grammar-nee type formulation. Ordinary sets can be specified like this Set ::= { Set* } for some appropriately infinite version of Kleene-star. (Note, this grammar is really sugar for a domain equation.) Now, if we want sets over references, we could modify the grammar, like this RSet ::= { Ref* } Ref ::= `Set*' R-sets only contain references and references point to (collections of) sets. Then, you can add a dereference operation to you theory to get back the sets being referenced. But, while under the quotes, the internal structure is not observable by the element-of and brace operators. Thus, from the point of view of these operators, they look like atoms. Note that as written, the quotes are serving a role isomorphic to the role of the braces. They are essentially two different collection operators that have been intertwined in an alternating manner. This alternation is in perfect correspondence with games semantics. We interpret { as opponent question, } as opponent answer, ` as player question, ' as player answer. This means that winning strategies for opponent yield sets while winning strategies for player yield references. The observation leads to a further generalization. Nothing restricts us to two kinds of collection operators. We could posit n different "colored" braces and element-of operators, written {i - i}, \in_i, for color i. Then we have the following specification for these sets Set(i) ::= {i Set(0 <= j < n : j <> i)* i} i have coded up (in my pidgin Haskell) a version for 3 colors and then shown how to do the von Neumann encoding of the naturals in this setting. The code can be found here: http://svn.biosimilarity.com/src/open/mirrororrim/rsets/trunk/MPSet.hs 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

2 3

Re: default for quotRem in terms of divMod?
by Henning Thielemann 12 Aug '07

12 Aug '07

On Sun, 12 Aug 2007, Lennart Augustsson wrote: > CPU design cannot be changed, because they implement well defined ISA. What is ISA? Why is it not possible to add CPU functions for `div` and `mod`? > The only processor I know of (NS 32k) with a different division is long > dead. If efficiency on current CPUs is the only advantage of `quot` and `rem`, then for future versions of Haskell I propose to fix these functions to the type Int rather than making them class methods. For non-machine types like Integer the efficiency argument does certainly not hold.

2 1

Re: Fw: [Haskell-cafe] IO within parser
by Gregory Propf 12 Aug '07

12 Aug '07

I noticed that StateT can enclose IO actions for instance. So you are saying the whole Parsec library would need to be rewritten as something like a ParsecT transformer monad for this to work? If this is the case I suppose I will stick with returning my list of include files. - Greg ----- Original Message ---- From: Bulat Ziganshin <bulat.ziganshin(a)gmail.com> To: Gregory Propf <gregorypropf(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Sent: Saturday, August 11, 2007 11:33:00 PM Subject: Re: Fw: [Haskell-cafe] IO within parser Hello Gregory, Sunday, August 12, 2007, 9:32:04 AM, you wrote: >> I've been struggling with writing a parser that needs to parse include >> files within source files. Parsec can't accomplish with without using unsafePerformIO because it's monad is pure. it's algorithmically impossible to have any i/o actions inside it. there was plans to rewrite Parsec in monad-transformer way and afair it was even one of GSOC projects -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com ____________________________________________________________________________________ Fussy? Opinionated? Impossible to please? Perfect. Join Yahoo!'s user panel and lay it on us. http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7

1 0

Fw: [Haskell-cafe] IO within parser
by Gregory Propf 12 Aug '07

12 Aug '07

Well the docs ( http://legacy.cs.uu.nl/daan/download/parsec/parsec.html ) hint that setInput and getInput are good for this. I can certainly how they *would* be - if I knew how to pull in files within the parse. Actually I use those functions to do multiple recursive passes but of course you already have the output from the first pass in the parser there. runParser only *looks* like it takes input from a file. Actually it just parses the string you give it and uses the filename arg for error messages only. You still need a way to pull the data into the string from the file. (Note: I accidentally sent this to Andrew instead of the list originally) ----- Original Message ---- From: Andrew Coppin <andrewcoppin(a)btinternet.com> To: haskell-cafe(a)haskell.org Sent: Saturday, August 11, 2007 1:25:16 PM Subject: Re: [Haskell-cafe] IO within parser Gregory Propf wrote: > I've been struggling with writing a parser that needs to parse include > files within source files. So far I cannot get this to work (in > reality to get work done I wrote a kludge that returns a list of > include filenames to be run later in a pure IO function. I realized > that this just amounted to creating my own half-assed monad system so > I really don't want to use this approach). I have read the tutorials > I could find on monad transformers but I still don't see what's going > on. I'm using the Parsec parser library. Here's an simple example of > what I've tried. I also tried using liftIO and got a message about > needing to add an instance of MonadIO. This made more sense but the > type of liftIO is baffling The fun part is that Parsec already has a feature for include files... (I can't remember where the heck it is or how you use it though.) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Fussy? Opinionated? Impossible to please? Perfect. Join Yahoo!'s user panel and lay it on us. ____________________________________________________________________________________ Choose the right car based on your needs. Check out Yahoo! Autos new Car Finder tool. http://autos.yahoo.com/carfinder/

2 1

Re: default for quotRem in terms of divMod?
by Henning Thielemann 12 Aug '07

12 Aug '07

Btw. is there any application, where 'quot' and 'rem' are needed? All occurrences of 'quot' and 'rem' I found in code so far were actually wrong and should have been 'div' and 'mod'. http://www.haskell.org/haskellwiki/Things_to_avoid#Forget_about_quot_and_rem

3 4