- Haskell-Cafe - Haskell.org

RE: Problem with backtracking monad transformer
by Guest, Simon 02 Feb '03

02 Feb '03

Hi, > On Thu, Jan 30, 2003 at 01:55:50PM -0000, Guest, Simon wrote: > > > I'm trying to make a backtracking state monad using Ralf Hinze's > > backtracking monad transformer. My problem is that it > > won't backtrack very far. > > > > Suppose I try ( a >> b ) `mplus` c. > > > > If b fails, it should try c, but it doesn't rewind past a. Andrew Bromage wrote: > > I've compared it with my own > well-tested implementation and it seems identical modulo renamings. The similarity is explained by the fact that I looked at your example on the Haskell Wiki as well as Ralf's paper, so thanks for that useful page. > > In case you want to compare: > > http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/hfl/hfl/mtl/ I will have a look at try to see what I am doing wrong. > > I didn't follow the rest of the code, so I suspect the problem is > elsewhere. One place to look is here: > > > -- backtracking state monad > > -- > > type NDSM st a = BACKTR (SM st) a > > You may have meant to stack the monad transformers in a different > order. This bit I don't understand. I only have one monad transformer, which I use to transform my SM monad. I have an uneasy feeling that my observe is in the wrong place (passed to runSM), but again, I can't see what else I should have done. Thanks for the assurance, but I'm still head scratching for now. cheers, Simon

2 1

Re: Global variables?
by Jon Cast 02 Feb '03

02 Feb '03

Nick Name <nick.name(a)inwind.it> wrote: > On Fri, 31 Jan 2003 07:47:43 +0000 > Glynn Clements <glynn.clements(a)virgin.net> wrote: > > The usual fudge is: > > import IORef > > import IOExts > > globalVar :: IORef Int > > globalVar = unsafePerformIO $ newIORef 0 > I see in the documentation of unsafePerformIO that no one makes > guarantees about the order in wich unsafePerformIO arguments are > performed (especially they don't have to be executed BEFORE main), so > this trick should not be adviced as a general practice; it should be > pointed out that it works in GHC but could not work in other > compilers. English nit: I think you mean ``could fail in other compilers'': it's not really impossible for the trick to work in other compilers than GHC. Otherwise, though, see my other post on this subject: unsafePerformIO will perform its action when the variable is accessed, so you can't write a Haskell program which differentiates between what any compiler actually does and running the variable allocations before main. > Vincenzo > -- > Fedeli alla linea, anche quando non c' Quando l'imperatore > malato, quando muore,o dubbioso, o perplesso. Fedeli alla linea > la linea non c'. [CCCP] Jon Cast

3 2

Re: Global variables?
by Jon Cast 02 Feb '03

02 Feb '03

Ralf Hinze <ralf(a)informatik.uni-bonn.de> wrote: > > Pavel G. Zhbanov wrote: > > > Is it even possible to make a "global variable" in Haskell? If > > > yes, how? > > The usual fudge is: > > import IORef > > import IOExts > > > > globalVar :: IORef Int > > globalVar = unsafePerformIO $ newIORef 0 > > However, beware of creating more than one "global variable" of the > > same type. If you enable optimisation, common subexpression > > elimination may result in both names referring to the same IORef. > John Hughes wrote a nice pearl on the subject, see > http://www.math.chalmers.se/~rjmh/Globals.ps This paper claims ``unsafePerformIO is unsafe''. That's not actually true in the sense meant; unsafePerformIO merely has safety pre-conditions that the compiler can't check. However, there's nothing wrong with using it (or wrapping it) as long as the preconditions are checked. In fact, IMO, it's /better/ to use unsafePerformIO in a common case like this, because exactly when the preconditions are satisfied will be much better understood. The precondition (proof obligation) of unsafePerformIO is that the order in which unsafePerformIOs are performed cannot affect the outcome of the program. However, in this case, ordering doesn't matter: the only side effect is allocation of a new IORef, and IORefs are sufficiently opaque we don't care (or really know) about un-allocated IORefs while the only case we care about the now-allocated IORef is when we de-reference it. But, that forces the IORef, which executes the unsafePerformIO. So, whenever we access the variable, it is allocated. Therefore, the outcome of the program (regardless of the order of evaluation) is the same as if all such global variable declarations are executed before main begins executing. So, the outcome is independent of the order of evaluation. There you go: the precondition of unsafePerformIO is satisfied, so the usage is safe. > Cheers, Ralf Jon Cast

2 1

how to open a file descriptor
by David Roundy 01 Feb '03

01 Feb '03

Hello. I'm in the process of interfacing with some C code (libcurl), and I thought that the easiest way to transfer the data in (which is a file transfered over the network) would be to open a pipe and write it into the pipe, and then to pass the pipe over to haskell where I could read it with the IO monad normally. Is there any nice way to open up a file descriptor? I was looking at the ghc internal code, which has an openFd function that would do what I want, but it doesn't seem to be exported. :( Any ideas? -- David Roundy http://civet.berkeley.edu/droundy/

2 2

Re: Global variables?
by Jon Cast 31 Jan '03

31 Jan '03

Glynn Clements <glynn.clements(a)virgin.net> wrote: > Pavel G. Zhbanov wrote: > > Is it even possible to make a "global variable" in Haskell? If yes, > > how? > The usual fudge is: > import IORef > import IOExts > globalVar :: IORef Int > globalVar = unsafePerformIO $ newIORef 0 > However, beware of creating more than one "global variable" of the > same type. If you enable optimisation, common subexpression > elimination may result in both names referring to the same IORef. Is this true? It seems wrong---I don't think expressions involving unsafePerformIO should be combined, for precisely this reason. Even if it is true, though, the following kludge should work: > {-# NOINLINE mkGlobalVar #-} > mkGlobalVar :: String -> alpha -> IORef alpha > mkGlobalVar name value = usafePerformIO (newIORef value) > globalVar = mkGlobalVar "globalVar" 0 This ensures that no common sub-expression elimination will be performed. > -- > Glynn Clements <glynn.clements(a)virgin.net> Jon Cast

1 0

Now solved [was RE: Problem with backtracking monad transformer]
by Guest, Simon 31 Jan '03

31 Jan '03

Andrew Bromage wrote: > > You may have meant to stack the monad transformers in a different > > order. I finally understand. This was exactly my problem. I had to discard my state monad, and use a state monad transformer on the simple backtracking monad (not the backtracking monad transformer on the state monad). Now it works fine (of course). Thanks for the help. cheers, Simon

1 0

Nine open CSE positions at Chalmers
by Patrik Jansson 31 Jan '03

31 Jan '03

The School of Computer Science and Engineering (at Chalmers Univ. in Gotheburg, Sweden) announces 9 open positions (teaching+research): http://www.cse.chalmers.se/doit/doiteng/vacancies/positions.html Apply or spread the word! (List relevance: Many of us use Haskell both in teaching and in research.) /Patrik PS. From my point of view, Haskellers with a background in Software Engineering / Information systems / Human Computer Interaction etc. are extra welcome!

1 0

``Cannot instantiate a type variable with a forall-type''
by Jon Cast 30 Jan '03

30 Jan '03

Why does GHC place this constraint? I would expect forall to be predicative, and a type variable to range over all types, but obviously I'm missing something. Jon Cast

1 0

List comprehensions
by Rijk J. C. van Haaften 30 Jan '03

30 Jan '03

Hello, Recently, I came accross this expression: [ x + y | x <- xs | y <- ys ] As far as I can see (Haskell Report), this is not allowed by the haskell 98 standard. So I assume it to be an ex- tension. Where can I find information about this? Thanks, Rijk

5 6

Problem with backtracking monad transformer
by Guest, Simon 30 Jan '03

30 Jan '03

I'm trying to make a backtracking state monad using Ralf Hinze's backtracking monad transformer. My problem is that it won't backtrack very far. Suppose I try ( a >> b ) `mplus` c. If b fails, it should try c, but it doesn't rewind past a. My sample code is below. GHCI> c [0,1] match_1 -- (1 or 0) then 1, OK GHCI> c [1,0] match_2 -- (1 then 0) or (1,1), OK GHCI> c [1,1] match_2 -- (1 then 0) or (1,1), fails What have I misunderstood? cheers, Simon (A disclaimer in an attachment? - it wasn't my idea.) -- backtracking state monad -- requires -fglasgow-exts import qualified Monad as M import qualified Control.Monad.Trans as MT -- turn tracing on and off by uncommenting just one of the following lines import Debug.Trace( trace ) --trace s x = x -- -- Ralf Hinze's efficient backtracking monad transformer -- newtype BACKTR m a = BACKTR { mkBACKTR :: (forall b. (a -> m b -> m b) -> m b -> m b) } instance (Monad m) => Monad (BACKTR m) where return a = BACKTR (\c -> c a) m >>= k = BACKTR (\c -> mkBACKTR m (\a -> mkBACKTR (k a) c)) -- We don't use a Backtr class, but do it with the MonadPlus class, -- mzero is false (fail), -- mplus is ¦ (orelse) instance (Monad m) => M.MonadPlus (BACKTR m) where mzero = BACKTR (\c -> id) m1 `mplus` m2 = BACKTR (\c -> mkBACKTR m1 c . mkBACKTR m2 c) -- standard MonadTrans class has lift for promote, and doesn't have observe instance MT.MonadTrans BACKTR where lift m = BACKTR (\c f -> m >>= \a -> c a f) observe :: (Monad m) => BACKTR m a -> m a observe m = mkBACKTR m (\a f -> return a) (fail "false") -- -- State Monad -- data SM st a = SM (st -> (a,st)) -- The monadic type instance Monad (SM st) where -- defines state propagation SM c1 >>= fc2 = SM (\s0 -> let (r,s1) = c1 s0 SM c2 = fc2 r in c2 s1) return k = SM (\s -> (k,s)) -- extracts the state from the monad readSM :: SM st st readSM = SM (\s -> (s,s)) -- updates the state of the monad updateSM :: (st -> st) -> SM st () -- alters the state updateSM f = SM (\s -> ((), f s)) -- run a computation in the SM monad runSM :: st -> SM st a -> (a,st) runSM s0 (SM c) = c s0 -- backtracking state monad -- type NDSM st a = BACKTR (SM st) a readNDSM :: NDSM st st readNDSM = MT.lift readSM updateNDSM :: (st -> st) -> NDSM st () updateNDSM f = MT.lift (updateSM f) --run a computation in the NDSM monad runNDSM :: st -> NDSM st a -> (a,st) runNDSM s0 m = runSM s0 (observe m) -- -- the state -- type Bit = Int data CState = CState { ok :: Bool, remaining_data :: [Bit], history :: [String] -- log, kept in reverse } deriving Show initState xs = CState True xs [] -- prepend a message in the log logit :: CState -> String -> CState logit s logmsg = s { history = logmsg : (history s) } -- -- matching action -- match_bits :: [Bit] -> NDSM CState () match_bits xs = do s <- readNDSM let s' = logit s ("attempt match_bits " ++ show xs ++ " remaining: " ++ show (remaining_data s)) s'' = if xs == take (length xs) (remaining_data s') then s' { remaining_data = drop (length xs) (remaining_data s') } else s' { ok = False } if ok s'' then updateNDSM (\s -> s'') else trace (unlines $ "MATCH FAILED":(reverse $ history s'')) M.mzero -- -- test routines -- -- just fine match_1 = (match_bits [1] `M.mplus` match_bits [0]) >> match_bits [1] -- this one only rewinds past the [0] attempt, not the [1] attempt match_2 = ( (match_bits [1] >> match_bits [0]) `M.mplus` match_bits [1, 1] ) c :: [Bit] -> NDSM CState () -> ([Bit], [String]) c h hspec = let (v, s) = runNDSM (initState h) hspec in case (ok s) of True -> ([], "ok":(reverse $ history s)) _ -> ([(negate)1], ["fail"])

2 1