Hi, I'm fairly new to Haskell and recently came across some programming tricks for reducing monadic overhead, and am wondering what higher-level concepts they map to. It would be great to get some pointers to related work. Background: I'm a graduate student whose research interests include methods for implementing domain specific languages. Recently, I have been trying to get more familiar with Haskell and implementing DSLs in it. I'm coming from having a fair bit of experience in Python so I know the basics of functional programming. However, I'm much less familiar with Haskell. In particular I have little to no internal map from existing DSL implementation techniques to the Haskell extensions that would no doubt make DSL implementations easier (and when they are *not* needed). I also don't have a complete picture of the functional programming research that would inform these techniques. I would greatly appreciate it if I could get pointers to the appropriate references so I can really get going on this. Specifically: There are some DSLs that can be largely expressed as monads, that inherently play nicely with expressions on non-monadic values. We'd like to use the functions that already work on the non-monadic values for monadic values without calls to liftM all over the place. The probability monad is a good example. import Control.Monad import Data.List newtype Prob a = Prob { getDist :: [(a, Float)] } deriving (Eq, Show) multiply :: Prob (Prob a) -> Prob a multiply (Prob xs) = Prob $ concat $ map multAll xs where multAll (Prob innerxs, p) = map (\(x, r) -> (x, p * r)) innerxs instance Functor Prob where fmap f (Prob xs) = Prob $ map (\(x, p) -> (f x, p)) xs instance Monad Prob where return x = Prob [(x, 1.0)] x >>= f = multiply (fmap f x) In this monad, >>= hides the multiplying-out of conditional probabilities that happen during the composition of a random variable with a conditional distribution. coin x = Prob [(1, x), (0, 1 - x)] test = do x <- (coin 0.5) y <- (coin 0.5) return $ x + y *Main> test Prob {getDist = [(2,0.25),(1,0.25),(1,0.25),(0,0.25)]} We can use a 'sum out' function to get more useful results: sumOut :: (Ord a) => Prob a -> Prob a sumOut (Prob xs) = Prob $ map (\kvs -> foldr1 sumTwoPoints kvs) eqValues where eqValues = groupBy (\x y -> (fst x == fst y)) $ sortBy compare xs sumTwoPoints (v1, p1) (v2, p2) = (v1, p1 + p2) *Main> sumOut test Prob {getDist = [(0,0.25),(1,0.5),(2,0.25)]} I'm interested in shortening the description of 'test', as it is really just a 'formal addition' of random variables. One can use liftM for that: test = liftM2 (+) (coin 0.5) (coin 0.5) It seems what I'm leading into here is making functions on ordinary values polymorphic over their monadic versions; I think this is the desire for 'autolifting' or 'monadification' that has been mentioned in works such as HaRE http://www.haskell.org/pipermail/haskell/2005-March/015557.html One alternate way of doing this, however, is instancing the typeclasses of the ordinary values with their monadic versions: instance (Num a) => Num (Prob a) where (+) = liftM2 (+) (*) = liftM2 (*) abs = liftM abs signum = liftM signum fromInteger = return . fromInteger instance (Fractional a) => Fractional (Prob a) where fromRational = return . fromRational (/) = liftM2 (/) Note that already, even though each function in the typeclass had to be manually lifted, this eliminates more overhead compared to lifting every function used, because any function with a general enough type bound can work with both monadic and non-monadic values, not just the ones in the typeclass: *Main> sumOut $ (coin 0.5) + (coin 0.5) + (coin 0.5) Prob {getDist = [(0,0.125),(1,0.375),(2,0.375),(3,0.125)]} *Main> let foo x y z = (x + y) * z *Main> sumOut $ foo (coin 0.5) (coin 0.5) (coin 0.5) Prob {getDist = [(0,0.625),(1,0.25),(2,0.125)]} Because of the implementation of fromInteger as return . fromInteger, we also 'luck out' and have the ability to mix ordinary and non-monadic values in the same expression: *Main> 1 + coin 0.5 / 2 Prob {getDist = [(1.5,0.5),(1.0,0.5)]} My question is, what are the higher-level concepts at play here? The motivation is that it should be possible to automatically do this typeclass instancing, letting us get the benefits of concise monadic expressions without manually instancing the typeclasses. Indeed, I didn't have this idea in Haskell; I'm coming from Python where one can realize the automatic instances: if we take the view that classes in Python are combined datatypes and instanced typeclasses, we can use the meta-object protocol to look inside one class's representation and output another class with liftM-ed (or return . -ed) methods and a custom constructor. I realize Template Haskell gives you the ability to reify instance/class declarations, but perhaps there's a less heavyweight way (or there should be). I think a good question as a starting point is whether it's possible to do this 'monadic instance transformation' for any typeclass, and whether or not we were lucky to have been able to instance Num so easily (as Num, Fractional can just be seen as algebras over some base type plus a coercion function, making them unusually easy to lift if most typeclasses actually don't fit this description). In general, what this seems to be is a transformation on functions that also depends explicitly on type signatures. For example in Num: class (Eq a, Show a) => Num a where (+), (-), (*) :: a -> a -> a negate, abs, signum :: a -> a fromInteger :: Integer -> a instance (Num a) => Num (Prob a) where (+) = liftM2 (+) -- Prob a -> Prob a -> Prob a (*) = liftM2 (*) -- Prob a -> Prob a -> Prob a abs = liftM abs -- Prob a -> Prob a signum = liftM signum -- Prob a -> Prob a fromInteger = return . fromInteger -- Integer -> Prob a Note that if we consider this in a 'monadification' context, where we are making some choice for each lifted function, treating it as entering, exiting, or computing in the monad, instancing the typeclass leads to very few choices for each: the monadic versions of +, -, * must be obtained with "liftM2",the monadic versions of negate, abs, signum must be obtained with "liftM", and the monadic version of fromInteger must be obtained with "return . " I think this is what we're doing in general: if we had a typeclass C with a type variable a, with some set of type signatures in which 'a' appears bound, we can do "instance C (M a)" for some monad M if there is some way to realize the resulting set of type signatures where every bound occurence of 'a' is replaced with 'M a'. The following script illustrates precisely what I mean by this: data Typ = Gr String -- Irreducible grounded type, like Int or Bool | Con String Typ -- Type constructor applied to a type of kind *, i.e., IO String, Maybe (Prob Int) | Arr Typ Typ -- Function T1 -> T2 | Tup (Typ, Typ) -- Tuple (T1, T2) deriving Eq instance Show Typ where show (Gr a) = a show (Con m a) = "(" ++ m ++ " " ++ show a ++ ")" show (Arr a b) = "(" ++ show a ++ " -> " ++ show b ++ ")" show (Tup (x, y)) = "(" ++ show x ++ ", " ++ show y ++ ")" --let a = b in expr for our type signature calculus typlet :: Typ -> Typ -> Typ -> Typ typlet a b expr = case a == expr of False -> typletdown a b expr True -> b typletdown a b (Tup (x, y)) = Tup (typlet a b x, typlet a b y) typletdown a b (Arr x y) = Arr (typlet a b x) (typlet a b y) typletdown a b (Con str c) = Con str (typlet a b c) typletdown a b (Gr s) = Gr s monadify a b expr = typlet a (Con b a) expr -- class declaration : the free type variable, with a list of signatures type ClassDecl = (Typ, [Typ]) -- monadify class signatures monadic_sigs :: ClassDecl -> String -> ClassDecl monadic_sigs (btyp, sigs) it = (Con it btyp, map (\sig -> monadify btyp it sig) sigs) -- Num mkNum = (Gr "a", [ (Gr "a") `Arr` ((Gr "a") `Arr` (Gr "a")), -- (+), (-), (*) (Gr "a") `Arr` (Gr "a"), -- abs, signum, negate (Gr "Integer") `Arr` (Gr "a")]) -- fromInteger main = do let testexpr =(Gr "a") `Arr` ((Gr "a") `Arr` (Gr "a")) print "Sample type signature:" print testexpr print "Monadified:" print $ monadify (Gr "a") "Prob" testexpr print $ "Num typeclass signatures:" print $ mkNum print "Signatures of the functions needed for instance (Num a) => Num (Prob a):" print $ monadic_sigs mkNum "Prob" I suppose I'm basically suggesting that the 'next step' is to somehow do this calculation of types on real type values, and use an inductive programming tool like Djinn to realize the type signatures. I think the general programming technique this is getting at is an orthogonal version of LISP style where one goes back and forth between types and functions, rather than data and code. I would also appreciate any pointers to works in that area. Thanks for any leads, Lingfeng Yang lyang at cs dot stanford dot edu