- Haskell-Cafe - Haskell.org

if -> is a type constructor
by Cagdas Ozgenc 24 Feb '02

24 Feb '02

Greetings folks. If (->) is a type constructor, what does its definition look like, what data constructors does it have? How does it differ from other type constructors, or maybe it doesn't? Could someone give an explanation... Thanks for taking time.

2 1

Re: Graphs
by Jan-Willem Maessen 23 Feb '02

23 Feb '02

David Feuer <dfeuer(a)cs.brown.edu> writes: > I seem to remember an article about functional graph algorithms using > extra-lazy arrays. Anyone know if these arrays have appeared in any > mainstream implementation? I assume you're referring to this paper by Thomas Johnsson: @Article{lazyArray, author = {Johnsson, Thomas}, title = {Efficient Graph Algorithms Using Lazy Monolithic Arrays}, journal = JFP, year = 1998, volume = 8, number = 4, pages = {323--333}, month = {July} } He uses similar techniques to do whole-program flow analysis of Haskell programs, a clever bit of coding described in the following paper: @inproceedings{grinHeap, AUTHOR = "Johnsson, Thomas", TITLE = "Analysing Heap Contents in a Graph Reduction Intermediate Language.", booktitle = Proc # "Glasgow Functional Programming Workshop", address = "Ullapool 1990", MONTH = "August", YEAR = 1991 } The LazyArray library is part of the standard hbc distribution. The Eager Haskell compiler depends on it (you can get very nice static hash tables this way, among other things). As a result, I've done a port of the library to GHC (and, I think, hugs). I should note that most of the hints required to pull off the implementation were found in the "State in Haskell" paper by Simon PJ and John Launchbury. The library is available (along with a few other useful snippets, like universal splittable supplies) here: http://www.csg.lcs.mit.edu/~earwig/haskell-lib/ -Jan-Willem Maessen

2 1

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

23 Feb '02

At 2002-02-23 07:55, Marcin 'Qrczak' Kowalczyk wrote: >It's in GHC in module MonadCont, together with a monad transformer >providing continuations and some instances. Could this sort of thing _please_ be added to <http://www.haskell.org/ghc/docs/latest/set/book-hslibs.html> or somewhere? Is this documented somewhere? -- Ashley Yakeley, Seattle WA

1 0

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 22 Feb '02

22 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 21 Feb '02

21 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