<div><br></div><div><br><div class="gmail_quote"><div dir="ltr">On Mon, 19 Nov 2018 at 4:33 AM, ducis wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:Arial"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:Arial"><div><br>The top-level story is that I am trying to create a monad that somehow records the "intermediate steps" of computation.</div></div></div></blockquote><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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`?</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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 ;-).</div><div dir="auto"><br></div><div dir="auto">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).</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto">AntC</div><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:Arial"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:Arial"><div><br>e.g. something like<br>Prelude> return 1 <br></div><div>([],1)<br>Prelude> return 1 >>= return.(+1)<br>([1],2)<br>Prelude> return 1 >>= return.(+1)>>=return.(+3)<br>([2,1],5)<br></div><div>(the list has the intermediate steps placed right-to-left so that new steps are appended to the left of the older steps)<br>Of course all "intermediate steps of computation" actually form a graph, but we are frequently focused on, say, <br>the transformation of a parse tree, where we want to take a series of snapshots of one "thing".<br><br>Since a "lifted function" (e.g. return.(+1)) has in general the type a->m b, there are two ways<br>to deal with input and output being not necessarily equal.<br><br>The first approach I tried is to only record latest steps starting with the last change of type<br>> newtype WithHistory b = WH ([b], b)  <br></div><div>and just discard the older steps when the input and output are of different types.<br>> newtype WithHistory b = WH ([b], b) deriving (Show,Eq)                                      <br>> instance Monad WithHistory where                        <br>>    return b = WH ([], b)   <br>>    (>>=) :: forall a b. WithHistory a -> (a -> WithHistory b) -> WithHistory b              <br>>    WH (h,a) >>= fm = WH (h1++coerceHistory (a:h),b)    <br>>       where <br>>       WH (h1, b) = fm a <br>>    class CoerceHistory a b  where      <br>>    coerceHistory :: [a] -> [b]      <br>>    instance CoerceHistory a a  where   <br>>    coerceHistory = id               <br>>    instance CoerceHistory a b  where    <br>>    coerceHistory _ = []<br>I have got the coerceHistory function to (appear to) work in GHCi<br>*Main> coerceHistory [2::Int] :: [Int]                        <br>[2]                                                           <br>*Main> coerceHistory "c" :: [Int]                             <br>[]                                                            <br>But the Monad instanciation does not really work.<br>GHC(7.6.3) hints for -XIncoherentInstances, which when<br>enabled seems to force the (>>=) to always use the instance<br>of coerceHistory returning []<br><br>The second approach is to use [Dynamic] for steps, i.e.,<br>> newtype WithHistory b = WH ([Dynamic], b)<br>> instance Monad WithHistory where<br>>    return b = WH ([], b)   <br>>    WH (h,a) >>= fm = WH (h1++forceDynList a++h, b)<br>>       where WH (h1, b) = fm a<br>and presumably<br></div><div>> class ForceDynList a                                   where forceDynList :: a -> [Dynamic] <br>> instance (Typeable a) => ForceDynList a    where forceDynList x = [toDyn x]<br>> instance ForceDynList a                              where forceDynList x = []<br>which is far from correct with error "Duplicate instance declarations"<br><br></div></div></div></blockquote></div></div>