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

Discussion:

ducis

2018-11-18 15:31:06 UTC

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

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

Send Haskell-Cafe mailing list submissions to
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
You can reach the person managing the list at
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Haskell-Cafe digest..."
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
8. external git dependency source in .cabal (Fabien R)
----------------------------------------------------------------------
Message: 1
Date: Sat, 17 Nov 2018 15:21:53 -0800
Subject: [Haskell-cafe] Timing out a pure evaluation of an expression
I did not write myself
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
Subject: Re: [Haskell-cafe] Timing out a pure evaluation of an
expression I did not write myself
Content-Type: text/plain; charset="utf-8"
Hello Ryan.
Try evaluating the expression to normal form instead of weak head normal

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

The function `force` comes from the deepseq package. You can read the docs
http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html
I hope that helps.
Best regards,
Daniel

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
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
Subject: Re: [Haskell-cafe] Timing out a pure evaluation of an
expression I did not write myself
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 <

Hello Ryan.
Try evaluating the expression to normal form instead of weak head normal

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

The function `force` comes from the deepseq package. You can read the docs
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 <

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
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
Subject: Re: [Haskell-cafe] Timing out a pure evaluation of an
expression I did not write myself
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.

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 <

Hello Ryan.
Try evaluating the expression to normal form instead of weak head normal

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

The function `force` comes from the deepseq package. You can read the
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 <

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
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)
Subject: [Haskell-cafe] Specialize a function on types of arguments?
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
Subject: Re: [Haskell-cafe] Specialize a function on types of
arguments?
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
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
Subject: Re: [Haskell-cafe] Timing out a pure evaluation of an
expression I did not write myself
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

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.
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
Subject: [Haskell-cafe] external git dependency source in .cabal
Content-Type: text/plain; charset=utf-8
Hello,
source-repository head
type: git
location: <git URL of pack1>
executable myExe
build-depends: base==4.10.1.0, pack1 -any
pack1 -any
Any hint ?
--
Fabien
------------------------------
Subject: Digest Footer
_______________________________________________
Haskell-Cafe mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
------------------------------
End of Haskell-Cafe Digest, Vol 183, Issue 14
*********************************************

ducis

2018-11-18 15:32:38 UTC

Permalink

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 ([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

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

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

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

The function `force` comes from the deepseq package. You can read the docs
http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html
I hope that helps.
Best regards,
Daniel

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

Hello Ryan.
Try evaluating the expression to normal form instead of weak head normal

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

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

Hello Ryan.
Try evaluating the expression to normal form instead of weak head normal

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

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

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,

"eq1" and "eq2" into one function?
eq1 :: (Eq a)=>a->a->Bool
eq1 = (==)
eq2 :: (Eq a,Eq b)=>a->b->Bool
eq2 _ _ = False

f:: a -> b -> b
f x y = y
g:: a -> a -> a
g x y = x

but at least in the first case [which I've put second], "a" and "b" should be any types.

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

Anthony Clayden

2018-11-19 10:56:41 UTC

Permalink

Post by ducis
The top-level story is that I am trying to create a monad that somehow
records the "intermediate steps" of computation.

Uh-oh. That got into deep water surprisingly quickly. We seem to be a long
way from your O.P. already. I'm not sure I can help much/here are some
general remarks.

Your examples below are using Int and String, but I take it you're really
dealing with much more complex types than that(?) -- you mention parse
trees. The usual way to stack one type on top of another in steps is with
Monad Transformers. At the point of stacking a different type, is that a
fresh computation ignoring history? Or is it a computation on type `a` that
produces a `b`?

I'm not convinced a monad is the right thing here. Perhaps any passing
Categoristas could offer an opinion. The reason using a monad feels wrong
is because of all the `return`s and especially the `(return . ( f ))`s.

I'm also wondering if using a list for "intermediate steps" is worth it: if
in general each computation step might produce a different type, just stack
on a heterogeneous list (in which some adjacent cells might by coincidence
be the same type). See the `'[]` promoted DataKind.

Yes, if GHC messages are talking about IncoherentInstances you are in
trouble. GHC seems far too eager to suggest them. "Incoherent" is just as
bad as it sounds. Almost always you can get the instances to compile but
you still can't use them/it shifts the problem to somewhere else in your
code which is even harder to diagnose. And it's always possible to rejig
the code to avoid IncoherentInstances -- that is, presuming your intended
semantics is actually coherent ;-).

I think that rather than monad bind `(>>=)` :: m a -> (a -> m b) -> m b`,
you want a polymonad bind `(>>?) :: m a -> (a -> m2 b) -> m2 b` in which
`m2` stacks a b-history on top of the a-history from `m` (which of course
includes history from previous types as well).

Now you're in trouble: polymonads currently give typechecking severe
indigestion. Contrast that for ordinary monads it's the same `m` all along
the chain, any step that fixes the monad (including the expected overall
return type) will ripple it through the lot.

But it's not as indeterminate as that: you can calculate `m2` given `m`,
`b`. And you can back-calculate `m a` given `m2` -- presuming you're using
a simple stacking structure. Sounds like a job for Type Families and (if
you want to continue using `do` notation) Rebindable syntax. But then
beware all the warnings in the Users Guide.

AntC

Post by ducis
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

instance ForceDynList a where forceDynList

x = []
which is far from correct with error "Duplicate instance declarations"

Dan Burton

2018-11-18 17:34:33 UTC

Permalink

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

Post by ducis
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

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

instance ForceDynList a where forceDynList

x = []
which is far from correct with error "Duplicate instance declarations"
Thanks!
Ducis
--
-----------------------------

Send Haskell-Cafe mailing list submissions to
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
You can reach the person managing the list at
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Haskell-Cafe digest..."
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
8. external git dependency source in .cabal (Fabien R)
----------------------------------------------------------------------
Message: 1
Date: Sat, 17 Nov 2018 15:21:53 -0800
Subject: [Haskell-cafe] Timing out a pure evaluation of an expression
I did not write myself
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

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

The function `force` comes from the deepseq package. You can read the docs
http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html
I hope that helps.
Best regards,
Daniel

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

Hello Ryan.
Try evaluating the expression to normal form instead of weak head normal

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

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

Hello Ryan.
Try evaluating the expression to normal form instead of weak head normal

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

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

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,

"eq1" and "eq2" into one function?
eq1 :: (Eq a)=>a->a->Bool
eq1 = (==)
eq2 :: (Eq a,Eq b)=>a->b->Bool
eq2 _ _ = False

f:: a -> b -> b
f x y = y
g:: a -> a -> a
g x y = x

but at least in the first case [which I've put second], "a" and "b" should be any types.

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

_______________________________________________
Haskell-Cafe mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

ducis

2018-11-19 02:34:42 UTC

Permalink

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" <***@gmail.com> åéïŒ

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 <***@126.com> 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 ([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

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

Send Haskell-Cafe mailing list submissions to
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
You can reach the person managing the list at
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Haskell-Cafe digest..."
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
8. external git dependency source in .cabal (Fabien R)
----------------------------------------------------------------------
Message: 1
Date: Sat, 17 Nov 2018 15:21:53 -0800
Subject: [Haskell-cafe] Timing out a pure evaluation of an expression
I did not write myself
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

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

The function `force` comes from the deepseq package. You can read the docs
http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html
I hope that helps.
Best regards,
Daniel

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

Hello Ryan.
Try evaluating the expression to normal form instead of weak head normal

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

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

Hello Ryan.
Try evaluating the expression to normal form instead of weak head normal

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

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

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,

"eq1" and "eq2" into one function?
eq1 :: (Eq a)=>a->a->Bool
eq1 = (==)
eq2 :: (Eq a,Eq b)=>a->b->Bool
eq2 _ _ = False

f:: a -> b -> b
f x y = y
g:: a -> a -> a
g x y = x

but at least in the first case [which I've put second], "a" and "b" should be any types.

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

Olaf Klinke

2018-11-19 21:03:53 UTC

Permalink

Post by ducis
The top-level story is that I am trying to create a monad that somehow
records the "intermediate steps" of computation.

If it is only for knowing where things went wrong, isn't that what the Either monad is for? The semantics of (Either YourErrorType) is that it returns `Right result' when all steps went through, and `Left errmsg' from the first place where something went wrong. You'd have to define YourErrorType to incorporate the relevant error information.

If you also want something like a call stack, i.e. a message like
"computation failed in step 3 with message: foo"
Then you need to stack a state transformer on top, e.g. StateT CallStack (Either YourErrorType) which decodes to
CallStack -> Either YourErrorType (resultType,CallStack)

An example using mtl transformers:

import Control.Monad.State.Strict
import Control.Monad.Except
type CallStack = (Int,[String])
type YourErrorType = String
type M a = StateT CallStack (Except YourError) a

fancyFunc :: Show a => (a -> b) -> (a -> M b)
fancyFunc f a = do
(n,stack) <- get
put (n+1,show a : stack)
return b

fancyMaybe :: Show a => (a -> Maybe b) -> (a -> M b)
fancyMaybe f a = do
(n,stack) <- get
case (f a) of
Nothing -> throwError $ "Failed at step "++(show n)++" on input "++(show a)
Just b -> do
put (n+1,show a : stack)
return b

runChainOfComputations = runStateT (1,[])

I once wrote a type 'ProvenienceT' which is a bit fancier than the above. It is a monadic EDSL and constructs a graph where nodes are (Markup of) intermediate steps of a computation and where edges are (user-supplied descriptions of) functions. It is inspired by the Javelin software of the 80s which pre-dates Excel spreadsheets. The result can be rendered as html. Can provide code if anyone is interested.

Cheers,
Olaf

Anthony Clayden

2018-11-20 03:03:25 UTC

Permalink

* The top-level story is that I am trying to create a monad that somehow*

*>*>* records the "intermediate steps" of computation.*

If it is only for knowing where things went wrong, ...

Thanks Olaf, no I think Ducis wants to stack the whole history of the
computation.

If ... Then you need to stack a state transformer on top,

Yes a monad transformer might be it. Thank you for the example.

As per my previous message, I'm not convinced it needs monads at all.
Here's a dumb approach as a straw man, showing that type-changing
steps are nothing special (or perhaps I mean type-preserving steps are
nothing special ;-). Ducis could explain why this won't do

nil = ()

cons x l = (x, l)

start :: a -> (a,())

start x = cons x nil -- i.e. singleton x

infixl 0 $>>

($>>) :: (b, _a) -> (b -> c) -> (c, (b, _a))

xs@(x, z) $>> f = cons (f x) xs

eg = start 1 $>> (+ 1) $>> (+ 3) $>> double $>> show

===> ("10",(10,(5,(2,(1,())))))

I chose ($>>) to be similar to ($>) from the Control.FPipe package
"trivial F#-style pipes for function composition and application".

You could use Datakind `'[]` instead of the 'poor man's heterogeneous
list' I've used, but that seems over-engineering.

AntC