Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the name of this monad-like functional programming pattern?

Tags:

I have occasionally encountered a pattern in code which resembles a monad but does not keep a consistent type across >>=.

Here is the simplest example I could come up with:

(First some type-level booleans:

data TyT = TyT
data TyF = TyF

class TyOr a b c | a b -> c

instance TyOr TyF TyF TyF
-- rest similarly

)

Now here is our "monad" type constructor:

data Marked p a = Marked a
    deriving (Show)

For a given p, Marked p is a * -> * which acts very much like m in a monad, but different, as occurs next, when we define "bind":

(>>%) :: (TyOr p q r) => Marked p a -> (a -> Marked q b) -> Marked r b
(Marked x) >>% f = Marked y where Marked y = f x

What's different here is that the result of >>% has a different type constructor than the arguments. Other than that it's basically a monad.

We could use it like this:

a :: Marked TyF Int
a = Marked 5

f :: Int -> Marked TyT Int
f x = Marked (x + 1)

ghci> a >>% f
Marked 6

ghci> :t a >>% f
a >>% f :: Marked TyT Int

(This was inspired by outis's observation that Python's "with" can't be a monad because it changes the type, but I've seen it in other (simpler) ways too).

like image 911
Owen Avatar asked Aug 21 '11 00:08

Owen


People also ask

What are monads in functional programming?

In functional programming, a monad is a software design pattern with a structure that combines program fragments (functions) and wraps their return values in a type with additional computation.

What is a monad example?

Monads are simply a way to wrapping things and provide methods to do operations on the wrapped stuff without unwrapping it. For example, you can create a type to wrap another one, in Haskell: data Wrapped a = Wrap a. To wrap stuff we define return :: a -> Wrapped a return x = Wrap x.

What is monad structure?

A monad is an algebraic structure in category theory, and in Haskell it is used to describe computations as sequences of steps, and to handle side effects such as state and IO. Monads are abstract, and they have many useful concrete instances. Monads provide a way to structure a program.

Is map a monad?

Map is not one of the defining properties of monads, however, because it's technically just a special case of FlatMap. A lifting function like Unit will wrap its object in a container, even if that object is itself the same type of container.


1 Answers

Well, it's closely related to monads in some sense, just incompatible with the Monad type class. In particular, we can note the following parallels:

  • Monoids have an associative operation with identity defined on values of a consistent type: mappend :: a -> a -> a and mempty :: a.

  • Monads have an associative operation with identity defined on type constructors, e.g.: join :: m (m a) -> m a and return :: a -> m a.

  • Functions--really, arrows in a category--have an associative operation and identity, but the associative operation is indexed by the objects of the category, which here means "types": (.) :: arr b c -> arr a b -> arr a c and id :: arr a a.

...so what would a monad whose join is indexed by types be? Hm.

A few references you might find interesting, exploring related concepts:

  • A Neighborhood of Infinity: Beyond Monads
  • via Lambda the Ultimate: Parameterized Notions of Computation
  • The Comonad.Reader: Parameterized Monads in Haskell
  • Oleg: Variable (type) State "Monad"
  • via Lambda the Ultimate: Kleisli Arrows of Outrageous Fortune

post scriptum -- You said this in a comment on the question:

You're right. I actually want to fix that to be more monad-like though, even though I'm not really "using" monads. I'll edit it. Though I would have more or less the same question about Applicatives.

Actually, limiting things to Applicative changes matters significantly! The difference between a -> Marked p b and Marked p (a -> b) is that, in the former, the properties of the Marked p structure can depend on the a parameter; whereas in the latter, the marking is independent of the function's arguments. The independence means that the two can treated separately, which simplifies matters considerably; noting that any value of type a is isomorphic to a function of type () -> a, you can probably turn it into some sort of two-tiered version of Arrow in a straightforward manner.

On the other hand, involving Monad implies some degree of interleaving between the functions and the marking context, which complicates matters for reasons similar to those discussed in the answers to this question.

like image 52
C. A. McCann Avatar answered Dec 07 '22 13:12

C. A. McCann