July 2007 - Haskell-Cafe

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

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

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

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

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

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

06 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