- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] ANNOUNCE: utf8-string-0.1
by Eric Mertens 10 Jul '07

10 Jul '07

On 7/9/07, Henning Thielemann <lemming(a)henning-thielemann.de> wrote: > HXT returns a list of warnings for invalid UTF-8 byte sequences: > http://www.fh-wedel.de/~si/HXmlToolbox/hdoc_arrow/Text-XML-HXT-DOM-Unicode.… > > Is your decoder lazy? > Yes, the decoder is lazy. Regarding error handling, I noticed that Python has three modes for decoding UTF-8: strict, replace, and ignore. strict: error "bad encoding" replace: ('\xfffd' :) ignore: id which I could add if there was interest. -- Eric Mertens

1 0

ANNOUNCE: Haskell XML Toolbox Version 7.2
by Uwe Schmidt 09 Jul '07

09 Jul '07

Haskell XML Toolbox 7.2 I would like to announce a new version of the Haskell XML Toolbox. This is mainly a bug fix release, but there is one new module for converting data between user defined types and the HXT DOM structure. This new modules enables the simple persistent storage and retrieval of arbitrary data with XML documents. See example directory "examples/arrows/pickle" in the distribution for a none trivial example of these picklers. These functions are an adaptation of Andrew Kennedy's pickler combinators. ( http://research.microsoft.com/~akenn/fun/picklercombinators.pdf ) The darcs repo for HXT is at http://darcs.fh-wedel.de/hxt More information and download: http://www.fh-wedel.de/~si/HXmlToolbox/index.html Please email comments, bugs, etc. to hxmltoolbox(a)fh-wedel.de Uwe -- University of Applied Sciences, Wedel, Germany http://www.fh-wedel.de/~si/index.html

1 0

Re: [Haskell-cafe] Gtk2Hs, Glade, Multiple windows/dialog in one interface file.
by Brandon S. Allbery KF8NH 09 Jul '07

09 Jul '07

On Jul 8, 2007, at 16:36 , D.V. wrote: > I finally got it to work with onResponse : I traced each possible > response to see which one was fired when clicking the close button.... Great, another place where the documentation's wrong. :/ (onActivateLeaf vs. onActivateItem (and after- versions) also found to be wrong. Must submit a bug report at some point.) -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery(a)kf8nh.com system administrator [openafs,heimdal,too many hats] allbery(a)ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

2 1

Memoisation + unsafePerformIO
by Tony Morris 09 Jul '07

09 Jul '07

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hello everyone, I am trying to write a generalisation of memoisation for a couple of backtracking algorithms that I wrote (which don't specify a memoisation technique), by keeping a local destructive update using unsafePerformIO and IORef - neither of which I have used before and I am struggling to figure out. I am going from the document: http://haskell.org/hawiki/GlobalMutableState I am not sure if: a) this is even possible b) if a) holds, if this is a good thing Here is some code to help demonstrate what I intend: {-# OPTIONS_GHC -fglasgow-exts #-} import Data.Ix - -- implementations must guarantee that - -- memo f k is equivalent to f k - -- but may otherwise use local destructive updates class Memo k v where memo :: (k -> v) -> k -> v instance (Ix k) => Memo k v where memo f k = error("todo: array") instance (Ord k) => Memo k v where memo f k = error("todo: binary tree") - -- Tony Morris http://tmorris.net/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGkZlFmnpgrYe6r60RArT8AJ4iFVyzmUN1pdxpMBokZpj48CiqRgCfReIe 2yZ55LMcFs24TJOVeCV4tbo= =IR5s -----END PGP SIGNATURE-----

3 2

ANNOUNCE: utf8-string-0.1
by Eric Mertens 09 Jul '07

09 Jul '07

Hello, I'd like to announce that I have posted a UTF-8 encoding/decoding library to hackage. This library also includes replacements for most of the System.IO namespace under System.IO.UTF8. This library detects overlong sequences, and replaces invalid code-points and invalid encodings with the replacement character '\xfffd'. The following file was used to ensure that the decoder was considered "safe": http://www.cl.cam.ac.uk/~mgk25/ucs/examples/UTF-8-test.txt utf8-string can be found on hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/utf8-string-0.1 source code is available via: darcs get http://code.haskell.org/utf8-string/ -- Eric Mertens

2 1

Compress and serialise data with lazy bytestrings, zlib and Data.Binary (was: Allocating enormous amounts of memory)
by dons＠cse.unsw.edu.au 09 Jul '07

09 Jul '07

Jefferson Heard write: > I'm using the Data.AltBinary package to read in a list of 4.8 million > floats and 1.6 million ints. Doing so caused the memory footprint to > blow up to more than 2gb, which on my laptop simply causes the program > to crash. I can do it on my workstation, but I'd really rather not, > because I want my program to be fairly portable. > > The file that I wrote out in packing the data structure was only 28MB, > so I assume I'm just using the wrong data structure, or I'm using full > laziness somewhere I shouldn't be. Here's a quick example of how to efficient read and write such a structure to disk, compressing and decompressing on the fly. $ time ./A Wrote 4800000 floats, and 1600000 ints Read 4800000 floats, and 1600000 ints ./A 0.93s user 0.06s system 89% cpu 1.106 total It uses Data.Binary to provide quick serialisation, and the zlib library to compress the resulting stream. It builds the tables in memory, writes and compresses the result to disk, reads them back in, and checks we read the right amount of CFloats and CInts. You'd then pass the CFloats over to your C library that needs them. Compressing with zlib is a flourish, but cheap and simple, so we may as well do it. With zlib and Data.Binary, the core code just becomes: encodeFile "/tmp/table.gz" table table' <- decodeFile "/tmp/table.gz" Which transparently streams the data through zlib, and onto the disk, and back. Simple and efficient. -- Don Here's the code: -- some imports import Text.Printf import Data.Binary import Codec.Compression.Zlib import Control.Monad import qualified Data.ByteString.Lazy as L import qualified Data.ByteString.Base as B import Foreign import Foreign.C.Types -- A simple table type for the arrays, that will be easy to manipulate data Table = Table { floats :: L.ByteString , ints :: L.ByteString } -- Serialise this data in gzip-compressed form: a gzipping Binary instance. instance Binary Table where put t = do put (compress (floats t)) put (compress (ints t)) get = liftM2 Table (decompress `liftM` get) (decompress `liftM` get) -- Default sizes floatSize = 4800000 intSize = 1600000 -- Build a new empty table newTable :: IO Table newTable = do f <- mallocArray floatSize :: IO (Ptr CFloat) i <- mallocArray intSize :: IO (Ptr CInt) -- fill them with data here -- -- convert to bytestrings. bf <- B.packCStringFinalizer (castPtr f) (floatSize * sizeOf (undefined :: CFloat)) (return ()) bi <- B.packCStringFinalizer (castPtr i) (intSize * sizeOf (undefined :: CInt)) (return ()) return $ Table (L.fromChunks [bf]) (L.fromChunks [bi]) -- Now just build the table, serialise it, read it back in, and print the result main = do table <- newTable -- write the data to disk, compressed with gzip as we go. encodeFile "/tmp/table.gz" table draw "Wrote" table -- load it back in, decompressing on the fly table' <- decodeFile "/tmp/table.gz" draw "Read" table' -- now use 'floats' as a Ptr to pass back to C. where draw s v = printf "%s %d floats, and %d ints\n" s (fromIntegral (lengthFloats v) `div` sizeOf (undefined :: CFloat)) (fromIntegral (lengthInts v ) `div` sizeOf (undefined :: CInt)) lengthFloats = L.length . floats lengthInts = L.length . ints

1 1

Re: practicality of typeful programming
by oleg＠pobox.com 09 Jul '07

09 Jul '07

Daniil Elovkov wrote: > I've recently asked some questions here about some little type hackery > implementing an embedded dsl. But now I wonder if it's worth the > effort at all... Yes it is. Typed embedded DSL are quite useful and widely used. For example, Lava (high-level hardware description language) uses phantom types to prevent the designer from building meaningless circuits (e.g., connecting a Bool and an Int wires). http://citeseer.ist.psu.edu/69503.html There are other such hardware design languages which profitably use types (which ought to be popularized more). Using types can decrease the amount of error checking in the implementation. I highly recommend the following _very_ good thesis on this topic: Morten Rhiger Higher-Order Program Generation http://www.brics.dk/DS/01/4/index.html

3 7

Re: [Haskell-cafe] Gtk2Hs, Glade, Multiple windows/dialog in one interface file.
by D.V. 09 Jul '07

09 Jul '07

I finally got it to work with onResponse : I traced each possible response to see which one was fired when clicking the close button.... onResponse aboutdialog $ \resp -> do putStrLn "onResponse!!!" case resp of ResponseNone -> putStrLn "ResponseNone" ResponseReject -> putStrLn "ResponseReject" ResponseAccept -> putStrLn "ResponseAccept" ResponseDeleteEvent -> putStrLn "ResponseDeleteEvent" ResponseOk -> putStrLn "ResponseOk" ResponseCancel -> putStrLn "ResponseCancel" >> widgetHide aboutdialog ResponseClose -> putStrLn "ResponseClose" ResponseYes -> putStrLn "ResponseYes" ResponseNo -> putStrLn "ResponseNo" ResponseApply -> putStrLn "ResponseApply" ResponseHelp -> putStrLn "ResponseHelp" ResponseUser n -> putStrLn ("ResponseUser "++ show n)

1 0

Gtk2Hs, Glade, Multiple windows/dialog in one interface file.
by D.V. 09 Jul '07

09 Jul '07

Is it possible to have multiple windows in a glade file, and display only one when the program starts, then show/hide the others as the need arises ? I can't find how... I have a main window with a menu. One entry shows the about dialog which is also defined in the glade file : aboutmenu <- xmlGetWidget xml castToMenuItem "apropos1" onActivateLeaf aboutmenu $ do widgetShowAll aboutdialog My problems are multiple : 1) how do I handle the close button that is automatically generated ? I tried doing this ... aboutdialog <- xmlGetWidget xml castToAboutDialog "aboutdialog1" onDestroy aboutdialog $ do widgetHide aboutdialog But the Close button doesn't work, and if I close the about dialog by the upper right cross button, it does disappear, but if I select again the menuitem, then a tiny empty dialog opens, as if the about dialog has been stripped out of all his inner components. And I get this line : (<interactive>:10852): Gtk-CRITICAL **: gtk_container_foreach: assertion `GTK_IS_CONTAINER (container)' failed I tried looking at the demos, but it doesn't help. The closest that could have helped uses an about dialog it creates, instead of reading from a glade file.

2 5

A very nontrivial parser
by Andrew Coppin 09 Jul '07

09 Jul '07

Well, I eventually got it to work correctly... (!) My goal is to be able to stack multiple parsers one on top of the other - but be able to *change* the stack half way through parsing if needed. This I eventually succeeded in doing. The external interface is fairly simple, but the type signatures are NOT. (!!) My basic idea was to abstract the data source that a parser gets its data from: class Source s where empty :: s x -> Bool fetch :: s x -> (x, s x) instance Source [] where -- Nice syntax... :-S empty = null fetch xs = (head xs, tail xs) Now I can define a parser type. But... uh... there's a slight glitch. What I *want* to say is Parser state in out = ... But what I ended up with is newtype Parser state src x y = Parser ((state, src x) -> (state, src x, y)) I then make Parser a monad, write some functions to get/set the state parameter, and token_get :: (Source src) => Parser state src x x token_get = Parser (\(state, tokens) -> let (t,ts) = fetch tokens in (state, ts, t)) Anyway, all of that more or less works. Then I begin the utterly psychopathic stuff: data Stack state0 src0 t0 t1 = ... instance Source (Stack state0 src0 t0) where ... stacked :: st0 -> Parser st0 src0 t0 [t1] -> st1 -> Parser st1 (Stack st0 src0 t0) t1 x -> Parser st9 src0 t0 x By this point, my brain is in total agony! >_< But, almost unbelievably, all this psychotic code actually *works*... (Well, there were a few bugs, they're fixed now.) Essentially, I have the "stacked" function, where if I do x <- stacked foo parser1 bar parser2 y <- parser3 then it runs parser2, but it uses parser1 to transform the data first. Which is what I actually wanted in the first place... Most critically, when parser2 *stops* demanding tokens, parser3 is run, picking up from where parser1 left off. (Confused yet? Wait til you see the code to implement this insanity!) One problem remains... That pesky source type. Every time I mention a parser, I have to say what kind of course object it reads from - even though all parsers work with *any* source object! (That's the whole point of the Source class.) I really want to get rid of this. (See, for example, the type signature for "stacked". Yuck!) Also, every time I write a simple parser, I get a compile-time error saying something about a "monomorphism restriction" or something... If I add an explicit type it goes away, but it's very annoying to keep typing things like test7 :: (Source src) => Parser state src Int Int and so forth. And I can't help thinking if I could just get *rid* of that stupid source type in the signature, there wouldn't be a problem... Anybody have a solution to this?

21 89

Language semantics
by Andrew Coppin 09 Jul '07

09 Jul '07

I have a tricky little question... Suppose I write a function like this: foo pattern1 | gard1 = ... | gard2 = ... foo pattern2 | gard3 = ... | gard4 = ... According to one tutorial I read, if pattern1 matches, pattern2 will never be tried, even if both guard1 and guard2 fail. And according to another tutorial I read, if pattern1 matches but all guards fail, pattern2 *will* be tried. Can somebody comfirm which one is actually correct?

10 25

Re: [Haskell-cafe] A very edgy language
by Andrew Coppin 09 Jul '07

09 Jul '07

Gwern Branwen wrote: > > Out of curiosity, why does ByteString wreck the cleanness of your BWT? It seems to me that if you're doing > bwt :: String -> Whatever > bwt arg = ...(time and space intensive ByteString operations).... $ ByteString.pack arg > > then your code is only modestly less clean. > It's more that currently I have bwt :: (Ord x) => [x] -> [x] and I'm going to have to change that to bwt :: ByteString -> ByteString Then I'll have to change all the list functions to ByteString functions. And then - the hardest part - I'm going to have to edit my entire program framework to make it do ByteString I/O instead of [Char], and pipe it all the way through to the BWT function. And then I'll have to go edit all the algorithms that *don't* use ByteStrings to fix them... The alternative is to do bwt = ByteString.unpack $ ... $ ByteString.pack I have no idea how efficient or not that would be...

1 0

Trying to make a Typeable instance
by Adrian Hey 08 Jul '07

08 Jul '07

Hello, I'm trying to make the type (ListGT map k a) an instance of Typeable, where map is kind (* -> *). data ListGT map k a = Empt | BraF ![k] a !(map (ListGT map k a)) | BraE ![k] !(map (ListGT map k a)) I thought I'd cracked it with something like this.. instance (Typeable (map (ListGT map k a)), Typeable k, Typeable a) => Typeable (ListGT map k a) where typeOf lgt = mkTyConApp (mkTyCon "Data.Trie.General.ListGT") [mTypeRep, kTypeRep, aTypeRep] where BraF [k] a m = lgt -- This is just to get types for k a m !! kTypeRep = typeOf k aTypeRep = typeOf a mTypeRep = typeOf m However, showing the resulting TypRep gives a stack overflow. I wasn't too surprised about this, so I tried replacing the last line with.. mTypeRep = mkTyConApp (typeRepTyCon (typeOf m)) [] ..thinking that this would make it terminate. But it doesn't. Could someone explain how to do this? Thanks -- Adrian Hey

4 7

ANNOUNCE: logict-0.2
by Dan Doel 08 Jul '07

08 Jul '07

Hello all, I've just completed a library adapting the logic programming monad from the "Backtracking, Interleaving, and Terminating Monad Transformers" paper[1] into a format typical of the hierarchical libraries (based on MTL). It uses the two-continuation passing implementation described therein. Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/logict-0.2 Tarball: http://hackage.haskell.org/packages/archive/logict/0.2/logict-0.2.tar.gz Feel free to let me know if your find any bugs, or have suggestions. Dan Doel [1]: http://okmij.org/ftp/papers/LogicT.pdf

1 0

interrupting an accept()ing thread
by Lukas Mai 08 Jul '07

08 Jul '07

Hello, cafe! I have the following code (paraphrased): ... forkIO spin ... spin = do (t, _) <- accept s -- (*) forkIO $ dealWith t -- (**) spin My problem is that I want to stop spin from another thread. The "obvious" solution would be to throw it an exception. However, that leaks a socket (t) if the exception arrives between (*) and (**). I could wrap the whole thing in block, but from looking at the source of Network.Socket it seems that accept itself is not exception safe; so no matter what I do, I can't use asynchronous exceptions to make spin exit. (Is this actually true? Should accept be fixed (along with a lot of other library functions)?) Another idea is to sClose s in another thread. This makes accept throw an IO exception, which breaks the loop. Yay! But it introduces another race condition: If a third thread creates a socket between sClose and accept, the underlying file descriptor of s may get reused, leading to silently wrong behavior because accept listens on the wrong socket now. My question is: How can I use accept in a loop so that I can safely stop it from another thread? Lukas

4 8

Re: Playing with delimited continuations
by oleg＠pobox.com 07 Jul '07

07 Jul '07

The ZFS library contains the most up-to-date implementation of the CC monad and the transformer. I have a few other versions scattered around, but they are probably not relevant. I found the CC_FrameT.hs to be the fastest one. > Is that you can think of normal continuations as delimited > continuations with a global prompt p0 that denotes the end of the > computation. You can emulate this using the reader monad to store the > prompt: Alternatively, one can use implicit parameters. They are quite handy in this case. > So, I suppose my first question is if anyone can see a better way of > generalizing the types of the control operators to work with the > arbitrarily nested monad stacks typically used in MTL. I believe the answer to this question is NO. That means, (delimited) continuations expose the fundamental limitation of monadic transformers. Monadic transformation approach imposes the strict separation of layers. They layers are fixed at compile time and can't dynamically change. Alas, there are many _practically significant_ circumstances where the layers have to change dynamically, have to interleave. Our ICFP06 paper discusses this point a bit, and the accompanying code contains the relevant examples. http://okmij.org/ftp/packages/DBplusDC-README.txt Please see the README file and the file reader.hs in the source code. When we first realized that monadic transformers had a significant limitation, we too felt odd. Please see also below. > First, the prompt module needs to use unsafeCoerce, or something equivalent. > But, of course, unsafeCoerce feels dirty to me, and it'd be nice if some cool > type system hackery could be used instead of going around the type system. Alternatively, if we have reference cells available (STRef or IORef), then we don't need unsafeCoerce. The whole code is pure Haskell with no unsafe operations, and is type safe and sound. This outcome is not an accident: given monadic style, the CC monad and reference cells are `equivalent'. Given one, we can get the other. Any type system that is capable of typing reference cells will give us delimited continuations (provided we have the monadic style so we can deal with the `stack'). One part of that claim, from multi-prompt delimited continuations to reference cells, was formulated and proven in the ICFP06 paper. The converse was formulated in an appendix to the paper, which was taken out because we ran out of space-time. The proof was done by construction, which is not generally available (although the pure OCaml implementation of CC shows how that can be done). The only drawback of using STRef or IORef to implement CC is that CC is no longer a transformer (because neither ST nor IO are). That may not be such a big drawback as the only benefit of CC being transformer (for us, at least) is that we can lay it out over the IO monad. Well, actually there is another benefit, of limiting the effects of the code: even if the CC m code will execute in the IO monad, the code cannot know that. Incidentally, there is actually little need to mix CC with other monad transformers like reader, writer, RWST, Error, etc. The CC monad subsumes them all! That is the important theoretical result by Filinski: delimited continuations can express every expressible monad. This has important practical benefits: we can use real names (variables of the type Prompt) to operate various pieces of state, environment, errors, etc. We no longer need to count the number of 'lift'. The overall performance may be better, too: each monadic layer adds at least one closure. CC monad can implement threads, and I have a hunch CC monad can implement STM. > Second is a minor point. There's a sequence datatype in the paper that > represents the delimited stack: > > > data Seq s r a b ... > > Which represents a sequence of frames that take a value of type 'a' to > a value of type 'b'. The paper mentions that the empty constructor > should have type 'Seq s r a a', but that it's impossible to do that, > so they instead have it take a function that provides evidence of the > equivalence between a and b, using 'id' and a smart constructor to > have the same effect. But, with GADTs, it's now possible to have a > constructor with the right type directly, so I did that in my > implementation. Have you checked the latest draft of the paper from Amr Sabry's home page? They might have changed that point. Anyway, there is an implementation > data Seq s r a = PushP (Prompt.Prompt r a) (Seq s r a) > | forall c. PushSeg (s r a c) (Seq s r c) > | forall c. PushCO (a -> c) (Seq s r c) > > type SubSeq s r a b = Seq s r b -> Seq s r a that has no EmptyS constructor as you can see. So, the trouble you have encountered goes away. The authors are aware of that minor point. The point is truly minor so perhaps it is not bothering with. If you'd like that code, please check with the authors first, because it is wholly based on their work.

3 2

Two-continuation `monads' and MonadMinus [Re: Parsers are monadic?]
by oleg＠pobox.com 07 Jul '07

07 Jul '07

When designing the full Kanren, we have experimented with two-continuation actions and various plumbing combinators (any, all, deterministic-all, etc). We eventually gave up on this after we realized that a simple interface suffices. Called MonadMinus, it is capable of defining LogicT monad with the true logical negation as well as interleaving and committed choice. Our ICFP05 paper describes MonadMinus monad (actually, the transformer) and LogicT as well as their two implementations. One of them uses success and failure continuations, and the other is based on delimited continuations. The latter offer an additional way to report `out-of-band' errors and continue parsing after the error has been `fixed'. http://okmij.org/ftp/Computation/monads.html#LogicT It is fair to say that whereas foldr/build and destroy/unfoldr fusion techniques work for Haskell lists, msplit/reflect in the LogicT paper is a fusion law for a general backtracking computation over arbitrary, perhaps even strict, base monad. That computation may look nothing like list; in fact, the LogicT paper gives an example with delimited continuations, with abort playing the role of nil and shift the role of cons.

2 3

ANN: functorm-1.0.1
by Stefan O'Rear 07 Jul '07

07 Jul '07

This is an update to remove a spurious dependency on the unix package (thanks to Andrea Vezzosi for the quick spot). I had used the vty cabal file as a template but forgot to fix the depenencies. Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/functorm-1.0.1 Tarball: http://hackage.haskell.org/packages/archive/functorm/1.0.1/functorm-1.0.1.t… Darcs: http://members.cox.net/stefanor/functorm Stefan

1 0

needsaname :: ([a] -> Maybe (b, [a])) -> (b -> [a]) -> [a] -> [a]
by Jules Bean 07 Jul '07

07 Jul '07

Hi, Yet another "Function looking for a name" post. Here's the type: > morph :: ([a] -> Maybe (b,[a])) -> (b -> [a]) -> [a] -> [a] Here, I am calling ([a] -> Maybe (b,[a])) the 'selector'. It is actually the same type as a simple parser. I am calling (b -> [a]) the 'transformer'. Once you've chosen your selector and transformer, it's a stream processing function [a] -> [a]. The idea is that the 'selector' looks at the front of the stream and decides if it matches some predicate. (Not necessarily just based on only the first element, though). If it does not, it will return Nothing and that element is passed through unchanged. If it matches then it produces (parses) some representation or calculation 'b'. The transformer is then responsible to transforming this 'b' back into a list of as to be spliced back into the stream. So morph is a general stream manipulation combinator. Let me give some examples: * Replace all strings of odd numbers by (just one occurence of) the number 0 *Main> morph (sAll odd) (const [0]) [1,3,2,3,4,4,3,1,5] [0,2,0,4,4,0] * Add one to all even numbers *Main> morph (sAll even) (map (+1)) [1,3,2,3,4,4,3,1,5] [1,3,3,3,5,5,3,1,5] Here "sAll" is the very simply defined: > sAll p l@(x:xs) | p x = Just (span p l) > | otherwise = Nothing * simple string replacement *Main> morph (sMatch "fox") (const "ferret") "the quick brown fox jumped over the lazy dog" "the quick brown ferret jumped over the lazy dog" * string match + modify *Main Data.Char> morph (sMatch "fox") (("'"++).(++"'").reverse . map toUpper) "the quick brown fox jumped over the lazy dog" "the quick brown 'XOF' jumped over the lazy dog" ...in the above two examples, sMatch is defined as: > sMatch a l | a `isPrefixOf` l = Just (a,drop (length a) l) > | otherwise = Nothing I'm fairly sure that the active hive-mind of haskell-cafe will be able to think of many more uses of this function. I actually wrote it to do HTML fix-up, working with the TagSoup library. A few quick definitions and it becomes easy to express things like 'remove all FONT, BR and U tags; replace all instances of B with SPAN CLASS="important"...'; the task of repairing broken HTML and replacing simplistic markup with semantic markup. It's very powerful to have the separation between selection and transformation; it's quite easy to build up powerful libraries of selectors and use them with simple transformers. Here is the definition of morph: > morph sel trans [] = [] > morph sel trans l@(x:xs) = case sel l of Nothing -> x : morph sel trans xs Just (b,xs') -> trans b ++ morph sel trans xs' I've written it to run over lists, but it would not be difficult to make it run over ByteStrings instead, and exploit the 'no-copying' effect on the bits of the stream which were not modified, which would be very handy for programs processing large bytestrings. It could be used for a streaming filter, for example; although care must be taken. A composition of 'morphs' will 'read-ahead' as far as its most greedy selector, so if did want it to stream, you'd have to make sure that your selectors don't read ahead indefinitely (like an XML selector waiting for a closing tag would). There is a close cousin which is fully recursive and not guaranteed to terminate, where you call 'morph' again on the "trans b" part, which I've been calling 'rmorph'. You need it if you want to, for example, remove all correctly nested <FONT>...</FONT> tags. (Although you wouldn't need it if you forgot about nesting, which is arguably more sane for that particular case). Has anyone spotted this function or a close analogue elsewhere in the haskell canon? Does anyone have a better name for it that 'morph'? Jules

5 5

Haddock doesn't work -- with Haddock
by Michael T. Richter 07 Jul '07

07 Jul '07

I've been wrestling the last few days with putting Haddock documentation into my code. After a dead-simple library failed to generate anything meaningful, I gave up, turfed my copy of Haddock and downloaded the latest from the web site. (Haddock 0.8, it seems.) runhaskell Setup.lhs configure runhaskell Setup.lhs build runhaskell Setup.lhs install These three worked fine and I verified with "which haddock" that the right executable is being run. Then I typed "runhaskell Setup.lhs haddock" and got this: michael@isolde:~/Development/haddock-0.8$ runhaskell Setup.lhs install Installing: /home/michael/software/lib/haddock-0.8/ghc-6.6.1 & /home/michael/software/bin haddock-0.8... michael@isolde:~/Development/haddock-0.8$ which haddock /home/michael/software/bin/haddock michael@isolde:~/Development/haddock-0.8$ runhaskell Setup.lhs haddock Preprocessing executables for haddock-0.8... Running Haddock for haddock-0.8... Warning: cannot use package haddock-0.8: ghc-pkg failed Warning: cannot use package base-2.1.1: interface /home/michael/software/share/ghc-6.6.1/html/libraries/base/base.haddock does not exist. Warning: cannot use package haskell98-1.0: HTML directory /home/michael/software/share/ghc-6.6.1/html/libraries/haskell98 does not exist. dist/build/tmp/src/Main.hs:"dist/build/tmp/src/Main.hs": 39:1: Parse error michael@isolde:~/Development/haddock-0.8$ This is exactly the same problem I had running Haddock on my own project. What's the next step from here? -- Michael T. Richter <ttmrichter(a)gmail.com> (GoogleTalk: ttmrichter(a)gmail.com) A well-designed and humane interface does not need to be split into beginner and expert subsystems. (Jef Raskin)

3 6

ANN: functorm-1.0
by Stefan O'Rear 07 Jul '07

07 Jul '07

This is the Data.FunctorM module from 6.6's base, deleted from HEAD still used by some projects (notably jhc); this package can be used for compatibility. Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/functorm-1.0 Tarball: http://hackage.haskell.org/packages/archive/functorm/1.0/functorm-1.0.tar.gz Stefan

1 0

Class Interfaces in OOHaskell?
by Scott West 07 Jul '07

07 Jul '07

Hello all, Looking at the OOHaskell black (grey?) magic, and wondering if there would be an interesting way to construct class interfaces using the OOHaskell paradigm? I'm trying to do it as so (assume relevant types/proxies declared): type FigureInter = Record ( Draw :=: IO () :*: HNil ) figure self = do return emptyRecord where _ = narrow self :: FigureInter abstrFigure self = do super <- figure self visible <- newIORef True returnIO $ setVisible .=. (\b -> writeIORef visible b) .*. isVisible .=. readIORef visible .*. draw .=. return () .<. super but ghci complains (you know how it likes to complain), with Couldn't match expected type `Record t2' against inferred type `F (Proxy Draw) (m ())' In the second argument of `(.*.)', namely `draw .=. (return ())' In the second argument of `(.*.)', namely `(isVisible .=. (readIORef visible)) .*. (draw .=. (return ()))' In the first argument of `(.<.)', namely `(setVisible .=. (\ b -> writeIORef visible b)) .*. ((isVisible .=. (readIORef visible)) .*. (draw .=. (return ())))' Anyone have any tips they care to share? :) Scott

2 2

Re: Combinators for Bi-Directional Tree Transformations: A Linguistic Approach to the View Update Problem" in Haskell
by Benjamin Pierce 07 Jul '07

07 Jul '07

Hi Titto, I'm not aware of any Haskell implementations of these bi-directional combinators, but the core definitions are not very big -- someone looking at the ML code should have no trouble recreating them in Haskell. The main issue to take care of, beyond the mathematical description in the paper, is doing enough memoization of intermediate structures. (Implementing a full-blown programming language based on these combinators is a more serious project, but even there the amount of code is not that large -- it's the design that takes time, and that you can just steal. :-) Regards, - Benjamin P.S. Please cc me directly on any responses -- I don't read the HaskellCafe list regularly...

2 1

Nix for Hackage/Cabal
by apfelmus 07 Jul '07

07 Jul '07

Hello, http://nix.cs.uu.nl/index.html "Nix is a purely functional package manager. This means that it treats packages like values in purely functional programming languages such as Haskell - they are built by functions that don't have side-effects, and they never change after they have been built." To me, it sounds like the ideal solution to package/make/build management in general and Cabal/Hackage/Cabal-install in particular. After all, compilation is just a _pure_ function compile :: Source -> Dependencies -> Object So, the suggestion is to use Nix for Hackage/Cabal. This way, we get package installation/deinstallation for free. I didn't look into it, but it seems that the package description language can express most content from .cabal files and I guess that it even eliminates the need for most of Cabal's functionality like finding compilers and such. The only drawback is that Nix uses a home-brew functional language for package descriptions. Of course, it would be ideal to have a Haskell DSL for that :) Regards, apfelmus

7 7

Abstraction leak
by Andrew Coppin 07 Jul '07

07 Jul '07

...and again today I found myself trying to do something that would be very easy in an imperative language, but I cannot think of a single good way of doing it in Haskell. Hopfully somebody can give me some hints. I'm writing a whole bunch of data compression programs. In particular, one of them was a Huffman encoder. The encoder scans the input file, computes symbol frequencies, and builds a canonical Huffman table, which it then dumps to file. The actual compressed data goes after that. The encoder consists of two functions. One takes the Huffman table and serializes it. The other does the actual encoding. The (++) operator joins the two together before going to file. Getting the data back is mildly more tricky. There's a decoder function that takes the complete data stream, parses out the Huffman table, and returns a pair containing the Huffman table and the remaining data. Then a second decoder function actually does the Huffman decoding on this data. So far, it's all pretty easy. The size of the Huffman table determins how many bytes the decoder needs to read, so it's easy to figure out where the table ends. And then I had a brainwave. I altered the encoder so that the output from the Huffman table serialize function codes through a simple RLE encoder before going to file. Then a went and altered the decoder to... uh... oops. Now I have a problem. It's easy enough to pass the entire data stream through an RLE decoder and feed that to the Huffman table deserialize function, and it will give be back the table. But I now have *no clue* where the table ends in the original stream! If this was Java, you would write all these compression and decompression stages as stream wrappers. So you wrap the raw input stream with an RLE decoder, have the function read the Huffman table, and then take off the RLE decoder and process the rest of the stream. However, in Haskell, the reading and deserializing of the Huffman table doesn't so anything detectable to the original data stream, so you can't tell how much of it the RLE decoder actually processed. Um... help! (What I did in the end was to write the size of the RLE encoded Huffman table to the file and read it back in the decoder. But this shouldn't actually be necessary...)

21 62

update on SoC projects?
by brad clawsie 07 Jul '07

07 Jul '07

does anyone have any interesting update info on the haskell SoC (summer of code) projects? in particular i am intersted in the haskell bindings to libcurl

4 3

Branches of a binary tree
by Kyle L Bittinger 06 Jul '07

06 Jul '07

I am writing some code to find peaks in molecular spectra. I represent a spectrum as a list of numbers (intensities) and build a binary search tree of the positions in the list (x-values) sorted by intensity. Peaks in the spectrum appear as branches of the tree. My task is to return branches of a binary tree that contain no other branches larger than some size. I wrote this function to test whether a tree can be classified as a peak. I suspect it's very inefficient, and it doesn't seem idiomatic to me either. I'm looking for suggestions to improve it: -- |Returns True if the tree can be classified as a peak. Peaks are -- qualified by not having any two branches with a size greater than n. isPeak :: Int -> Tree a -> Bool isPeak _ Tip = True isPeak n (Node _ l r) | (ltn l) && (ltn r) = True | (ltn l) && (gtn r) = isPeak n r | (gtn l) && (ltn r) = isPeak n l | (gtn l) && (gtn r) = False | otherwise = error "isPeak: no matching condition in guard" where gtn = (>=n) . size ltn = (<n) . size The "things to avoid" section of the haskell wiki suggests using an "atLeast" function for testing the length of lists. I don't know how to write this for trees, but I could do something like: gtn = atLeast n . flatten ltn = not . gtn The rest of my module is below. Most of it is standard binary tree stuff. Any suggestions would be much appreciated! --Kyle data Tree a = Tip | Node a (Tree a) (Tree a) deriving Show insert :: Ord a => Tree a -> a -> Tree a insert Tip x = Node x Tip Tip insert (Node y l r) x | x <= y = Node y (insert l x) r | otherwise = Node y l (insert r x) growTree :: Ord a => [a] -> Tree a growTree = foldl insert Tip size :: Tree a -> Int size Tip = 0 size (Node x l r) = 1 + (size l) + (size r) flatten :: Tree a -> [a] flatten Tip = [] flatten (Node x l r) = flatten l ++ [x] ++ flatten r atLeast :: Int -> [a] -> Bool atLeast 0 _ = True atLeast _ [] = False atLeast n (_:ys) = atLeast (n-1) ys peaks :: Int -> Tree a -> [[a]] peaks _ Tip = [] peaks n t@(Node _ l r) | isPeak n t = [flatten t] | otherwise = peaks n l ++ peaks n r -- Stolen from <http://haskell.org/haskellwiki/Blow_your_mind> sortIndicies ys = map fst $ L.sortBy (comparing snd) $ zip [0..] ys where comparing f x y = compare (f x) (f y)

2 1

Problem using ap -- No instance for (Monad ((->) [[a]]))
by Jim Burton 06 Jul '07

06 Jul '07

If I try a function to make a point-free version of the function in this fold -- foldr (\x ys -> ys ++ map (x:) ys) [[]] :pl gives me GOA Control.Monad> :pl (\x ys -> ys ++ map (x:) ys) ap (++) . map . (:) GOA Control.Monad> :t ap (++) . map . (:) ap (++) . map . (:) :: (Monad ((->) [[a]])) => a -> [[a]] -> [[a]] but this is what happens if I try to use it: GOA Control.Monad> let ps = foldr (ap (++) . map . (:)) [[]] <interactive>:1:16: No instance for (Monad ((->) [[a]])) arising from use of `ap' at <interactive>:1:16-22 Possible fix: add an instance declaration for (Monad ((->) [[a]])) In the first argument of `(.)', namely `ap (++)' In the first argument of `foldr', namely `((ap (++)) . (map . (:)))' In the expression: foldr ((ap (++)) . (map . (:))) [[]] (0.00 secs, 0 bytes) What gives? -- View this message in context: http://www.nabble.com/Problem-using-ap----No-instance-for-%28Monad-%28%28-%… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 1

reimplementing break (incorrectly) "quickcheck p list" gives me feedback that it breaks on list, but not what predicate test caused the breakage
by Thomas Hartman 06 Jul '07

06 Jul '07

I am a total quickcheck noob. Is there a way to find out what predicate test "<function>" is, below? Also, is there a way I can ask quickcheck to test lists of various built in types, not just Int? *********** Falsifiable, after 4 tests: <function> [1] *Recursion> testMyBreak Falsifiable, after 1 tests: <function> [-1,1,2] *Recursion> testMyBreak = quickCheck $ \p l -> myBreak p (l :: [Int]) == break p l myBreak t xs = let f t next rest = if t next then ([], snd rest) else (next : fst rest, snd rest) in foldr ( f t ) ([],[]) xs --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

3 2

"Combinators for Bi-Directional Tree Transformations: A Linguistic Approach to the View Update Problem" in Haskell
by Pasqualino 'Titto' Assini 06 Jul '07

06 Jul '07

Hi, I wondered if anyone had written an Haskell implementation of the combinators described in: "Combinators for Bi-Directional Tree Transformations: A Linguistic Approach to the View Update Problem" (see the Papers section of http://www.seas.upenn.edu/~harmony/) Harmony's source is in O'Caml so I guess that a translation in Haskell should not be to hard. More in general, is there any work in Haskell on "updateable views" of generic data structures? Thanks, titto

1 0

folds with escapes
by Michael Vanier 06 Jul '07

06 Jul '07

I'm sure this has been done a hundred times before, but a simple generalization of foldl just occurred to me and I wonder if there's anything like it in the standard libraries (I couldn't find anything). Basically, I was trying to define the "any" function in terms of a fold, and my first try was this: > any :: (a -> Bool) -> [a] -> Bool > any p = foldl (\b x -> b || p x) False This is inefficient, because if (p x) is ever True the rest of the list is scanned unnecessarily. So I wrote a more general foldl with an "escape" predicate which terminates the evaluation, along with a function which tells what to return in that case (given an argument of the running total 'z'): > foldle :: (b -> Bool) -> (a -> a) -> (a -> b -> a) -> a -> [b] -> a > foldle _ _ _ z [] = z > foldle p h f z (x:xs) = if p x then h z else foldle p h f (f z x) xs Using this function, "foldl" is: > foldl' = foldle (const False) id and "any" is just: > any p = foldle p (const True) const False I also thought of an even more general fold: > foldle' :: (b -> Bool) -> (a -> b -> [b] -> a) -> (a -> b -> a) -> a -> [b] -> a > foldle' _ _ _ z [] = z > foldle' p h f z (x:xs) = if p x then h z x xs else foldle' p h f (f z x) xs Using this definition, you can write "dropWhile" as: > dropWhile :: (a -> Bool) -> [a] -> [a] > dropWhile p = foldle' (not . p) (\_ x xs -> x:xs) const [] Again, I'm sure this has been done before (and no doubt better); I'd appreciate any pointers to previous work along these lines. Mike

8 9

Sparse documentation
by Andrew Coppin 06 Jul '07

06 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 06 Jul '07

06 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 05 Jul '07

05 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 05 Jul '07

05 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 05 Jul '07

05 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

Haskell's "currying" versus Business Objects Gem Cutter's "burning"
by peterv 05 Jul '07

05 Jul '07

In Haskell, currying can only be done on the last (rightmost) function arguments. So foo x y can be curried as foo x but not as foo ? y where ? would be a "wilcard" for the x parameter. In Haskell, one must write a new function foo2 y x = foo x y and then one can curry the x parameter like foo2 y In Gem Cutter - which is a visual programming language - on can "burn" any input argument (which is like putting the ? for any argument in the foo function). See http://resources.businessobjects.com/labs/cal/gemcutter-techpaper.pdf This burning looks more general to me, but cannot be done using the textual approach? Does this reasoning make any sense? Thanks, Peter

9 8

Playing with delimited continuations
by Dan Doel 04 Jul '07

04 Jul '07

Hello, My interest was recently caught reading some of Oleg Kiselyov's material on delimited continuations, and so I decided to look into them a little closer. Don Stewart also mentioned in passing on #haskell that'd it'd be nice to have support for delimited continuations either in the standard library, or in some other easily installable package. So, I thought I'd see what such a beast might look like, and dug up the Dybvig, Petyon-Jones, Sabry paper[1] on the subject that I'd read long ago, but probably not understood much. :) After a day or so of hacking, I have (what I think is) a proper implementation of the monad and transformer, along with a suitable typeclass, and instances for the various transformers in the MTL. However, I have by no means tested it extensively (as I don't have a lot of ideas off hand for monad stacks involving delimited continuations), and I'm not totally thrilled with the results I have, so I thought I'd ask for advice/commentary here. Code is attached. First, I guess, should come an example of code using the delimited continuations: > pop = do (h:t) <- get > put t > return h > abortP p e = withSubCont p (\_ -> e) > loop 0 _ = return 1 > loop n p = do i <- pop > if i == 0 > then abortP p (return 0) > else do r <- loop (n-1) p > return (i*r) > test1 n l = runDelCont > (runStateT (newPrompt >>= \p -> > pushPrompt p (loop n p)) l) > test2 n l = runState > (runDelContT (newPrompt >>= \p -> > pushPrompt p (loop n p))) l So, loop finds the product of the first n numbers stored in a list in the state, but aborts immediately if it sees a 0. test1 and test2 stack the monads in the opposite order, but the results are the same in this case (it isn't a very sophisticated example). Another example, from the paper, is that you can think of normal continuations as delimited continuations with a global prompt p0 that denotes the end of the computation. You can emulate this using the reader monad to store the prompt: > type Continue r b a = ReaderT (Prompt.Prompt r b) (DelCont r) a > runContinue :: (forall r. Continue r b b) -> b > runContinue ct = runDelCont (newPrompt >>= \p -> > pushPrompt p (runReaderT ct p)) > callCC' f = withCont (\k -> pushSubCont k (f (reify k))) > where > reify k v = abort (pushSubCont k (return v)) > abort e = withCont (\_ -> e) > withCont e = ask >>= \p -> withSubCont p (\k -> pushPrompt p (e k)) > loop2 l = callCC' (\k -> loop' k l 1) > where > loop' _ [] n = return (show n) > loop' k (0:_) _ = k "The answer must be 0." > loop' k (i:t) n = loop' k t (i*n) So, the loop computes the product of a list of numbers, returning a string representation thereof, but aborts with a different message if it sees 0. Again, nothing special, but it seems to work. However, this is where I started to run into some uglines that followed from my design choices. Most flows from the typeclass: class (Monad m) => MonadDelCont p s m | m -> p s where newPrompt :: m (p a) pushPrompt :: p a -> m a -> m a withSubCont :: p b -> (s a b -> m b) -> m a pushSubCont :: s a b -> m a -> m b So, 'm' is the delimited control monad in question, 'p' is the type of prompts associated with said monad, and 's' is the associated type of subcontinuations that take an 'a', and produce a 'b'. Those four functions are the generalizations of the four control operators from the paper. The crux of the matter is the way the prompts and subcontinuations are typed. A prompt 'p a' can have values of type 'a' returned through it, which is fine in the vanilla DelCont monad. However, in a monad transformed by a StateT, a computation 'm a' isn't returning an 'a' through the prompt. It's actually returning an '(a,s)', due to the state threading. And the same is an issue with the subcontinuation. So, I came up with a couple wrappers: newtype PairedPrompt s p a = PP { unPP :: p (a, s) } newtype PairedSubCont s k a b = PSC { unPSC :: k (a, s) (b, s) } And then you can declare instances like so: instance (MonadDelCont p s m) => MonadDelCont (PairedPrompt t p) (PairedSubCont t s) (StateT t m) where ... Where the declarations not only lift the delimited control actions, but wrap and unwrap the prompts and subcontinuations appropriately. However, this has two issues: 1) It seems kind of kludgy at first glance, although maybe that's just me. 2) It doesn't always work correctly. Consider the following code: > loop3 l = callCC' (\k -> loop' k l 1) > where > loop' _ [] n = return n > loop' k (0:_) _ = k 0 > loop' k (i:t) n = tell [n] >> loop' k t (i*n) It does almost the same thing as loop2, only it has some writer output, too. And we'd like to write: > test3 l = runContinue (runWriterT (loop3 l)) but we can't, because that's a type error, because the prompt is created outside of runWriterT, where it will have type 'Prompt r (a, w)', but used inside runWriterT, where it needs to have type 'PairedPrompt w (Prompt r) a'. Instead, we have to write: > test3 l = runDelCont > (runReaderT > (runWriterT > (newPrompt >>= \p -> > pushPrompt p (local (const p) $ loop3 l))) > undefined) So that the prompt is created and used in the same monadic context. This is hardly ideal. So, I suppose my first question is if anyone can see a better way of generalizing the types of the control operators to work with the arbitrarily nested monad stacks typically used in MTL. Nothing's come to my mind immediately, but I've stopped thinking about it very hard for the time being, and I'm sure there are people here who are much better acquainted with the theory of this sort of thing than I am. I suppose my other issues have to do with the original implementation itself, although I don't really feel very qualified to criticize it, and I can see why all the things were done the way that they were... First, the prompt module needs to use unsafeCoerce, or something equivalent. Prompts are, internally, just Ints, but they have a phantom type (I think that's the right term) denoting the type of value that can be returned through them. Then we eventually want to split the call stack using a prompt of type 'Prompt r a', but there be many prompts on the stack, which will have type 'Prompt r b' for some b (and the actual type of b is forgotten by the stack, I believe, as it's an existential type). However, since the internal Ints are unique identifiers, when we find that the identifiers match, 'a' and 'b' must be the same. So, the implementation uses unsafeCoerce to forge evidence that they are. But, of course, unsafeCoerce feels dirty to me, and it'd be nice if some cool type system hackery could be used instead of going around the type system. But I've really no idea whether there's any substitute for unsafeCoerce here, so I thought I'd ask some of the experts here. Second is a minor point. There's a sequence datatype in the paper that represents the delimited stack: > data Seq s r a b ... Which represents a sequence of frames that take a value of type 'a' to a value of type 'b'. The paper mentions that the empty constructor should have type 'Seq s r a a', but that it's impossible to do that, so they instead have it take a function that provides evidence of the equivalence between a and b, using 'id' and a smart constructor to have the same effect. But, with GADTs, it's now possible to have a constructor with the right type directly, so I did that in my implementation. However, after saying that in the paper, they go on to use the empty constructor with the coerced evidence functions produced above to produce empty sequences of type 'Seq s r a b' where we have some evidence that 'a' and 'b' are the same. So, using the GADT approach, where in the original paper there'd be a single EmptyS constructor, there is now required an extra coercion constructor on top of it in most cases where empty sequences are used. So, I suppose my second question is whether there is any sense in restricting the type to 'Seq s r a a' at all, since it just seems to require extra baggage? I suppose this might tie in with the above question, as the coercions of types Haskell's type system can't prove equal are what's being used. Third, just as a general question, is the paper I'm using the most definitive and recent on the subject of implementing delimited continuations in Haskell? I did some quick google searches, but nothing much turned up besides this paper, and some papers using the implementation in examples of using delimited continuations. It's also the implementation Oleg uses in his recent zipper file system, so I assume there haven't been any particularly radical developments since it was written (which wasn't that long ago, I suppose). Anyhow, I'd appreciate any discussion or thoughts anyone had on the above, or on delimited continuations in haskell in general, as it's a topic that's interested me lately. The attached code is certainly in no shape to be put in a library yet, but perhaps if the issues above can be fixed, or it's decided that they don't matter, it could pave the way. Apologies for the length, and I hope I'm posting to the right place (this didn't seem formal enough for haskell@...). Cheers, Dan Doel [1]: http://research.microsoft.com/Users/simonpj/papers/control/control.pdf

1 0

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

04 Jul '07

[I assume this was meant to go to the list as well, so I'm adding it back to the CCs] On 7/3/07, Thomas Conway <drtomc(a)gmail.com> wrote: > It occurs to me that tweaking the GC parameters can probably make a > big difference: is starting with a bigger heap likely to help, or more > generations? My generation hypothesis is that more generations will > encourage the cached data to drop down out of generation 0, reducing > the GC load. > Starting with a bigger heap is likely to help, since it means that GCs will be needed less often. I'm not sure I buy your generation hypothesis, because even with two generations, you would expect to see some of the cached data move to generation 1. Lots of data in generation 0 implies your code continues to allocate many objects as it goes on running. On the other hand, you could still try and see if it helps. Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt "The illegal we do immediately. The unconstitutional takes a little longer." -- Henry Kissinger

1 0

The Garbage Collector Ate My Homework
by Thomas Conway 04 Jul '07

04 Jul '07

Well, not quite, but look at the following: 118,342,689,824 bytes allocated in the heap 144,831,738,780 bytes copied during GC (scavenged) 335,086,064 bytes copied during GC (not scavenged) 255,257,516 bytes maximum residency (42 sample(s)) 222884 collections in generation 0 (3891.90s) 42 collections in generation 1 (153.99s) 536 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 233.66s (776.99s elapsed) GC time 4045.89s (4251.52s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 4279.55s (5028.52s elapsed) %GC time 94.5% (84.5% elapsed) Alloc rate 506,470,897 bytes per MUT second Productivity 5.5% of total user, 4.6% of total elapsed Can anyone offer general suggestions for how to fix this! 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.

3 2

Getting debugging/logging info?
by Hugh Perkins 04 Jul '07

04 Jul '07

In imperative languages we can do this type of thing: SystemLogging.LogInfo("About to do something..."); DoSomething(); SystemLogging.LogInfo("Did Something"); SystemLogging.LogInfo("x is " + x ); How can we do something similar in Haskell?

5 7

Re: [Haskell-cafe] Haskell's currying and partial application
by Peter Verswyvelen 04 Jul '07

04 Jul '07

Duh, I made a typo in my previous emails, I did mean a -> (b -> c) and not a -> (b,c). But you guys quickly corrected that IMHO when reading http://haskell.org/haskellwiki/Currying a newbie like me cannot see the difference between currying and partial application... I quote the text: -------------------- "Currying is the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function if any arguments are still needed. In Haskell, all functions are considered curried: that is, all functions in Haskell take just single arguments. This is mostly hidden in notation, and so may not be apparent to a new Haskeller. Let's take the function div :: Int -> Int -> Int which performs integer division. The expression div 11 2 unsurprisingly evaluates to 5. But there's more that's going on than immediately meets the untrained eye. It's a two-part process. First, div 11 is evaluated and returns a function of type Int -> Int" -------------------- But that is partial application, not currying no... Later in the text tuples are mentioned, but the real definition of currying being -- Hope I get it right this time... curry :: ((a, b) -> c) -> a -> b -> c is not really clear from the article to me... >----- Oorspronkelijk bericht ----- >Van: Henning Thielemann [mailto:lemming@henning-thielemann.de] >Verzonden: dinsdag, juli 3, 2007 01:48 PM >Aan: 'Peter Verswyvelen' >CC: Haskell-Cafe(a)haskell.org >Onderwerp: Re: [Haskell-cafe] Haskell's currying and partial application > > >On Tue, 3 Jul 2007, Peter Verswyvelen wrote: > >> Ah, thanks for the correction. So if I understand it correctly, this is currying: > >See also: > http://haskell.org/haskellwiki/Currying > http://haskell.org/haskellwiki/Partial_application > >and more generally: > http://haskell.org/haskellwiki/Category:Glossary > >

3 4

Before
by Andrew Coppin 04 Jul '07

04 Jul '07

What were monads like before they became a Haskell language construct? Is Haskell's idea of a "monad" actually anywhere close to the original mathematical formalism? Just being randomly curiose...

4 7

Re: [Haskell-cafe] Haskell's
by Peter Verswyvelen 03 Jul '07

03 Jul '07

Ah, thanks for the correction. So if I understand it correctly, this is currying: when f :: (a,b) -> c then g :: a -> (b,c) is the curried form of f? So currying has to do with tuples? And partial application is just leaving away some tail arguments? >----- Oorspronkelijk bericht ----- >Van: Jules Bean [mailto:jules@jellybean.co.uk] >Verzonden: dinsdag, juli 3, 2007 12:19 PM >Aan: 'peterv' >CC: Haskell-Cafe(a)haskell.org >Onderwerp: Re: [Haskell-cafe] Haskell's "partial application" (not currying!) versus Business Objects Gem Cutter's "burning" > >peterv wrote: >> In Haskell, currying can only be done on the last (rightmost) function >> arguments. > > >You are talking about partial application, not currying. > >> foo x y >> >> can be curried as >> >> foo x >> >> but not as >> >> foo ? y >> >> where ? would be a “wilcard” for the x parameter. > >(\x -> foo x y) > >[snip] > >> This burning looks more general to me, but cannot be done using the >> textual approach? > >Well, it can be done, but basically there are two issues: > >1. You need to demarquate the 'scope' of the ?. What 'lump' of >expression is the partially evaluated part. An obvious way to do this is >with parentheses, but you have to be careful. > >2. If you have more than one ?, you need to remember which is which. >Think of nested expressions, nested ?s. What if you want to use the >'same' ? more than once? > >The solution that haskell chooses to (2) is to 'label' the ?s with >names. The solution to (1) is to mark the scope with a \, and the list >of names bound: > >\x z -> foo (foo x y) z > >Jules > > > >

4 4

Re: [Haskell-cafe] Re: Parsers are monadic?
by Gregory Propf 03 Jul '07

03 Jul '07

Right, I read more about it and found this out. The 'main' function is apparently magical at runtime and allows you to break the with pure functionality just once but since it can call other functions this allows for useful programs to be written. ----- Original Message ---- From: Jules Bean <jules(a)jellybean.co.uk> To: Gregory Propf <gregorypropf(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Sent: Monday, July 2, 2007 1:40:09 AM Subject: Re: [Haskell-cafe] Re: Parsers are monadic? Gregory Propf wrote: > Thanks, that was helpful. I didn't realize that there were pure > functional monads. Actually, it's stronger than that. All monads are pure functional, even IO. Haskell is an entirely 100% pure functional language[*]. The IO monad allows you to build up, in a pure, referentially transparent way, an object call an 'IO action' which you have no way of actually executing, per se. Fortunately, this isn't as useless as it sounds since the runtime system contains the support to "actually run" the special IO action called 'main', which bootstraps the whole setup. Jules [*] non-functions like unsafePerformIO are not technically part of the haskell language! ____________________________________________________________________________________ Never miss an email again! Yahoo! Toolbar alerts you the instant new Mail arrives. http://tools.search.yahoo.com/toolbar/features/mail/

3 2