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

ducis ducis_cn at 126.com
Sun Nov 18 15:31:06 UTC 2018


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 at haskell.org wrote:
>Send Haskell-Cafe mailing list submissions to
>	haskell-cafe at 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 at haskell.org
>
>You can reach the person managing the list at
>	haskell-cafe-owner at 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 at 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 <ryan.reich at gmail.com>
>To: haskell-cafe <haskell-cafe at haskell.org>
>Subject: [Haskell-cafe] Timing out a pure evaluation of an expression
>	I did	not write myself
>Message-ID:
>	<CAO8Ocku+=6GkyW-z8bShr7OSJppT_yPmrkcknF=UXYDn7+KBQg at mail.gmail.com>
>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
>-------------- next part --------------
>An HTML attachment was scrubbed...
>URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181117/d1121b86/attachment-0001.html>
>
>------------------------------
>
>Message: 2
>Date: Sun, 18 Nov 2018 01:51:58 +0100
>From: Daniel Díaz Casanueva <dhelta.diaz at gmail.com>
>To: ryan.reich at gmail.com
>Cc: haskell-cafe <haskell-cafe at haskell.org>
>Subject: Re: [Haskell-cafe] Timing out a pure evaluation of an
>	expression I did not write myself
>Message-ID:
>	<CAJFXAQimv-mJB7e1WMzz1urduRr5MV5mewVhhaCH52rFxJtY1w at mail.gmail.com>
>Content-Type: text/plain; charset="utf-8"
>
>Hello Ryan.
>
>Try evaluating the expression to normal form instead of weak head normal
>form in your expression. So:
>
>>>> timeout 1 $ evaluate $ force $ let x = 0 : x in last x
>
>The function `force` comes from the deepseq package. You can read the docs
>here:
>http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html
>
>I hope that helps.
>
>Best regards,
>Daniel
>
>Am So., 18. Nov. 2018 um 00:22 Uhr schrieb Ryan Reich <ryan.reich at gmail.com
>>:
>
>> 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
>> _______________________________________________
>> Haskell-Cafe mailing list
>> To (un)subscribe, modify options or view archives go to:
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>> Only members subscribed via the mailman list are allowed to post.
>-------------- next part --------------
>An HTML attachment was scrubbed...
>URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181118/73b143bd/attachment-0001.html>
>
>------------------------------
>
>Message: 3
>Date: Sun, 18 Nov 2018 01:55:56 +0100
>From: Daniel Díaz Casanueva <dhelta.diaz at gmail.com>
>To: ryan.reich at gmail.com
>Cc: haskell-cafe <haskell-cafe at haskell.org>
>Subject: Re: [Haskell-cafe] Timing out a pure evaluation of an
>	expression I did not write myself
>Message-ID:
>	<CAJFXAQiDqmsgYJpQB7KRBuiVR5wvwAN-y35r08_Q_TmSkAmyBg at mail.gmail.com>
>Content-Type: text/plain; charset="utf-8"
>
>Actually, after reading the question again, it seems like my response
>wasn't quite right. You are not actually building the list. In that case, I
>am as confused as you. :)
>
>Sorry!
>
>Am So., 18. Nov. 2018 um 01:51 Uhr schrieb Daniel Díaz Casanueva <
>dhelta.diaz at gmail.com>:
>
>> Hello Ryan.
>>
>> Try evaluating the expression to normal form instead of weak head normal
>> form in your expression. So:
>>
>> >>> timeout 1 $ evaluate $ force $ let x = 0 : x in last x
>>
>> The function `force` comes from the deepseq package. You can read the docs
>> here:
>> http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html
>>
>> I hope that helps.
>>
>> Best regards,
>> Daniel
>>
>> Am So., 18. Nov. 2018 um 00:22 Uhr schrieb Ryan Reich <
>> ryan.reich at gmail.com>:
>>
>>> 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
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> To (un)subscribe, modify options or view archives go to:
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>>> Only members subscribed via the mailman list are allowed to post.
>>
>>
>-------------- next part --------------
>An HTML attachment was scrubbed...
>URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181118/cc14c57d/attachment-0001.html>
>
>------------------------------
>
>Message: 4
>Date: Sat, 17 Nov 2018 16:57:56 -0800
>From: Ryan Reich <ryan.reich at gmail.com>
>To: dhelta.diaz at gmail.com
>Cc: haskell-cafe <haskell-cafe at haskell.org>
>Subject: Re: [Haskell-cafe] Timing out a pure evaluation of an
>	expression I did not write myself
>Message-ID:
>	<CAO8OckswZrJ2EtvQvfTZOKyi78=TqS0dGjgyKYy0fTf38KAgVg at mail.gmail.com>
>Content-Type: text/plain; charset="utf-8"
>
>I was just about to reply with an observation to that effect :)  The place
>that I'd want to put 'force' is actually inside the 'let' clause, which of
>course you can't do just by applying a function.  The expression as a whole
>is just an Integer.
>
>On Sat, Nov 17, 2018 at 4:56 PM Daniel Díaz Casanueva <dhelta.diaz at gmail.com>
>wrote:
>
>> Actually, after reading the question again, it seems like my response
>> wasn't quite right. You are not actually building the list. In that case, I
>> am as confused as you. :)
>>
>> Sorry!
>>
>> Am So., 18. Nov. 2018 um 01:51 Uhr schrieb Daniel Díaz Casanueva <
>> dhelta.diaz at gmail.com>:
>>
>>> Hello Ryan.
>>>
>>> Try evaluating the expression to normal form instead of weak head normal
>>> form in your expression. So:
>>>
>>> >>> timeout 1 $ evaluate $ force $ let x = 0 : x in last x
>>>
>>> The function `force` comes from the deepseq package. You can read the
>>> docs here:
>>> http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html
>>>
>>> I hope that helps.
>>>
>>> Best regards,
>>> Daniel
>>>
>>> Am So., 18. Nov. 2018 um 00:22 Uhr schrieb Ryan Reich <
>>> ryan.reich at gmail.com>:
>>>
>>>> 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
>>>> _______________________________________________
>>>> Haskell-Cafe mailing list
>>>> To (un)subscribe, modify options or view archives go to:
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>>>> Only members subscribed via the mailman list are allowed to post.
>>>
>>>
>-------------- next part --------------
>An HTML attachment was scrubbed...
>URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181117/6f7e8165/attachment-0001.html>
>
>------------------------------
>
>Message: 5
>Date: Sun, 18 Nov 2018 12:01:25 +0800 (CST)
>From: ducis <ducis_cn at 126.com>
>To: haskell-cafe at haskell.org
>Subject: [Haskell-cafe] Specialize a function on types of arguments?
>Message-ID: <552773e2.1be5.16724faf3d0.Coremail.ducis_cn at 126.com>
>Content-Type: text/plain; charset="gbk"
>
>Hi, everyone,
>
>Is it possible to make combine the following "f" and "g" into one function?
>f:: a -> b -> b 
>f x y = y       
>g:: a -> a -> a 
>g x y = x       
>
>Or similarly, "eq1" and "eq2" into one function?
>eq1 :: (Eq a)=>a->a->Bool     
>eq1 = (==)                    
>eq2 :: (Eq a,Eq b)=>a->b->Bool
>eq2 _ _ = False               
>
>Looks like it would require some typeclasses, but at least in the first case, "a" and "b" should be any types.
>
>Best!
>-------------- next part --------------
>An HTML attachment was scrubbed...
>URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181118/b642c82a/attachment-0001.html>
>
>------------------------------
>
>Message: 6
>Date: Sun, 18 Nov 2018 17:40:51 +1300
>From: Anthony Clayden <anthony_clayden at clear.net.nz>
>To: haskell-cafe at haskell.org
>Subject: Re: [Haskell-cafe] Specialize a function on types of
>	arguments?
>Message-ID:
>	<CAM7nRYRGswE+hepEttL6ccw=bKatwBcBqe9fG4VphSFDYOyD1A at mail.gmail.com>
>Content-Type: text/plain; charset="utf-8"
>
>Hi Ducis,
>
>> Is it possible to make combine the following "f" and "g" into one
>function?
>
>"combine" is vague. You perhaps mean: look at the types of the arguments,
>and choose one function or the other?
>
>> Looks like it would require some typeclasses,
>
>I'll answer the question as put (yes it needs typeclasses), but I can't
>help feel there's a backstory, and you might well be doing something that
>could be done better, if I knew what you're trying to achieve. Let's take
>the second one first
>
>> "eq1" and "eq2" into one function?
>> eq1 :: (Eq a)=>a->a->Bool
>> eq1 = (==)
>> eq2 :: (Eq a,Eq b)=>a->b->Bool
>> eq2 _ _ = False
>
>class Eqbytype a b  where
>  eqt :: a -> b -> Bool
>
>instance {-# OVERLAPPING #-} (Eq a) => Eqbytype a a  where
>  eqt = (==)
>
>instance {-# OVERLAPPABLE #-} Eqbytype a b  where
>  eqt _ _ = False
>
>Look at the Users Guide for what the OVERLAPPING/OVERLAPPABLE pragmas are doing.
>
>Note for the first instance I repeated type var `a` in the head,
>meaning: pick this instance if the two arguments to the method are of
>the same type.
>
>Note for the second instance, I didn't bother with the `Eq`
>constraint, since we can't compare values of distinct types.
>
>
>> f:: a -> b -> b
>> f x y = y
>> g:: a -> a -> a
>> g x y = x
>So you want same argument types to drive which argument to pick? Or
>you want the return type to drive which argument? That's possible:
>look at the definition of class `Read` in the Prelude. Again we can
>pick instances depending on a repeated type. But your requirements are
>not clear.
>
>
>> but at least in the first case [which I've put second], "a" and "b" should be any types.
>
>No they can't: as you state it, you require either all three the same,
>or the second to be the same as the return type.
>
>Come back and ask a more focussed question once you've worked through the
>above. (And explain why you're asking.) The above code is untested, BTW.
>
>AntC
>-------------- next part --------------
>An HTML attachment was scrubbed...
>URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181118/d274cd13/attachment-0001.html>
>
>------------------------------
>
>Message: 7
>Date: Sun, 18 Nov 2018 09:22:08 +0100
>From: arjenvanweelden at gmail.com
>To: haskell-cafe at haskell.org
>Subject: Re: [Haskell-cafe] Timing out a pure evaluation of an
>	expression I did not write myself
>Message-ID: <27e9100ff70dd67791ed34e152c58239499bba65.camel at gmail.com>
>Content-Type: text/plain; charset="UTF-8"
>
>On Sat, 2018-11-17 at 15:21 -0800, Ryan Reich wrote:
>> 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
>> 
>If you are using GHC, the -fno-omit-yields compiler option might be of
>help, which does not optimize out the allocation check that is also
>used for interrupting threads.
>
>See also: 
>https://stackoverflow.com/questions/34317730/haskell-timeout-diverging-computation
>
>Are you using the threaded runtime (GHC option -threaded)?
>
>hope this helps, Arjen
>
>
>
>------------------------------
>
>Message: 8
>Date: Sun, 18 Nov 2018 12:53:50 +0100
>From: Fabien R <theedge456 at free.fr>
>To: haskell-cafe at haskell.org
>Subject: [Haskell-cafe] external git dependency source in .cabal
>Message-ID: <660c8ca8-3879-b5e5-52c4-682f6e4be80b at free.fr>
>Content-Type: text/plain; charset=utf-8
>
>Hello,
>I'm trying to reference an external source of a package within a sandbox, using cabal 2.0.0.1:
>
>source-repository head
>   type: git
>   location: <git URL of pack1>
>
>executable myExe
>    build-depends: base==4.10.1.0, pack1 -any
>
>But "cabal -v install --only-dependencies" fails:
>
>cabal: Encountered missing dependencies:
>pack1 -any
>
>Any hint ?
>
>--
>Fabien
>
>
>------------------------------
>
>Subject: Digest Footer
>
>_______________________________________________
>Haskell-Cafe mailing list
>Haskell-Cafe at haskell.org
>http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
>------------------------------
>
>End of Haskell-Cafe Digest, Vol 183, Issue 14
>*********************************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181118/bf11e045/attachment.html>


More information about the Haskell-Cafe mailing list