[haskell-cafe] Monad and kinds
Daniel Fischer
daniel.is.fischer at web.de
Tue Sep 2 10:35:57 EDT 2008
Am Dienstag, 2. September 2008 15:34 schrieb Ramin:
> Hello, I'm new here, but in the short time I have known Haskell, I can
> already say it's my favorite computer language.
>
> Except for monads, and no matter how many tutorials I read, I find the
> only kind of monad I can write is the monad that I copied and pasted
> from the tutorial, i.e. I still don't get it even though I thought I
> understood the tutorial, and I'm stuck using monads others have already
> written.
Considering some pretty brilliant people have a few years advantage over you,
don't expect to find a situation where you need a monad not yet written for a
while :)
>
> My project is this: I am writing a mini-database of sorts. I thought I
> would make a query a monad, so I could chain multiple queries together
> using the "do" notation, and run more complex queries on the list in one
> shot. The query itself is stateful because it contains information that
> changes as the database is traversed. The query may also make updates to
> the records. I got the program to work perfectly using purely functional
> techniques, but complex queries resulted in that stair-step looking
> code. So I thought this would be the perfect opportunity to try my hand
> at monads.
>
> The query monad I wrote looks something like this (much simplified):
> data Query state rec = Query !(state, rec)
>
> Where "state" is the type of state, so a query can contain any
> information relevant to the search and can be updated as the search
> progresses.
> Then, "rec" is the type of records in the database, which isn't
> determined inside the database module, so I can't just declare "rec" to
> be of any type I choose.
>
> But I just cannot write the instance declaration for my Query data type
> no matter what I try. If I write:
> instance Monad Query where
> return (initState, someRecord) = Query (initState, someRecord)
> {- code for (>>=) -}
> GHC gives an error, "Expected kind `* -> *', but `Scanlist_ctrl' has
> kind `* -> * -> *' ". If I try this:
> instance Monad (Query state) where
> return (initState, someRecord) = Query (initState, someRecord)
> {- code for (>>=) -}
> GHC give an error, "Occurs check: cannot construct the infinite type: a
> = (s, a) when trying to generalise the type inferred for `return' ".
The type of return is (Monad m => a -> m a). If m = (Query state), the type of
return becomes (rec -> Query state rec) and (return a) must be
Query (something of type state, a).
Now, if you try
return (initState, someRecord) = Query (initState, someRecord),
the (initState, someRecord) on the left has type a, and the someRecord on the
right has the same type. From the left hand side follows a = (state, rec),
hence someRecord has type rec. But from the right hand side, someRecord must
have type a = (state, rec), so we find rec = (state, rec). That of course is
impossible.
>
> I get the sense I am trying to shove a square peg into a round hole. I
> was thinking of trying some other things, like implementing the monad in
> a higher-level module where I knew the type of the records I would be
> using, but I don't like being told where to implement things. I also
> thought of trying to re-write my query algorithm to somehow use
> "Control.Monad.State.Strict" instead of my own query type, but then I
> wouldn't get to write my own monad!
But this looks very much like an application well suited for the State monad
(or a StateT). So why not use that? Or you could write your own specialised
version without looking at the existing code, so you could at least
familiarise yourself a little more with monads.
>
> Though the information given in this e-mail is limited, is there anyone
> who can clearly see there is something about monads that I just don't
> get and tell me what it is?
>
> Anyone who took the time to read this, I am very appreciative.
> Ramin Honary
A monad is a type constructor of kind (* -> *), that is, it takes one type as
argument and returns some other type. Your Query takes two types as argument
and makes one new type from that, so Query has kind (* -> * -> *) and cannot
possibly be a monad. What could be a monad is (Query a) which has kind (* ->
*). However, the only halfway meaningful return you can define then is
return someRecord = Query (undefined, someRecord),
which doesn't look particularly useful. And (>>=) then can't make use of the
state either, it would have to be one of
Query (s,r) >>= f = f r
or
Query (s,r) >>= f = let Query (_,r1) = f r in Query (s,r1)
or something completely meaningless.
HTH,
Daniel
More information about the Haskell-Cafe
mailing list