- Haskell-Cafe - Haskell.org

Re: Monadic Call/CC?
by Marcin 'Qrczak' Kowalczyk 23 Feb '02

23 Feb '02

Thu, 21 Feb 2002 19:36:13 -0800, Ashley Yakeley <ashley(a)semantic.org> pisze: > data ContMonad p a = MkContMonad ((a -> p) -> p); [...] It's in GHC in module MonadCont, together with a monad transformer providing continuations and some instances. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ QRCZAK

1 0

Re: Monadic Call/CC?
by Ashley Yakeley 23 Feb '02

23 Feb '02

At 2002-02-22 01:36, Richard Uhtenwoldt wrote: >So, congratulations, you've written call/cc in Haskell. I think. Yes. test2 :: CPS (IO ()) (); test2 = do { liftM (putStr "aa\n"); ref <- liftM (newIORef Nothing); liftM (putStr "bb\n"); flag <- peirceM (\c -> do { liftM (putStr "cc\n"); liftM (writeIORef ref (Just c)); liftM (putStr "dd\n"); c True; liftM (putStr "ee\n"); return False; }); liftM (putStr "ff\n"); if (flag) then do { liftM (putStr "gg\n"); Just c' <- liftM (readIORef ref); liftM (putStr "hh\n"); c' False; liftM (putStr "ii\n"); } else do { liftM (putStr "jj\n"); } }; ContMonad> doMonadCPS test2 aa bb cc dd ff gg hh ff jj ...which shows that the continuation passed in by peirceM works both inside and outside the call. Changing "c' False" to "c' True" gave this endless iteration: ContMonad> doMonadCPS test2 aa bb cc dd ff gg hh ff gg hh ff gg hh ... I assume by the magic of Haskell's tail recursion, this won't eat up space. -- Ashley Yakeley, Seattle WA

1 0

Haskell problem
by Mark Wotton 22 Feb '02

22 Feb '02

Hi, I'm trying out some combinatorial parsers, and I ran into a slightly inelegant construction. To parse a sequence of things, we have a function like pThen3 :: (a->b->c->d) -> Parser a -> Parser b -> Parser c -> Parser d pThen3 combine p1 p2 p3 toks = [(combine v1 v2 v3, toks3) | (v1, toks1) <- p1 toks, (v2, toks2) <- p2 toks1, (v3, toks3) <- p3 toks2] The problem with this is that this structure has to be duplicated for pThen2, pThen4, and so on. These other forms are very similar to pThen3, but there seems to be no way to capture this in Haskell's type system, as the combine function has a different signature for each pThenX. (This is actually the first time the Haskell type system has got in my way rather than helping.) Is there a way around this problem? mrak

5 5

Graphs
by Wojciech Fraczak 22 Feb '02

22 Feb '02

Hi everybody, I would like to ask you, if you do not know any graph library for haskell. I would like to use haskell for prototyping some of algorithms on graphs and finite state automata/transducers. In fact what I'm looking for is a good (efficient and easy readable) data type definition for labeled graphs. Thanks, Wojtek

3 2

Re: Monadic Call/CC?
by Ashley Yakeley 22 Feb '02

22 Feb '02

At 2002-02-22 01:36, Richard Uhtenwoldt wrote: >Yeah, it's called continuation-passing style (CPS). Good. I have a small collection of wheels I've reinvented in my ignorance. >So, congratulations, you've written call/cc in Haskell. I think. >So, what I said this afternoon, namely, that call/cc is >"not something an implementation is likely >to be able to support unintentionally", I now have to retract. >I think. Well, I have to create my own monad and do call/cc in that. Doing call/cc in IO is another matter entirely. >I guess the call/cc you wrote last night in terms of catch and a ref >didn't work too well; huh? I havent't tested it. But I agree that it certainly won't allow continuations to survive after peirceM has returned, so can't be considered proper call/cc. -- Ashley Yakeley, Seattle WA

1 0

Re: Monadic Call/CC?
by Ashley Yakeley 22 Feb '02

22 Feb '02

>Given this: > > class (Monad m) => PeirceMonad m where > { > peirceM :: ((a -> m b) -> m a) -> m a; > }; > >...which Monads can be made PeirceMonads? Here's one: data ContMonad p a = MkContMonad ((a -> p) -> p); unContMonad (MkContMonad app) = app; instance Monad (ContMonad p) where { return a = MkContMonad (\cont -> cont a); (MkContMonad ma) >>= bf = MkContMonad (\cont -> ma (\a -> unContMonad (bf a) cont)); }; instance PeirceMonad m where { peirceM foo = MkContMonad (\cont -> unContMonad (foo (\a -> MkContMonad (\_ -> (cont a)))) cont); }; doContMonad :: ContMonad p p -> p; doContMonad cm = unContMonad cm id; test1 = doContMonad (peirceM (\continuation -> do { continuation 1; continuation 2; continuation 3; })); -- returns 1 Now here's the interesting thing. The usual way to represent "real-world" functions (i.e. with side-effects, or changing the world) from a to b is to define a special _type constructor_, 'IO', and define the function as 'a -> IO b'. But an alternative, would have been to define a special _type_, Action, and define the function as 'a -> (b -> Action) -> Action'. And then your 'main' function has type 'Action'. Nor do we have to declare special >>= and return functions as we do for IO. Here's how it's equivalent: type Action = IO (); type ActionMonad = ContMonad Action; doActionMonad :: ActionMonad () -> Action; doActionMonad cm = unContMonad cm return; liftIO :: IO a -> ActionMonad a; liftIO ioa = MkContMonad (\cont -> ioa >>= cont); ...and note that we get Peirce continuations for free: peirce foo cont = foo (\a _ -> (cont a)) cont; -- constructors removed -- Ashley Yakeley, Seattle WA

2 1

Re: Monadic Call/CC?
by Ashley Yakeley 22 Feb '02

22 Feb '02

At 2002-02-21 19:36, I wrote: > And then your 'main' function has type 'Action'. Sorry, And then your 'main' function has type 'Action -> Action'. -- Ashley Yakeley, Seattle WA

1 0

Re: Monadic Call/CC?
by Ashley Yakeley 21 Feb '02

21 Feb '02

At 2002-02-20 22:15, I wrote (on the Haskell list): >Haskell? Given this: > > class (Monad m) => PeirceMonad m where > { > peirceM :: ((a -> m b) -> m a) -> m a; > }; > >...which Monads can be made PeirceMonads? This is untested, but... instance PeirceMonad IO where { peirceM foo = do { ref <- newIORef Nothing; catch (foo (\a -> do { writeIORef ref (Just a); ioError (userError "break"); })) (\ex -> do { ma <- readIORef ref; case ma of { Just a -> return a; _ -> ioError ex; }; }) } }; So you can do it if you have refs and throw/catch for your monad. I think. -- Ashley Yakeley, Seattle WA

2 1

RE: Survival of generic-classes in ghc
by Jan-Willem Maessen 21 Feb '02

21 Feb '02

* Language philosophers who are skimming this discussion will want to take a look at #### below. Simon PJ writes: > One thing that is slowing me down is a design uncertainty: how to > deal cleanly with constructors. To write read, show, etc, one needs > access to the constructor name, fixity etc. We dance around that a > little in the paper. I'm thinking of this design: ... > -- Con is part of the Generics library, like 1, :*:, :+: > newtype Con c a = Con a > > class ConCls c where > name :: c -> String > arity :: c -> Arity > ..etc.. > > data NilT -- Phantom types > data ConsT -- one per constructor > > instance ConCls NilT where > name _ = "Nil" > ...etc... > > instance ConCls ConsT wher > name _ = "Cons" > ...etc... But you're going to have to keep those ConCls dictionaries somewhere, which means either: 1) The type Con should existentially quantify over c: < data Con a = forall c. (ConCls c) => Con a [I haven't checked that this is even legal anywhere, but you get the idea] 2) Any function which needs the type "c" must carry around a dictionary for *each* constructor in the type. I'm not quite sure how to work the typing of the code generic functions in this regime, though I'm sure it could somehow be managed. As long as we're reifying everything in sight, why not simplify the design problem and reify the constructor dictionaries? >From my own strawman experiments (this is old code): > data Constructor t = Constructor CI !t > > data CI = CI Bool String Int [String] [Bool] deriving (Eq) > -- Op-ness, constructor, fixity, field names, strictnesses of fields We could do something similar for fields, of course. There need only be one copy of this info for each data constructor (and field); it's easy for the compiler to share these. The type CI is effectively a representation of the dictionary for ConCls. The "Constructor" type the works just like the existentially quantified example (1). The drawback? We need to store the constructor info CI in every reified constructor. My suspicion is this will not matter much in practice. Compiling generics should be done with one of two sets of assumptions: * Generics are a mechanism of convenience. If you want your code to go fast, you should write the code longhand (possibly using an overlapping instance for an otherwise generic function/class). In this case, the extra overhead of the constructor info is likely to be a drop in the bucket. * Generics should be specialized at the types at which they are used. This might be accomplished by careful inlining of reification functions into the bodies of generic methods (or vice versa). In this case "Constructor" should vanish. ####################### On a broader philosophical note: I'm disturbed by the idea of adding explicit type application and the like to Haskell. Haskell language extensions are rapidly becoming a riotous array of confusing syntax and twisty semantic corners. From an experimenter's standpoint, this isn't so bad. However, many of these extensions are incredibly useful, and there's a lot of code relying upon them. This creates pressure (from both users and implementors) to immortalize the existing, grubby implementations. The result? An incomprehensible, byzantine language. For example, we now have multiparameter type classes (useful) with functional dependencies (addressing a vital problem with multiparameter constraint solving). Now Simon is wants explicit type application, kind annotations, and the like. There are some things Haskell does very well---algebraic types and pattern matching are cleaner and more pleasant to use then in ML, and the class system has proven to be Haskell's most brilliant distinguishing feature. I'd like to see solutions to some of the current problems that build on these strengths. I'm not sure if it's possible to get a type language based on functions and pattern matching in the face of type inference. Cayenne makes it clear that one can write type-level code very naturally when the type language and the value language work the same way. Similarly, I observe that: * Views = coercion methods + implicitly-inserted coercions + deforestation * Generics = reification methods + functions become methods + implicitly-inserted reification + deforestation The two lists are pretty similar, and it might be worth trying to unify the efforts in some fashion---possibly by breaking down the functionality into simple pieces. Here are some possibilities: * Come up with a coherent story on implicitly-inserted coercions. Ideally fromInteger and fromRational would just be specific cases of this coherent story. (The current story is nice and coherent: if it's a numeric constant, there's a coercion, otherwise there isn't.) * Allow patterns to match at multiple types, if those types match particular constraints (such as coercability). These two together might well be enough to give you views. * Give the deriving mechanism a language-level reading. Allow "deriving"-like clauses outside the context of type declarations. * Give some way to declare "closure" of a class. This should be done with an eye on abstraction barriers. Perhaps "closed" classes may still be derived (by newtypes, or using the mechanism for generics). * Make generic functions look like closed classes; possibly this means allowing the programmer to write instances as part of the class declaration. * Perhaps Haskell needs a universal class. This class would provide the reification methods for all [boxed?] data types, and might be a place for the implementation to hide (e.g.) type-based GC methods or specialized versions of seq. I'm hoping something along these lines is enough for single-parameter generics at least. Much of this work already exists in fragmentary form. However, in many cases it's part of attempts at larger mechanisms. For example, "views" proposals have suggested using distinguished "view types", and adding coercions when patterns mention the constructor of a view type. "Closed" classes were mentioned in the paper on instance resolution at PoPL last month. And of course there's lots of good work on generics, the big problem being that the efforts have become scattershot and still doesn't seem to fit the rest of the language nicely. It's time to reduce the useful mechanisms to their essentials. -Jan-Willem Maessen Eager Haskell project

1 0

RE: Survival of generic-classes in ghc
by Simon Peyton-Jones 21 Feb '02

21 Feb '02

| and I know from testing earlier versions that the | generic-classes support was pretty buggy. Is there any hope | of a revival? Does it already work in CVS? I suspect it will | rot away if nobody works on it. | | Any comments from the implementors - does the idea "fit well" | with ghc? Is it a lot of work to make it more stable? No, it should not be a lot of work to revive, and I will do it. Keep bugging me until I do. One thing that is slowing me down is a design uncertainty: how to deal cleanly with constructors. To write read, show, etc, one needs access to the constructor name, fixity etc. We dance around that a little in the paper. I'm thinking of this design: -- An example data type data List a = Nil | Cons a (List a) -- The "ring" type derived from it -- Note the Con wrapped around the constructors data ListO a = Con NilT 1 :+: Con ConsT (a :*: List a) -- Con is part of the Generics library, like 1, :*:, :+: newtype Con c a = Con a class ConCls c where name :: c -> String arity :: c -> Arity ..etc.. data NilT -- Phantom types data ConsT -- one per constructor instance ConCls NilT where name _ = "Nil" ...etc... instance ConCls ConsT wher name _ = "Cons" ...etc... Now you can write class Show a where show :: a -> String show {| Con c t |} (Con x) = (name (undefined::c)) ++ show x ...etc.. Note the "undefined::c"; it is really just a type argument to "name", so that we get the string for the right constructor. It's a bit clunky, though. Another possiblity would be to make the ConCls class look like this class ConCls c where name :: String arity :: Int ...etc... Now we'd have to give an explicit type argument at the call site: show {| Constr c t |} (Con x) = (name {| c |}) ++ show x I quite like the thought of being able to supply explicit type arguments.... but I don't konw how to speak about the order of type parameters. What order does map takes its two type parameters in? Another question is whether we need an indication that we have reached a field of the constructor. Should we have: data ListO a = Con NilT (Field 1) :+: Con ConsT (Field a :*: (Field List a)) newtype Field a = Field a Without this, it's hard to write a generic function to count the number of fields of the data type. But in general, one might want to know when making the transition from "this" type to the argument types of the constructors. I think that the main reason I'm not making much progress is that I don't know what design choices to make. I'd be glad to discuss it with interested parties. Simon

2 1