StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
15015601
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
4
CommunityOwnedDate
CreationDate
2013-02-22T01:56:48.043
FavoriteCount
0
LastActivityDate
2013-02-22T04:33:52.753
LastEditDate
2013-02-22T04:33:52.753
LastEditorUserId
476408
OwnerUserId
476408
ParentId
15014517
PostTypeId
2
Score
6
ViewCount
0
LastEditorDisplayName
text
Body
<p>It looks like you want to (a) sequence some transformations and (b) short-circuit predicate failure at various stages. This whole process is parametric over the "contained" type (which is Int here) and the predicate.</p> <p>Let's dive in.</p> <h2>I</h2> <p>The primary effect we're controlling here is failure, so <code>Maybe</code> is a great place to start. It's <code>Monad</code> instance lets us compose various <code>Maybe</code>-producing computations.</p> <pre><code>-- some pure computations f, g, h :: a -> a -- ... lifted and sequenced! may :: a -> Maybe a may = (return . f) >=> (return . g) >=> (return . h) </code></pre> <p>This is a very ceremonial way of writing <code>(h . g . f)</code> since we're just using completely general "monadic" (really, <code>Kleisli</code>) composition and no special effects.</p> <h2>II.</h2> <p>Given a predicate <code>p :: a -> Bool</code>, we can start to fail. The first way to do this would be to use <code>Maybe</code>'s <code>MonadPlus</code> instance and <code>guard :: MonadPlus m => Bool -> m ()</code>.</p> <pre><code>\a -> do x <- return (f a) guard (p x) y <- return (g x) guard (p y) z <- return (h y) guard (p z) return z </code></pre> <p>But we've obviously got a fairly repeated pattern going on here---at every "composition boundary" of pure functions we perform our predicate and maybe fail. This is a strong commingling of <code>Reader</code>-like and <code>Maybe</code>-like effects just like you thought, but it doesn't have quite the same <code>Monad</code>ic semantics as either of those or their stack. Can we capture it some other way?</p> <h2>III.</h2> <p>Well, let's try wrapping them up.</p> <pre><code>newtype OurMonad a = OM { getOM :: MaybeT (Reader (a -> Bool)) a } </code></pre> <p>Now <code>OurMonad</code> is a <code>newtype</code> around the monad transformer stack including <code>Reader</code> and <code>Maybe</code>. We'll be able to take advantage of that in order to write a highly general "run" function, <code>runOurMonad :: (a -> Bool) -> OurMonad a -> Maybe a</code>.</p> <p>Or, rather, it sort of feels like we could, right? I want to argue that we can't, actually. The reason is that in order to write a <code>Monad</code> instance we have to have a <code>Functor</code> instance* which means that given any function mapping <code>a -> b</code> we need to be able to map <code>OM a -> OM b</code>. The problem is that we don't generally know how to generalize our predicate! I know no way to write a function <code>(a -> b) -> (a -> Bool) -> b -> Bool</code> unless we also have a function <code>b -> a</code>**.</p> <p>So we're stuck trying to generalize this to a <code>Monad</code>. I don't think it is one.</p> <h2>IV.</h2> <p>But your example didn't actually need the full generality of Monad—we know all of our pure transformations are <code>Endo</code>, i.e. of type <code>a -> a</code>. That's one way our single predicate could be sufficient! We can take advantage of the type homogeneity to write a list of our <code>Endo</code>s as <code>[a -> a]</code>. So let's just define what we need a little more directly as a <code>fold</code> over that list:</p> <pre><code>stepGuarded :: (a -> Bool) -> a -> [a -> a] -> Maybe a stepGuarded pred = foldM $ \a f -> mfilter pred (return $ f a) stepGuarded (`elem` [3, 7, 9]) 3 [ (+1), (*2) ] -- Nothing stepGuarded (`elem` [4, 8, 9]) 3 [ (+1), (*2) ] -- Just 8 </code></pre> <p>* n.b. Not technically true, but theoretically and practically if we can't write a <code>Functor</code> instance then we'll get stuck writing a <code>Monad</code> instance, too.</p> <p>** Technically, this is still a categorical <code>Functor</code>, it's just contravariant whereas <code>Functor</code> and <code>Monad</code> assume the functor is covariant. We can generalize all of this to have functors-on-isomorphisms, Edward Kmett calls these <code>ExFunctor</code>s I think and you get to define <code>xmap :: (a -> b) -> (b -> a) -> f a -> f b</code> instead, which is nice.</p>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POParameterized Maybe monad
  singulars
  PostTypePostTypeId
  PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USJ. Abrahamson
UserOwnerUserId
1. USJ. Abrahamson
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POParameterized Maybe monad
  singulars
  PostTypePostTypeId
  PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
  singulars
  PostPostId
  PO
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTUpMod
2. VO
  singulars
  PostPostId
  PO
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTUpMod
3. VO
  singulars
  PostPostId
  PO
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTAcceptedByOriginator
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.