July 2007 - Haskell-Cafe

Sparse documentation
by Andrew Coppin 05 Jul '07

05 Jul '07

Is there a reason why the documentation for virtually every module in Control.Monad simply begins with a line that says "Inspired by some paper (http://www.ogi.edu/csee/~mpj/)" and then just shows you a bunch of type signatures, without telling you *anything* about what the module is supposed to be for, or what all these classes, types, methods and functions are meant to *do*? I'm currently struggling with a really knotty problem, and the last thing I need is unhelpful documentation. :-S (Did I mention that that URL goes nowhere?)

12 18

Lightweight sequent calculus and linear abstractions
by oleg＠pobox.com 05 Jul '07

05 Jul '07

Conor McBride has posed an interesting problem: > implement constructors > P v for embedding pure values v > O for holes > f :$ a for application, left-associative > and an interpreting function > emmental > such that > emmental (P (+) :$ (P (*) :$ O :$ P 10) :$ O) 4 2 = 42 I believe one can do better. There is no need for the :$ operation, and there is no need for of lifting non-functional constants. The following code demonstrates a more economical notation. The code essentially implements Hypothetical Reasoning, considering an expression with holes as an (intuitionistic) sequent. Each hole is one formula in the antecedent. The formulas in the antecedent are ordered, so our logic is actually the relevance, substructural intuitionistic logic. The function emmental takes the form of the Deduction Theorem (and its implementation is the proof of the theorem). The test takes the form > test_McBride = dt ((ih *! (10::Int)) +! ih) 4 2 > where ih = holet (undefined::Int) and gives the predictable answer. Another test, which shows that we can pile up holes (aka hypotheses) at will, and they all line up: > test7 = let exp = l1 (map succ) ((1::Int) !: ih !: ih !: ih !: [5]) > ih = holet (undefined::Int) > deduced = dt exp > in deduced 11 12 13 > -- [2,12,13,14,6] > test_order = dt( (ih `p` ih) `p` (ih `p` ih) ) 1 2 3 4 > where ih = holet (undefined::Int) > -- ((1,2),(3,4)) It is clear from our examples that our holes are monomorphically typed; the lifted functions don't have to be. We could have implemented things the other way around. We could have played with more complex inferences when applying polymorphic functions to polymorphic sequents. At present, we chose the simplest solution. Here it is. {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} {-# OPTIONS -fallow-overlapping-instances #-} -- the extensions are merely for the sake of IsHypothetical below -- Lightweight sequent calculus: computations on sequents module SEQ where -- Hypothetical value: one formula in the antecedent newtype H a = H a -- The primitive sequent: a |- a hole :: H a -> a hole (H x) = x -- The version of the above to make it easy to assign a specific type to it holet :: a -> H a -> a holet _ = hole -- This class proves, by construction, the Deduction Theorem -- x |- b ==> x -> b class DeductionTh seq r | seq -> r where dt :: seq -> r instance (IsHypothetical seq f, DeductionTh' f seq r) => DeductionTh seq r where dt = dt' (undefined::f) class DeductionTh' f seq r | f seq -> r where dt' :: f -> seq -> r instance DeductionTh y r => DeductionTh' HTrue (H x -> y) (x->r) where dt' _ hf = \x -> dt (hf (H x)) instance DeductionTh' HFalse a a where dt' _ = id -- Lifting an a->b function to sequents class Lift1 a b arg res | a b arg -> res where l1 :: (a->b) -> (arg->res) instance (IsHypothetical arg f, Lift1' f a b arg res) => Lift1 a b arg res where l1 = l1' (undefined::f) class Lift1' f a b arg res | f a b arg -> res where l1' :: f -> (a->b) -> (arg->res) instance Lift1 a b y b' => Lift1' HTrue a b (H x -> y) (H x -> b') where l1' _ fn arg = \hx -> l1 fn (arg hx) -- here we assert a local functional dependency instance TypeCast arg a => Lift1' HFalse a b arg b where l1' _ fn arg = fn (typeCast arg) test1 = dt True test2 :: Int -> Int test2 = dt hole test2' = dt (holet (1::Int)) test3 = dt (l1 not True) test4 = dt (l1 not (holet False)) -- expected type error -- test4' = dt (l1 not (holet (1::Int))) test4'' = test4 False -- Lifting an a->b->c function to two sequents -- we should keep the order of formulas in the combined antecedent -- The following is just a funnily written `append' of two sequences class Lift2 a b c arg1 arg2 res | a b c arg1 arg2 -> res where l2 :: (a->b->c) -> (arg1->arg2->res) instance (IsHypothetical arg1 f1, IsHypothetical arg2 f2, Lift2' f1 f2 a b c arg1 arg2 res) => Lift2 a b c arg1 arg2 res where l2 = l2' (undefined::f1) (undefined::f2) class Lift2' f1 f2 a b c arg1 arg2 res | f1 f2 a b c arg1 arg2 -> res where l2' :: f1 -> f2 -> (a->b->c) -> (arg1->arg2->res) -- First, drain the antecedent formulas from arg1 instance Lift2 a b c y1 arg2 r => Lift2' HTrue f2 a b c (H x1 -> y1) arg2 (H x1 -> r) where l2' _ _ fn arg1 arg2 = \hx1 -> l2 fn (arg1 hx1) arg2 -- now, add the antecedent formulas from arg2, if any instance Lift2 a b c x1 y2 r => Lift2' HFalse HTrue a b c x1 (H x2 -> y2) (H x2 -> r) where l2' _ _ fn arg1 arg2 = \hx2 -> l2 fn arg1 (arg2 hx2) instance (TypeCast x1 a, TypeCast x2 b) => Lift2' HFalse HFalse a b c x1 x2 c where l2' _ _ fn arg1 arg2 = fn (typeCast arg1) (typeCast arg2) -- Time for tests infixl 6 +! infixl 7 *! infixr 5 !: x +! y = l2 (+) x y x *! y = l2 (*) x y x `p` y = l2 (,) x y x !: y = l2 (:) x y test5 = dt ((1::Int) +! (2::Int)) test51 = dt (holet (1::Int) +! (2::Int)) test51' = test51 10 -- 12 test52 = dt (holet (undefined::Int) `p` holet True) test52' = test52 5 False -- (5,False) test_McBride = dt ((ih *! (10::Int)) +! ih) 4 2 where ih = holet (undefined::Int) test6 = dt( l1 sum (ih !: ih !: ih !: [5]) ) 1 2 3 where ih = holet (undefined::Int) -- 11 test7 = let exp = l1 (map succ) ((1::Int) !: ih !: ih !: ih !: [5]) ih = holet (undefined::Int) deduced = dt exp in deduced 11 12 13 -- [2,12,13,14,6] -- Testing the proper ordering of formulas in the antecedent test_order = dt( (ih `p` ih) `p` (ih `p` ih) ) 1 2 3 4 where ih = holet (undefined::Int) -- ((1,2),(3,4)) -- see http://okmij.org/ftp/Haskell/typecast.html#deep-join data HTrue data HFalse class IsHypothetical a b | a -> b instance TypeCast f HTrue => IsHypothetical (H x->y) f instance TypeCast f HFalse => IsHypothetical a f class TypeCast a b | a -> b, b->a where typeCast :: a -> b class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' instance TypeCast'' () a a where typeCast'' _ x = x

4 3

System.Exit
by Thomas Conway 05 Jul '07

05 Jul '07

Hi All, Can anyone tell me what System.Exit.exitWith is actually supposed to do? As far as I can tell, it seems to be a synonym of (return ()). Okay, I'll stop being provocative and try and be helpful. So I have a web server, which like the one in The Literature(TM), essentially has a main loop: doit sok = do (reqSok,reqAddr) <- Network.Socket.accept sok forkIO (handleRequest reqSok reqAddr) doit sok This is all well and good, but how do you *stop* a server? Well, you have a request (blah blash auth blah blah) which tells it to shut down, /quit for example. I have a function to handle the quit request that looks something like: quitHandler sok addr .... = do tidyUpEverything .... sendOkResponse sok sClose sok System.Exit.exitWith ExitSuccess All nice and simple. All except one detail: it doesn't actually work. It prints exit: ExitSuccess but the "doit" loop keeps going. Of course, it goes totally spacko, because of the call to tidyUpEverything, but it doesn't exit. So, if I set an IORef/TVar inside quitHandler which I inspect either just before or just after the call to Network.Socket.accept, I could exit the loop, but that only helps once the next request comes in. I contemplated a solution involving Control.Exception.throwTo, but I actually read the doco (!) which states the following: <quote> If the target thread is currently making a foreign call, then the exception will not be raised (and hence throwTo will not return) until the call has completed. This is the case regardless of whether the call is inside a block or not. </quote> So no joy there. Ideas anyone? And is exitWith broken, or is it the doco that's broken? cheers, T. -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

4 4

Parsers are monadic?
by Gregory Propf 05 Jul '07

05 Jul '07

First post. I'm a newbie, been using Haskell for about a week and love it. Anyway, this is something I don't understand. Parsers are monadic. I can see this if the parser is reading from an input stream but if there's just a block of text can't you just have the parser call itself recursively feeding the unparsed text down the recursion and tacking nodes onto the tree as the recursions return, finally returning the whole tree to the top level caller. Seems this meets the criteria for pure functionality, same result every time with same args. myParser :: [Char] -> ParseTree ____________________________________________________________________________________ Get the free Yahoo! toolbar and rest assured with the added security of spyware protection. http://new.toolbar.yahoo.com/toolbar/features/norton/index.php

13 21

Where's the problem ?
by Rome 05 Jul '07

05 Jul '07

Hi everyone, I write a program for fast online multiplication, this means, leading digits are computed first, so this program is able to handle real numbers. My program and Source-Code is available under http://www.romeinf04.de http://www.romeinf04.de but only with german comments, because this is my master thesis. Now the problem: My program computes using the schoenhage-strassen multiply-subroutine the output everytime only until the 32777th Digit, but then it holds without an error message. Windows Task manager tells me CPU Usage 100% and Memory Allocation is increasing. Profiling told me, the function Algorithm.resultOfMult is using this memory. To compute the 32777th digit, my program needs several digits of the input-numbers including the 32800th. I'm using GHC 6.6.1 with option -O2 to compile. Output is row-wise by an IO-function, calling itself recursively with updated parameters, hte output looks like: dig11 dig21 --> res1 dig12 dig22 --> res2 dig12 dig23 --> res3 . . . and so on If I use the Naive-Multiply-Subroutine, the problem occurs at the 16392th digit. A friend of mine compiled it under Linux and got: . . . 32779 : 1 1 ---32776--> 0 32780 : 1 0 ---32777--> -1 Main: Ix{Integer}.index: Index (32766) out of range ((0,32765)) If I convert every Integer into Int and use instead of the generic list functions the prelude-list functions, it works. I don't have any idea, where the problem might be... Greetings Roman Please excuse my english writing, I'm from Germany. -- View this message in context: http://www.nabble.com/Where%27s-the-problem---tf4022913.html#a11426358 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

6 8

Parsec - collecting patches - How to contact maintainer Daan Leijen ?
by Marc Weber 05 Jul '07

05 Jul '07

Paresc is a great piece of software. But there are some things which do bother me occasionally. A short list: Things I'd like to change: a) custom location tracking. (I've already written a patch, but I haven't tested how much speed will suffer? Which would be a nice test?) b) Add a function returning a monadic result (thus either (fail . show) return each time .. ) because I feel like doing this all the time. c) make some functions more generic examples: module Text.ParserCombinators.Parsec.Char (these functions should work with any token type): anyChar -> anyToken char -> expectToken string -> expectTokens satisfy d) export some simple functions such as nat decimal etc.. Sometimes all I just want to get an integer without importing Tokens and specifying a language.. shapr / sorear suggested asking SPJ to contact Daan Leijen. Perhaps there are different approaches to address the issues above? Do you also have some patches / suggestions ? Marc Weber

2 1

Re: [Haskell-cafe] folds with escapes
by oleg＠pobox.com 05 Jul '07

05 Jul '07

> Can you do dropWhile in terms of foldr? One can write foldr that represents drop or dropWhile of the original foldr. One can do even more: zip two folds. That is, obtain a fold that is equivalent to zipping up two lists represented by the original folds. Even furthermore, one can do all these things without recursion (neither at the value level, nor at the type level). http://okmij.org/ftp/Algorithms.html#zip-folds

1 0

Re: [Haskell-cafe] Re: Abstraction leak
by dons＠cse.unsw.edu.au 04 Jul '07

04 Jul '07

drtomc: > On 7/4/07, Donald Bruce Stewart <dons(a)cse.unsw.edu.au> wrote: > >Can we do a cheap bytestring binding to libxml, to avoid any initial > >String processing? > > For my part, it's not too big an issue. A version of HaXml or at least > Parsec built on top of ByteString would be a good start. I know there > was a SoC for the latter, though I have not looked to see where it > ended up. > > Actually, if you were looking for a good bit of abstraction to build > how's this? It would be *really* nice to do all my IO with mmap so my > program isn't hit by the buffer duplication problem[*]. The kind of > API I have in mind is something like: > > data Mapping -- abstract > > mmap :: Handle {- or Fd, perhaps -} -> Offset -> Length -> IO Mapping > > read :: Mapping -> Offset -> Length -> IO ByteString > > write :: Mapping -> Offset -> ByteString -> IO () > > munmap :: Mapping -> IO () -- maybe just use a finalizer Oh, we should really restore the mmapFile interface in Data.ByteString. Currently its commented out to help out windows people. And the current implementation does indeed use finalisers to handle the unmapping. > This API has the problem that read in particular still has to do > copying. If you think about the binary XML stuff I mentioned before, > you'll see that it would be really nice if I could mmap in a record > and parse it without having to do any copying, or at least to defer > any copying with a copy-on-write scheme. Doing a simple implementation > of read that just put a ByteString wrapper around the mmapped memory > would be nice and efficient, but would suffer from the problem that if > something changed that bit of the underlying file, things would break. > Maybe it's just not possible to finesse this one. Yep. The current impl is: mmapFile :: FilePath -> IO ByteString mmapFile f = mmap f >>= \(fp,l) -> return $! PS fp 0 l mmap :: FilePath -> IO (ForeignPtr Word8, Int) mmap = do ... p <- mmap l fd fp <- newForeignPtr p unmap -- attach unmap finaliser return fp Maybe I should just stick this in the unix package. -- Don

2 1

Re: [Haskell-cafe] The Garbage Collector Ate My Homework
by Tim Chevalier 04 Jul '07

04 Jul '07

On 7/3/07, Thomas Conway <drtomc(a)gmail.com> wrote: > Okay, so a bit of a tweak of the RTS flags, I got a DRAMATIC improvement: > > 239,434,077,460 bytes allocated in the heap > 9,034,063,712 bytes copied during GC (scavenged) > 132,748,740 bytes copied during GC (not scavenged) > 226,313,736 bytes maximum residency (7 sample(s)) > > 5992 collections in generation 0 (136.16s) > 38 collections in generation 1 ( 62.69s) > 7 collections in generation 2 ( 1.38s) > > 792 Mb total memory in use > > INIT time 0.00s ( 0.00s elapsed) > MUT time 417.54s (673.69s elapsed) > GC time 200.23s (205.86s elapsed) > EXIT time 0.00s ( 0.00s elapsed) > Total time 617.78s (879.55s elapsed) > > %GC time 32.4% (23.4% elapsed) > > Alloc rate 573,432,968 bytes per MUT second > > Productivity 67.6% of total user, 47.5% of total elapsed > > The flags I used were: -H500M -G3 > Nice -- but did you compare the results if you just add -H500M and not -G3? Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt "Aw, honey, you can keep what's in my pockets, but send me back my pants." --Greg Brown

1 0

Re: [Haskell-cafe] Very simple parser
by Gregory Propf 04 Jul '07

04 Jul '07

I hadn't seen that before, thanks. My code wouldn't be that useful as it depends on some of my datatypes. I don't know some basic things here since I'm so new to Haskell. For example, am I to assume that I need to create my own instance of State and then define get and put for it? Some of the examples seem to just use functions that manipulate a state but do not create a new datatype. ----- Original Message ---- From: Arie Peterson <ariep(a)xs4all.nl> To: haskell-cafe(a)haskell.org Sent: Monday, July 2, 2007 2:46:14 PM Subject: Re: [Haskell-cafe] Very simple parser Did you look at the documentation for the State monad? <http://haskell.org/ghc/docs/latest/html/libraries/mtl/Control-Monad-State-L…> It also contains some examples. Getting the next instruction sounds like a job for 'get'; to remove it from the state you might use 'put' or 'modify'. If this doesn't help, can you show something you tried? Greetings, Arie _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ____________________________________________________________________________________ Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more. http://mobile.yahoo.com/go?refer=1GNXIC

4 4