Dear Haskellers,
Yesterday I stumbled upon a problem type checking a program involving
multi-parameter type classes. GHC rejected the program; still, I was
not immediately convinced it contained a type error. Having given it
some more thoughts, I start to suspect that the type checker is in err
and that the program is well-typed after all. But, well, I might be
overlooking something obvious...
I have reduced my code to a small but hopelessly contrived example
program exposing the problem. Please hang on.
Because we employ multi-parameter type classes, we need the Glasgow
extensions:
{-# OPTIONS -fglasgow-exts #-}
Let's start easy and define the identity monad:
newtype Identity a = Identity {runIdentity :: a}
instance Monad Identity where
return = Identity
Identity a >>= f = f a
Then, let's introduce the foundations for the (contrived) example:
class (Monad m) => IsItem m i where
processItem :: i -> m ()
class (Monad m) => IsProcessor p m | m -> p where
process :: (IsItem m i) => i -> m ()
-- ...some more methods, possibly involving p...
So, an item is something that can be processed within the context of a
certain monad, and a processor is something that can process an item of
an appropriate type. Note the functional dependency from m to p: a
processor type m uniquely determines the type of the processing context
p.
Before we move on, consider this canonical item type, which is just a
one-field record representing an implementation of the IsItem class:
newtype Item m = Item {processItemImpl :: m ()}
The corresponding instance declaration is obvious:
instance (Monad m) => IsItem m (Item m) where
processItem = processItemImpl
Furthermore values of every type that is an instance of IsItem can be
converted to corresponding Item values:
toItem :: (IsItem m i) => i -> Item m
toItem = Item . processItem
Please stick with me, for we are now going to implement a monad
transformer for processors (which, for this example, is really just the
identity monad transformer):
newtype ProcessorT p m a = ProcessorT {runProcessorT :: m a}
instance (Monad m) => Monad (ProcessorT p m) where
return = ProcessorT . return
ProcessorT m >>= f = ProcessorT (m >>= runProcessorT . f)
instance (Monad m) => IsProcessor p (ProcessorT p m) where
process = processItem
Then, finally, we use this transformer to derive a processor monad:
newtype Processor p a = Processor {unwrap :: ProcessorT p Identity a}
runProcessor :: Processor p a -> a
runProcessor = runIdentity . runProcessorT . unwrap
So, we just make sure that Processor is a monad:
instance Monad (Processor p) where
return = Processor . return
Processor m >>= f = Processor (m >>= unwrap . f)
Now all what is left to do is declare Processor an instance of
IsProcessor. To this end, we need to be able to cast items for
Processor p to items for ProcessorT p Identity (for all p). The
following function takes care of that:
castItem :: (IsItem (Processor p) i) => i -> Item (ProcessorT p
Identity)
castItem = Item . unwrap . processItem
Note that up 'til now everything is fine: GHC is happy, I am happy. But
then,
when all the hard work is done, and we just only have to connect things
properly, it just breaks:
instance IsProcessor p (Processor p) where
process = Processor . process . castItem
After adding this last instance declaration, GHC happily reports:
Processor.hs:56:24:
Could not deduce (IsItem (ProcessorT p Identity)
(Item (ProcessorT p1 Identity)))
from the context (IsProcessor p (Processor p),
Monad (Processor p),
IsItem (Processor p) i)
arising from use of `process' at Processor.hs:56:24-30
Probable fix:
add (IsItem (ProcessorT p Identity) (Item (ProcessorT p1
Identity)))
to the class or instance method `process'
or add an instance declaration for
(IsItem (ProcessorT p Identity)
(Item (ProcessorT p1 Identity)))
In the first argument of `(.)', namely `process'
In the second argument of `(.)', namely `process . castItem'
In the definition of `process': process = Processor . (process .
castItem)
Processor.hs:56:34:
Could not deduce (IsItem (Processor p1) i)
from the context (IsProcessor p (Processor p),
Monad (Processor p),
IsItem (Processor p) i)
arising from use of `castItem' at Processor.hs:56:34-41
Probable fix:
add (IsItem (Processor p1) i) to the class or instance method
`process'
or add an instance declaration for (IsItem (Processor p1) i)
In the second argument of `(.)', namely `castItem'
In the second argument of `(.)', namely `process . castItem'
In the definition of `process': process = Processor . (process .
castItem)
It seems to me that the type checker fails to unify p and p1 where it
really should. But once again: I may be wrong here. So, could you
either explain to me what I'm missing here and why this program is
indeed ill-typed, or confirm that it's really just GHC that should be
accepting this program.
I have attached a file Processor.hs containing the example program.
Please note that I've only tested this with GHC 6.4. I did not try it
(yet) with the version in HEAD. Neither did I investigate how Hugs acts
on this code.
I'm aware that there are some workarounds to get past this problem. The
most obvious approach to circumventing this issue is to alter the
signature of process so that it takes an explicit Item value and put
the need for casting (using toItem) to the caller side. But that's just
not the point, of course.
I'm sorry for this far too long post, but this issue is quite essential
for the code I'm currently working. Reactions, therefore, are much
appreciated.
TIA,
Stefan
http://www.cs.uu.nl/~stefan/
Dear List Subscribers,
I am pleased to announce the first stable release of HSFFIG, yet
another tool for autogeneration of FFI bindings from C include files.
The project is now hosted at Sourceforge: http://hsffig.sourceforge.net
Downloads page: http://www.sourceforge.net/projects/hsffig
Darcs repo: darcs get http://hsffig.sourceforge.net/repos/hsffig-1.0
Tutorial: http://www.haskell.org/hawiki/HsffigTutorial
The wiki page "HsffigExamples" has been separated from the Tutorial.
If anybody has an interesting example of using HSFFIG please update
the page with code samples.
Brief summary of changes:
- The distribution is now cabalized. Please read the INSTALL file.
- The multiparameter class and combinators to access members of
structures/unions are moved to separate library. It is necessary to
specify -package HSFFIG when compiling applications.
Thanks to everybody who participated in discussions related to HSFFIG
on this list, and privately. This helped me with implelentation of
some features and gave some ideas for future improvement.
Debian, RPM, and other packagers: if you create a HSFFIG package
please let me know the package URL so I can update the Freshmeat
project information page, and the project homepage.
For any problems related to this project feel free to contact me.
--
Dimitry Golubovsky
IMPORTANT NOTE: Registration is now available at:
http://www.cs.ioc.ee/tfp-icfp-gpce05/
CUFP 2005
THE SECOND ACM SIGPLAN
COMMERCIAL USERS OF FUNCTIONAL PROGRAMMING WORKSHOP
http://www.galois.com/cufp/
Talinn, Estonia
September 24th 2005
Co-located with ICFP
http://www.brics.dk/~danvy/icfp05/
----------------------------------------------------------------------
Important dates
Early registration deadline July 29, 2005
Late registration deadline September 2, 2005
Workshop September 24, 2005
Registration is available at:
http://www.cs.ioc.ee/tfp-icfp-gpce05
----------------------------------------------------------------------
The goal of CUFP is to build a community for users of functional
programming languages and technology, be they using functional
languages in their professional lives, in an open source project
(other than implementation of functional languages), as a hobby,
or any combination
thereof.
In short: anyone who uses functional programming as a /means/, but not
an /end/.
----------------------------------------------------------------------
Schedule
The meeting will last a full day, with a mix of invited presentations
and discussion sessions.
This year, we have the following confirmed speakers:
* Atrijus Tang; talking about PUGS, a Perl6 implementation, written
in Haskell;
* Fabrice Le Fessant; talking about MLDonkey, a popular
multi-platform, multi-network P2P client written in OCaml.
* Michael Sperber; talking about uses of Scheme in the banking
industry.
* David Roundy; talking about darcs, a popular and flexible
revision control system well-suited to highly distributed
development, written in Haskell.
* Jim Grundy; talking his experiences with functional programming
at Intel's Strategic CAD Labs.
* Robert Boone; talking about his experiences at FreeScale.
* Jonathan Soebel; talking about lessons the FP community can learn
from the OMG's Model Driven Architecture (MDA) and its related
marketing efforts.
We will also be having two working sessions, where lively debate and
brainstorming will be the order of the day:
* FP, Education, and Industry: industry folks complain that there
aren't enough FP folks being produced by schools, and educators
complain that students don't see any point in studying FP if there are
no jobs to be had. How can we break this stalemate? Simon Thompson of
Functional and Declarative Programming in Education (FDPE05) will be
joining us, and we'll be debriefing at FDPE05.
* Stimulating a CUFP Community: we'd like the buzz and excitement
surrounding CUFP to persist beyond the workshops. What would such a
community look like? How do we make it happen? The session will kick
off with two separate but complimentary starting points: a proposed
"Users of FP" community web site and a proposed "Haskell Consortium"
web site.
There will be no published proceedings, as the meeting is intended to
be more a discussion forum than a technical interchange. A full report
of last year's workshop appeared in the Functional Programming column
of the December 2004 issue of SIGPLAN Notices, and we plan to do the
same this year.
--
Andy Moran Phone: 503.626.6616, x113
Galois Connections Inc. Fax: 503.350.0833
12725 SW Millikan Way, Suite #290 http://www.galois.com
Beaverton, OR 97005 moran(a)galois.com
