- Haskell-Cafe - Haskell.org

Annoucing alternative to Text.Regex
by Chris Kuklewicz 08 Mar '06

08 Mar '06

This message is cross-posted to haskell-cafe(a)haskell.org and libraries(a)haskell.org Hi, Working on the shootout (specifically http://shootout.alioth.debian.org/gp4/benchmark.php?test=regexdna&lang=all ), it was impossible to use Text.Regex since it was too slow (it would reach the timeout limit, such as an hour, where TCL takes 3.21 seconds ). So we had to work around this by implementing our own regex engine. I have tooled up an all-parsec version that I think can be a nearly drop-in-alternative to Text.Regex. I will describe it a bit and then ask for advice. It takes the string form of the regular expression and uses Parsec to create a (data Pattern) tree structure. This recognizes all of "man re_format" including back references, missing only the [[:>]] or [[<:]] extension (word boundaries). It also accepts new modifiers '?' and '+' to be used like "a*?" and "a*+" for lazy and possessive matching. The Pattern form is amenable to simplification, and some easy simplification are performed. Then the Pattern is transformed in a Parsec parser that will match the input (from the beginning only) and return all the captured sub-expressions. It also supports (get|set|update)UserState functions. It should return the longest match when all the pattern elements are greedy, i.e. no lazy or possessive modifiers are used. With lazy or possessive modifiers the longest alternative is used, but this may not be the longest overall match. (Parsec keeps track of line and column position, but not the number of characters, which had to be added.) Note that the pattern "(.)Q\1" can be used to match strings like "aQa", and "(a|b\1)+" matches all of "ababba". The Text.Regex compatibility code embeds the generated Parsec parser into more complicated parsers and runs them to emulate the different functions in the Text.Regex interface. It is possible to extend all of this in several ways: 1) Turn the Pattern into simpler parsec, e.g. if the expression captures are not needed 2) When possible, turn the Pattern into a faster DFA parser instead of Parsec 3) Create parsers that with different semantics than "longest match", e.g. left-biased 4) Creates parsers that return all matches 5) Employ smart optimizations for special forms of Pattern 6) With an earlier version, I made a proof of principle String -> ExpQ transformer that created Parsec at compile time using Template Haskell. This could be updated. Not done: testing. (If you have clever things to throw at it, pass them along). Not done: benchmarking (though it should usually beat Text.Regex). And now I want to ask for advice. If there is interest I could post the code somewhere, but I don't own a stable place to put it at the moment. Is there a canonical place on the net to put small Haskell modules (28 kB uncompressed) ? Is there some darcs-repository I could insert it into ? Also, is there a library style guide somewhere with best practices?

2 2

RE: [Haskell] Re: Trying On Learn Haskell Web Server
by Bayley, Alistair 08 Mar '06

08 Mar '06

[Moving to café] > From: haskell-bounces(a)haskell.org > [mailto:haskell-bounces@haskell.org] On Behalf Of Mattias Bengtsson > > > > > I think that continuation-based web session state management, ala > > > Smalltalk/Seaside, would be a very natural fit for a > Haskell framework -- all > > > handled by a "Web session monad", maybe. (Or maybe I > just don't know what I'm > > > talking about ;) > > > > This is by far the biggest drawback of HSP today. There is no > > high-level support for continuations (other than explicitly defined > > continuations at top level). > > I would really like to know exactly what this means. Are there any > examples or papers on this? I have a lot of links... which I'll feel free to spam you and the list with :-) Here a list of continuation-based web-frameworks that I know about; there may be more: Cocoon (Java + Javascript) http://cocoon.apache.org/ Borges (Ruby) http://borges.rubyforge.org/ Wee (Ruby) http://www.ntecs.de/blog/Wee WASH (Haskell) http://www.informatik.uni-freiburg.de/~thiemann/haskell/WASH/ Seaside (Smalltalk) http://www.seaside.st/ PLT Scheme (Scheme) http://www.plt-scheme.org/ (can't find the actual library) Siscweb (Scheme) http://siscweb.sourceforge.net/ Uncommon Web (Common Lisp) http://common-lisp.net/project/ucw/ Rife (Java) http://rifers.org One of the first people (but not the only, I think) to recognise that continuations were a good way of modelling web interations was Christian Queinnec: http://www-spi.lip6.fr/~queinnec/PDF/www.pdf http://www-spi.lip6.fr/~queinnec/Papers/webcont.ps.gz Probably the best-known such framework is Seaside (ironic, as Smalltalk doesn't natively support continuations, AFAIK): http://www.seaside.st/ Phil Wadler is also doing something along these lines in Links, I believe: http://homepages.inf.ed.ac.uk/wadler/links/ Excellent summary of problems with REST and continuations (Dave Roberts): http://www.findinglisp.com/blog/2004/11/web-application-design-rest-of-stor… IBM article, mainly about Cocoon - a Java + Javascript framework: http://www-128.ibm.com/developerworks/java/library/j-contin.html More hype: http://phirate.exorsus.net/wiki/doku.php?id=web_development_in_2005 http://phirate.exorsus.net/wiki/doku.php?id=further_discussion_of_continuat… http://phirate.exorsus.net/wiki/doku.php?id=sessions_and_state Bill Clementson's postings (he's a Lisper): http://bc.tech.coop/blog/041229.html Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

1 0

ANN: pass.net is live in haskell!
by S. Alexander Jacobson 08 Mar '06

08 Mar '06

I just launched http://pass.net. Pass.net lets website use the user's email domains to authenticate. The default implementation is in Haskell and is now live. -Alex- PS I am at ETech right now and will be at SXSW next week. If you are here, please say hi. ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

1 0

Can't uninstall GHC or prepare SOE installation on OS X
by Xavier Elizalde 07 Mar '06

07 Mar '06

I've installed the Glasgow Haskell Compiler 6.4.1 for OS X on my system. I have The Haskell School of Expression book and the instructions for setting up and running the SOE software seem to have a different configuration compared to GHC 6.4.1. Namely, it's meant to use X11 and locations for files are different. I presume the easiest thing to do is uninstall GHC 6.4.1 and install the binaries available on the SOE site. I've attempted to run the uninstall AppleScript for GHC, but I get a "Finder got an error: Can't get item "GHC-6.4.pkg" of folder "Receipts" of folder "Library" of startup disk. (-1728)" error. What should I do? If I'm going to uninstall it by hand, I don't know which files need to be removed. And I also wonder if it is actually preferable to somehow keep GHC and just configure it to work with the SOE by installing the GraphicsLib library and getting it to use X11. And I'm not clear about how I should do that. Or does the GHC already have GraphicsLIb as part of it? If so, shouldn't it launch an X11 Xterm terminal rather than the standard OS X Terminal? Xavier

1 0

PrefixMap: code review request
by David F.Place 07 Mar '06

07 Mar '06

Hi, I'm a newish Haskell hacker with way too much experience hacking Lisp. At first, I found my Haskell code looking very lisp-y. I think my code is becoming more idiomatic haskell. I would be very grateful to anyone who would take a glance at the code below and point out any un-idiomatic usages that jump out. It's a small module from a program which looks for palindromes in a list of words. Thanks very much. Cheers, David \begin{code} {-# OPTIONS -O2 -optc-O3 #-} module PrefixMap (PrefixMap,fromDistinctAscPairList,searchMap) where import Data.List import qualified Data.Map as Map import Test.HUnit \end{code} The PrefixMap datastructure implements a Prefix Tree which allows a key/value relationship. \begin{code} data PrefixMap k v = Node (Maybe v) (Map.Map k (PrefixMap k v)) deriving (Show) \end{code} A PrefixMap is built from an alphabet enumerating the possible constituents of keys and a list of pairs of keys and objects. A key is a string of elements of the alphabet. The list must be distinct and in ascending order. The constraint is not checked. \begin{code} fromDistinctAscPairList :: Ord k => [k]->[([k],v)]->PrefixMap k v fromDistinctAscPairList alphabet pairList = build alphabet Nothing (partList pairList alphabet) partList :: Ord k => [([k],v)]->[k]->[(k,[([k],v)])] partList pairs alphabet = reverse . fst $ foldl' f ([],pairs) alphabet where f (result,pairs) l = (result',rest) where (part,rest) = span ((==l) . head . fst) pairs result' = if null part then result else (l,part):result build :: Ord k => [k]->(Maybe v)->[(k,[([k],v)])]->(PrefixMap k v) build alphabet val pairs = Node val $ Map.fromDistinctAscList treePairs where treePairs = [(c,mkITree l)|(c,l)<-pairs] mkITree l = build alphabet x (partList l' alphabet) where (x,l') = findNode $ snipKeys l snipKeys :: Ord k => [([k],v)]->[([k],v)] snipKeys l = [(k,v) | (_:k,v) <- l] findNode :: Ord k => [([k], v)] -> (Maybe v, [([k], v)]) findNode l = if null suffix then (Nothing,l) else ((Just $ snd.head $ suffix),prefix++(tail suffix)) where (prefix,suffix) = span (not.null.fst) l \end{code} searchMap applies a function to each object in the PrefixTree that is on the path specified by the key and the subtree below it and returns a list of the results. \begin{code} searchMap :: Ord k => (v -> vv) -> [k] -> PrefixMap k v -> [vv] searchMap f [] t = walk f t [] searchMap f (k:ks) (Node v al) = maybe rest ((:rest) . f) v where rest = maybe [] (searchMap f ks) (Map.lookup k al) walk :: (a -> b) -> PrefixMap k a -> [b] -> [b] walk f (Node Nothing al) z = Map.fold (walk f) z al walk f (Node (Just x) al) z = Map.fold (walk f) (f x:z) al test1 = TestCase (do input <- readFile "words.txt" let dict = words input pairs = zip dict dict alpha = ['a'..'z'] ftree = fromDistinctAscPairList alpha pairs fAnswer = searchMap id "assert" ftree rtree = fromDistinctAscPairList alpha $ sort $ zip (map reverse dict) dict rAnswer = searchMap id "tressa" rtree assertEqual "forward search" ["as","ass","assertedly","asserted", "asserters","asserter","asserting", "assertions","assertion","assertively", "assertivenesses","assertiveness", "assertive","assertors","assertor", "asserts","assert"] fAnswer assertEqual "reverse search" ["reassert","overassert","assert"] rAnswer ) tests = TestList [TestLabel "Tree Test" test1] \end{code} \end{document} -------------------------------- David F. Place mailto:d@vidplace.com

16 38

mediawiki syntax highlighting plugins
by Johannes Ahlmann 07 Mar '06

07 Mar '06

hi, i've noted that the new haskellwiki has dropped syntax highlighting support for haskell code fragments. while i think that full highlighting might be overkill, at least different color markup of code and comments would certainly be nice. investigating the options for syntax highlighting in mediawiki i found the following two extensions using GNU enscript: http://www.wickle.com/wiki/index.php/Syntax_Highlight_extension http://www.milab.is.tsukuba.ac.jp/~bushuhui/index.php?title=Enhanced_syntax… where the second is an alteration of the first, with haskell support already added. an alternative would be geshi (http://qbnz.com/highlighter/) for which a mediawiki plugin also exists (http://meta.wikimedia.org/wiki/GeSHiHighlight) but it says on the geshi site "GeSHi supports PHP5 and Windows". and i'm not clear whether they mean it _also_ supports those options or exclusively. it would be cool if one of the wiki maintainers could look into this matter and possibly install/setup one of the above extensions. thank you, Johannes Ahlmann

3 2

Comparing programs
by Harry Chesley 07 Mar '06

07 Mar '06

This is more of an algorithm question than a language question, but any insights would be much appreciated. The problem is to input a series of programs and find previous occurrences of the same algorithm. The programs consist of a set of input parameters (a, b, c, ...), and a set of side-effect-free functions (f, g, h, ...). Since the functions are side-effect-free, they can be reordered without changing the algorithm ("f(a), g(b)" is the same as "g(b), f(a)"). Subsequent calls of the same function with the same parameters have no effect ("f(a), f(a)" is the same as "f(a)"); in fact, you can assume duplicates have been removed in earlier processing. But here's the thing that makes it hard (at least for me): two programs are considered the same if they can be made to match by rearranging the order of the input parameters. I.e., "f(a), g(b)" is the same as "f(b), g(a)". Although parameters can be reordered, they cannot be substituted ("f(a), g(b)" is _not_ the same as "f(a), g(a)"). Example: "f(a), g(b), h(a, b)" is the same as "f(b), g(a), h(b, a)" but _not_ the same as "f(a), g(b), h(b, a)". I need a way to compare the input programs, and preferably to order them. In Haskell terms, given the programs are represented by a type Prog, I want Prog to be a member of class Ord, letting me use tools like Data.Map to look up information about previous instances. I can do a brute-force compare by trying all the parameter permutations, but that only gives me Eq, not Ord, and seems terribly inelegant as well.

4 3

Credit Card Authorization code
by S. Alexander Jacobson 06 Mar '06

06 Mar '06

I am looking for Haskell code that does credit card authorization? e.g. paypal website pro does not supply a Haskell lib. Does anyone know where to find something like this? -ALex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

2 1

Hacking Hawk
by szefirov＠ot.ru 06 Mar '06

06 Mar '06

Hawk didn't updated from GHC v4.04. It does contain dependencies on functions that are present in my current (6.04) GHC distribution, but they are not documented. Those functions and constructors are (just a error log from ghc): --------------------------- AQ.lhs:17:16: Not in scope: type constructor or class `STArray' AQ.lhs:82:14: Not in scope: `newSTArray' AQ.lhs:92:21: Not in scope: `writeSTArray' AQ.lhs:258:27: Not in scope: `readSTArray' AQ.lhs:262:27: Not in scope: `writeSTArray' --------------------------- They are in GHC.Arr module now. I found that googling for their name. They also changed their types so that they are not compatible with Control.Monad.ST (previous versions were compatible with LazyST). What does they do? Is it possible to rewrite them for current version of ghc?

3 2

Haskell documentation and GADTs
by Jim Apple 06 Mar '06

06 Mar '06

I'm having trouble generating automatic documentation in a module with GADTs. Haddock gives a parse error, and http://www.cse.ogi.edu/~hallgren/Programatica/tools/features.html seems to indicate that Programmatica will as well. Any ideas? Jim

1 0