March 2010 - Haskell-Cafe

Seeking advice about monadic traversal functions
by Darryn Reid 08 Apr '10

08 Apr '10

Hi, I hope that this is an appropriate place to post this question; I initially posted to Haskell-beginners since that seemed appropriate to my knowledge level. Brent Yorgey kindly suggested I should post here instead. Just for a little background: I'm an experienced computer scientist and mathematician but am very new to Haskell (I love it, I might add, but have much to learn). I've coded a (fairly) general rewriting traversal - I suspect the approach might be generalisable to all tree-like types, but this doesn't concern me much right now. My purpose is for building theorem provers for a number of logics, separating the overall control mechanism from the specific rules for each logic. The beauty of Haskell here is in being able to abstract the traversal away from the specific reduction rules and languages of the different logics. I have paired down the code here to numbers rather than modal formulas for the sake of clarity and simplicity. My question is two-fold: 1. Does my representation of the traversal seem good or would it be better expressed differently? If so, I'd appreciate the thoughts of more experienced Haskell users. 2. I cannot really see how to easily extend this to a queue-based breadth-first traversal, which would give me fairness. I'm sure others must have a good idea of how to do what I'm doing here except in breadth-first order; I'd appreciate it very much if someone could show me how to make a second breadth-first version. Thanks in advance for any help! Darryn. start of code. ------------------------------------------------------------------------- import Control.Monad import Control.Monad.Identity -- Tableau is a tree containing formulas of type a, in -- Fork (disjunctive) nodes and Single (conjunctive) nodes. -- Paths from root to Nil each represent an interpretation. data Tableau a = Nil -- End of a path | Single a (Tableau a) -- Conjunction | Fork (Tableau a) (Tableau a) -- Disjunction deriving (Eq, Show) -- 'Cut' directs the traversal to move back up the tree rather than into -- the current subtree, while 'Next' directs the traversal to proceed -- into the subtree. data Action = Cut | Next deriving (Eq, Show) -- The type of the rewrite function to perform at each node in -- the traversal of the tree. The Rewriter returns the new -- subtree to replace the existing subtree rooted at the -- traversal node, and a direction controlling the traversal -- to the next node. type Rewriter m a = Tableau a -> m (Tableau a, Action) -- The traversal function, depth-first order. rewrite :: (Monad m) => Rewriter m a -> Tableau a -> m (Tableau a) rewrite rf t = do (t', d) <- rf t rewrite' rf d t' -- Worker function for traversal, really its main body. rewrite' :: (Monad m) => Rewriter m a -> Action -> Tableau a -> m (Tableau a) rewrite' rf Cut t = return t rewrite' rf Next Nil = return Nil rewrite' rf Next (Single x t1) = do t1' <- rewrite rf t1 return (Single x t1') rewrite' rf Next (Fork t1 t2) = do t1' <- rewrite rf t1 t2' <- rewrite rf t2 return (Fork t1' t2') -- Some examples to test the code with: -- ghci> let t0 = (Single 2 (Single 3 Nil)) -- ghci> let t1 = (Single 1 (Fork t0 (Fork (Single 4 Nil) (Single 5 Nil)))) -- ghci> let t2 = (Fork (Single 10 Nil) (Single 11 Nil)) -- ghci> let t3 = (Fork (Single 3 Nil) (Single 3 Nil)) -- Running "test4 t1 t2" produces the expected result; running -- "test4 t1 t3" does not terminate, because this endlessly -- generates new patterns that match the substitution condition: test4 :: (Num t) => Tableau t -> Tableau t -> Tableau t test4 tab tab' = runIdentity (rewrite rf tab) where rf (Single 3 Nil) = return (tab', Next) rf t = return (t, Next) -- Running "test5 t1 t3", however, does terminate because the "Cut" -- prevents the traversal from entering the newly spliced subtrees -- that match the pattern. test5 :: (Num t) => Tableau t -> Tableau t -> Tableau t test5 tab tab' = runIdentity (rewrite rf tab) where rf (Single 3 Nil) = return (tab', Cut) rf t = return (t, Next) ------------------------------------------------------------------------- end of code.

3 7

GSOC Haskell Project
by Mihai Maruseac 06 Apr '10

06 Apr '10

Hi, I'd like to introduce my idea for the Haskell GSOC of this year. In fact, you already know about it, since I've talked about it here on the haskell-cafe, on my blog and on reddit (even on #haskell one day). Basically, what I'm trying to do is a new debugger for Haskell, one that would be very intuitive for beginners, a graphical one. I've given some examples and more details on my blog [0], [1], also linked on reditt and other places. This is not the application, I'm posting this only to receive some kind of feedback before writing it. I know that it seems to be a little too ambitious but I do think that I can divide the work into sessions and finish what I'll start this summer during the next year and following. [0]: http://pgraycode.wordpress.com/2010/03/20/haskell-project-idea/ [1]: http://pgraycode.wordpress.com/2010/03/24/visual-haskell-debugger-part-2/ Thanks for your attention, -- Mihai Maruseac

5 13

Data Structures GSoC
by Nathan Hunter 06 Apr '10

06 Apr '10

Hello. I am hoping to take on the Data Structures project proposed two years ago by Don Stewart here<http://hackage.haskell.org/trac/summer-of-code/ticket/1549>, this summer. Before I write up my proposal to Google, I wanted to gauge the reaction of the Haskell community to this project. Particularly: -What Data Structures in the current libraries are in most dire need of improvement? -How necessary do you think a Containers Library revision is? -Should I attempt to build on the work Jamie Brandon did with Map as generalised tries, or is that beyond the scope of this project I am very excited to work with functional data structures, and I would greatly appreciate any input. -Nathan Hunter

5 5

Where are the haskell elders?
by Günther Schmidt 05 Apr '10

05 Apr '10

Hi all, I notice that posts from the Haskell elders are pretty rare now. Only every now and then we hear from them. How come? Günther

10 12

Time for a San Francisco Hackathon?
by Bryan O'Sullivan 04 Apr '10

04 Apr '10

I'm thinking it might be a good idea to organise a Haskell Hackathon for people in (and who'd like to visit) the Bay Area. The tentative date I have in mind is the first weekend in May (conveniently May 1). If you'd be interested in attending or helping to organise, please let me know.

4 4

Profiling
by Andrew Coppin 03 Apr '10

03 Apr '10

Two small questions: 1. Is Thread Scope any use for profiling single-threaded programs? 2. I tried to compile my program with -prof, but GHC just whines at me that the packages I'm using haven't been compiled for profiling. Do I really need to go recompile every single package I'm using with profiling support before I can profile my program? How do I tell Cabal to install the necessary code? (I really hope this doesn't involve uninstalling and reinstalling everything...)

3 2

benchmarking pure code
by Paul Brauner 01 Apr '10

01 Apr '10

Hello, I'm writing a library for dealing with binders and I want to benchmark it against DeBruijn, Locally Nameless, HOAS, etc. One on my benchmark consists in 1. generating a big term \x.t 2. substituting u fox in t The part I want to benchmark is 2. In particular I would like that: a. \x.t is already evaluated when I run 2 (I don't want to measure the performances of the generator) b. the action of substituting u for x in t were measured as if I had to fully evaluate the result (by printing the resulting term for instance). After looking at what was available on hackage, i set my mind on strictbench, which basically calls (rnf x `seq` print "") and then uses benchpress to measure the pure computation x. Since I wanted (a), my strategy was (schematically): let t = genterm rnf t `seq` print "" bench (subst u t) I got numbers I didn't expect so I ran the following program: let t = genterm print t bench (subst u t) and then I got other numbers! Which were closer to what I think they should be, so I may be happy with them, but all of this seems to indicate that rnf doesn't behave as intended. Then I did something different: I wrote two programs. One that prints the result of (subst u t): let t = genterm let x = (subst u t) print x bench (print x) recorded the numbers of that one and then ran the program: let t = genterm bench (print (subst u t)) got the numbers, and substracted the first ones to them. By doing so, I'm sure that I get realistic numbers at least: since I print the whole resulting term, I've got a visual "proof" that it's been evaluated. But this is not very satisfactory. Does anyone have an idea why calling rnf before the bench doesn't seem to "cache" the result as calling show does? (my instances of NFData follow the scheme described in strictbench documentation). If not, do you think that measuring (computation + pretty printing time - pretty printing time) is ok? Regards, Paul

4 8

why doesn't time allow diff of localtimes ?
by briand＠aracnet.com 01 Apr '10

01 Apr '10

which is a variation of the question, why can't I compare localtimes ? or am I missing something in Time (yet again). Thanks, Brian

5 6

Re: iteratee: Do I need to roll my own?
by Valery V. Vorotyntsev 31 Mar '10

31 Mar '10

> I'm looking at iteratee as a way to replace my erroneous and really > inefficient lazy-IO-based backend for an expect like Monad DSL I've > been working for about 6 months or so now on and off. > > The problem is I want something like: > > expect "some String" > send "some response" > > to block or perhaps timeout, depending on the environment, looking for > "some String" on an input Handle, and it appears that iteratee works > in a very fixed block size. Actually, it doesn't. It works with what enumerator gives him. In case of `enum_fd'[1] this is a fixed block, but generally this is a ``value'' of some ``collection''[2]. And it is up to programmer to decide of what should become a value. [1] http://okmij.org/ftp/Haskell/Iteratee/IterateeM.hs [2] http://okmij.org/ftp/papers/LL3-collections-enumerators.txt > While a fixed block size is ok, if I can put back unused bytes into > the enumerator somehow (I may need to put a LOT back in some cases, > but in the common case I will not need to put any back as most > expect-like scripts typically catch the last few bytes of data sent > before the peer is blocked waiting for a response...) I don't quite get this ``last few bytes'' thing. Could you explain? I was about writing that there is no problem with putting data back to Stream, and referring to head/peek functions... But then I thought, that the ``not consuming bytes from stream'' approach may not work well in cases, when the number of bytes needed (by your function to accept/reject some rule) exceeds the size of underlying memory buffer (4K in current version of `iteratee' library[3]). [3] http://hackage.haskell.org/packages/archive/iteratee/0.3.4/doc/html/src/Dat… Do you think that abstracting to the level of _tokens_ - instead of bytes - could help here? (Think of flex and bison.) You know, these enumerators/iteratees things can be layered into _enumeratees_[1][4]... It's just an idea. [4] http://ianen.org/articles/understanding-iteratees/ > Otherwise, I'm going to want to roll my own iteratee style library > where I have to say "NotDone howMuchMoreIThinkINeed" so I don't over > consume the input stream. What's the problem with over-consuming a stream? In your case? BTW, this `NotDone' is just a ``control message'' to the chunk producer (an enumerator): IE_cont k (Just (GimmeThatManyBytes n)) > Does that even make any sense? I'm kind of brainstorming in this > email unfortunately :-) What's the problem with brainstorming? :) Cheers. -- vvv

3 2

Re: Do I need to roll my own?
by John Lato 31 Mar '10

31 Mar '10

Hi Dave, > From: David Leimbach <leimy2k(a)gmail.com> > > I'm looking at iteratee as a way to replace my erroneous and really > inefficient lazy-IO-based backend for an expect like Monad DSL I've been > working for about 6 months or so now on and off. > > The problem is I want something like: > > expect "some String" > send "some response" > > to block or perhaps timeout, depending on the environment, looking for "some > String" on an input Handle, and it appears that iteratee works in a very > fixed block size. While a fixed block size is ok, if I can put back unused > bytes into the enumerator somehow (I may need to put a LOT back in some > cases, but in the common case I will not need to put any back as most > expect-like scripts typically catch the last few bytes of data sent before > the peer is blocked waiting for a response...) I'm quite sure I don't know what you're trying to do. The only time I can think of needing this is if you're running an iteratee on a file handle, keeping the handle open, then running another iteratee on it. Is this what you're doing? If so, I would make a new run function: runResidue :: (Monad m, SC.StreamChunk s el) => IterateeG s el m a -> m (a, s) runResidue iter = runIter iter (EOF Nothing) >>= \res -> case res of Done x s -> return (x, s) Cont _ e -> error $ "control message: " ++ show e This function will return the unused portion of the stream, then you can do this: enumResidue :: Handle -> s -> EnumeratorGM s el m a enumResidue h s = enumPure1Chunk s >. enumHandle h Is this what you need? If I'm completely wrong about what you're trying to do (or you're using multiple threads), there are other options. You also may want to look at iteratee-HEAD. The implementation has been cleaned up a lot, the block sizes are user-specified, and there's an exception-based, user-extensible mechanism for iteratees to alter enumerator behavior. Sincerely, John

2 1