Re: [Haskell-cafe] Haskell-Cafe Digest, Vol 183, Issue 14

Thanks for pointing that out. I haven't been seriously dealing with the monad laws as the code is not even working yet. But I guess it should be able to adjust the definition to fit the monad laws. Say, with current definition we have return 1 >>= return === WH ([],1) >>= \x->WH ([],x) === WH ([1],1) But if we change the definition of >>= to WH (h,a) >>= fm = WH (h1++if a == b then coerceHistory h else coerceHistory (a:h),b) where ... then return 1 >>= return === WH ([],1) while return 1 >>= return.(+2) === WH ([1],3) Of course this may break in other cases. The reason is that (apart from reducing explicit recording) I have used the Maybe monad extensively to express "computation that may fail" in existing code, and in the end I would like something which not only handles the possible failure also records history based on this WithHistory monad. 在 2018-11-19 01:34:33，"Dan Burton" 写道： I would recommend against this, since having >>= "record history" breaks monad laws. Particularly, this one: f >>= return === f Instead, why not use a plain old `Writer [Dynamic]` monad and explicitly `tell` whenever you want to add a historical record? import Control.Monad.Trans.Writer (Writer, tell) import Data.Dynamic (Dynamic, toDyn) import Data.Typeable (Typeable) newtype WithHistory b = WH (Writer [Dynamic] b) deriving (Functor, Applicative, Monad) tellHistory :: Typeable a => a -> WithHistory () tellHistory a = WH $ tell [toDyn a] someComputation :: WithHistory Int someComputation = do let x = 1 tellHistory x let y = x + 1 tellHistory y let yStr = show y tellHistory yStr let z = y + 3 tellHistory z return z -- Dan Burton On Sun, Nov 18, 2018 at 10:31 AM ducis wrote: Hi, Anthony, The top-level story is that I am trying to create a monad that somehow records the "intermediate steps" of computation. e.g. something like Prelude> return 1 ([],1) Prelude> return 1 >>= return.(+1) ([1],2) Prelude> return 1 >>= return.(+1)>>=return.(+3) ([2,1],5) (the list has the intermediate steps placed right-to-left so that new steps are appended to the left of the older steps) Of course all "intermediate steps of computation" actually form a graph, but we are frequently focused on, say, the transformation of a parse tree, where we want to take a series of snapshots of one "thing". Since a "lifted function" (e.g. return.(+1)) has in general the type a->m b, there are two ways to deal with input and output being not necessarily equal. The first approach I tried is to only record latest steps starting with the last change of type

newtype WithHistory b = WH ([b], b)

and just discard the older steps when the input and output are of different types.

newtype WithHistory b = WH ([b], b) deriving (Show,Eq) instance Monad WithHistory where return b = WH ([], b) (>>=) :: forall a b. WithHistory a -> (a -> WithHistory b) -> WithHistory b WH (h,a) >>= fm = WH (h1++coerceHistory (a:h),b) where WH (h1, b) = fm a class CoerceHistory a b where coerceHistory :: [a] -> [b] instance CoerceHistory a a where coerceHistory = id instance CoerceHistory a b where coerceHistory _ = [] I have got the coerceHistory function to (appear to) work in GHCi *Main> coerceHistory [2::Int] :: [Int] [2] *Main> coerceHistory "c" :: [Int] [] But the Monad instanciation does not really work. GHC(7.6.3) hints for -XIncoherentInstances, which when enabled seems to force the (>>=) to always use the instance of coerceHistory returning []

The second approach is to use [Dynamic] for steps, i.e.,

newtype WithHistory b = WH ([Dynamic], b) instance Monad WithHistory where return b = WH ([], b) WH (h,a) >>= fm = WH (h1++forceDynList a++h, b) where WH (h1, b) = fm a and presumably

class ForceDynList a where forceDynList :: a -> [Dynamic] instance (Typeable a) => ForceDynList a where forceDynList x = [toDyn x] instance ForceDynList a where forceDynList x = [] which is far from correct with error "Duplicate instance declarations"

Thanks! Ducis -- ----------------------------- At 2018-11-18 20:00:01, haskell-cafe-request@haskell.org wrote:

Send Haskell-Cafe mailing list submissions to haskell-cafe@haskell.org

To subscribe or unsubscribe via the World Wide Web, visit http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe or, via email, send a message with subject or body 'help' to haskell-cafe-request@haskell.org

You can reach the person managing the list at haskell-cafe-owner@haskell.org

When replying, please edit your Subject line so it is more specific than "Re: Contents of Haskell-Cafe digest..."

Today's Topics:

1. Timing out a pure evaluation of an expression I did not write myself (Ryan Reich) 2. Re: Timing out a pure evaluation of an expression I did not write myself (Daniel Díaz Casanueva) 3. Re: Timing out a pure evaluation of an expression I did not write myself (Daniel Díaz Casanueva) 4. Re: Timing out a pure evaluation of an expression I did not write myself (Ryan Reich) 5. Specialize a function on types of arguments? (ducis) 6. Re: Specialize a function on types of arguments? (Anthony Clayden) 7. Re: Timing out a pure evaluation of an expression I did not write myself (arjenvanweelden@gmail.com) 8. external git dependency source in .cabal (Fabien R)

----------------------------------------------------------------------

Message: 1 Date: Sat, 17 Nov 2018 15:21:53 -0800 From: Ryan Reich To: haskell-cafe Subject: [Haskell-cafe] Timing out a pure evaluation of an expression I did not write myself Message-ID: Content-Type: text/plain; charset="utf-8"

I want to time out a pure computation. My experience, and that described in various previous questions here and elsewhere (the best of which is https://mail.haskell.org/pipermail/haskell-cafe/2011-February/088820.html), is that this doesn't always work: for instance,

...

...

...

timeout 1 $ evaluate $ let x = 0 : x in last x

does not time out because, apparently, the fact that the expression evaluates in constant space (i.e. never allocates) means that it never yields to the timeout monitor thread that would kill it.

The solution that is described in the other iterations is to embed checkpoints in the expression that do allocate, giving the RTS a chance to switch contexts. However, in my application, the expression is /arbitrary/ and I do not have the freedom to inject alterations into it. (Don't argue this point, please. The expression is arbitrary.)

How can I time out a tight loop like the above? Clearly, it can be done, because I can, say, alt-tab over to another terminal and kill the process, which exploits the operating system's more aggressively pre-emptive scheduling. Is there a solution using bound threads, say 'forkOS' instead of 'forkIO' in the implementation of 'timeout'? Unix signals? Some FFI-based workaround? Etc. Keep in mind that notwithstanding that comment, I don't actually want to kill the whole process, but just the one evaluation.

Thanks in advance, Ryan Reich