Satisfying monad laws without a type constructor

Question

Given e.g. a type like

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a

I can easily write instances for Functor, Applicative, Monad, etc.

But if the "contained" type is predetermined, e.g.

data StringTree = Branch StringTree StringTree
                | Leaf String

I lose the ability to write these instances.

If I were to write functions for my StringTree type

stringTreeReturn :: String -> StringTree
stringTreeBind   :: String -> (String -> StringTree) -> StringTree
stringTreeFail   :: String -> StringTree
-- etc.

that satisfied the monad laws, could I still say that StringTree is a monad?

Answer 1

No. You're looking at the difference between a type and a kind. Simplistically, a kind is the way that Haskell classifies types, so it's a level of abstraction above types. ghci can help.

:type stringReturn
stringReturn :: String -> StringTree
:type Functor
<interactive>:1:1: Not in scope: data constructor `Functor'

So right off the bat, we can see that a function, which has a type, is an entirely different thing than a type, which has a kind.

We can also ask ghci about kinds.

:kind Functor
Functor (* -> *) -> Constraint
:kind StringTree
StringTree :: *
:kind Tree
Tree :: * -> *

Kinds use * for variables in their notation. We can see from the interaction above that Functor expects a type that is parameterized over one argument. We can also see that StringTree doesn't take any parameters, and Tree takes one.

That's a long way of expressing and unpacking your question, but hopefully it shows the difference between types and kinds.

Answer 2

Tree a isn't a monad, either generally or for any particular a, Tree itself is a monad. A monad isn't a type, it's a correspondence between any type and a "monadic version" that type. For example, Integer is the type of integers, and Maybe Integer is the type of integers in the Maybe monad.

Consequently, StringTree, which is a type, can't be a monad. It's just not the same kind of thing. You can try to imagine it as the type of strings in a monad, but your functions stringTreeReturn, etc, don't match the types of their monadic correspondents. Look at the type of >>= in the Maybe monad:

Maybe a -> (a -> Maybe b) -> Maybe b

The second argument is a function from some a to any type in the Maybe monad (Maybe b). stringTreeBind has the type:

String -> (String -> StringTree) -> StringTree

The second argument can only be a function from String to the monadic version of String, rather than to the monadic version of any type.

Consequently, you can't do everything you can do to values in an arbitrary monadic type to StringTree values, which is why it can't be made an instance. Even if you could somehow get it treated as a monad, things would start going wrong when generic monadic code expects to be able to use generic monadic operations in ways that don't make sense for StringTree.

Ultimately, if you're thinking of it as "like" a monad because it's String in a container that can behave similarly to monadic containers, the easiest thing to do is simply make it a generic container of any type (Tree a). If you need have auxiliary functionality that depends specifically on it being a tree of strings, then you can write that code as operating only on Tree String values, and it will happily co-exist along with code that works generically on Tree a.

Answer 3

No, that wouldn't be a monad. Think about it, can you write a monad m so only m String is ever possible?