Satisfying monad laws without a type constructor
-
27-06-2021 - |
質問
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?
解決
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.
他のヒント
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
.
No, that wouldn't be a monad. Think about it, can you write a monad m
so only m String
is ever possible?