- Haskell-Cafe - Haskell.org

tree with labeled edges as a monad
by Andrew Pimlott 20 Jan '05

20 Jan '05

This is a "have you seen this monad?" post. I was trying to construct a search tree, and decided I wanted to do it in a monad (so I could apply StateT and keep state as I explored the space). I discovered that a tree with labeled leaves is a monad, but I wanted to label internal nodes, and such a tree (eg, Data.Tree.Tree) is not a monad (because it can only have one result type). Finally, I realized I could get a similar effect by labeling the edges and the leaves with different types: data Tree l a = Leaf a | Branch [(l, Tree l a)] instance Monad (Tree l) where return = Leaf Leaf a >>= f = f a Branch c >>= f = Branch [(l, t >>= f) | (l, t) <- c] You might use it as turn = do board <- getBoard move <- lift (Branch [(move, return move) | move <- findMoves board]) applyMove move turn I found this quite pleasing, though I hadn't run across trees as monads before. Has anyone else found this useful? Is it in a library somewhere? Andrew

3 2

RE: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 20 Jan '05

20 Jan '05

On 19 January 2005 16:49, Keean Schupke wrote: > But what about the continuing computation... we do not want > the fastest IO system, but we want the program to comlete the > fastest... So ideally we want 2 threads! > > One runs the Haskell code that is not waiting for IO. (IE other > Haskell threads)... The other runs a select loop as you suggest! > > This way the number of threads is fixed (2) and execution never > 'blocks' for IO. (Simon, what about this scheme?) This is what GHC does, if I understand you correctly. The thread running select() does so in its own OS thread, while another OS thread runs the Haskell code. As long as you use -threaded, that is. Oh, and before GHC 6.4 it was done a different way - the scheduler used to do the select() between running Haskell threads. Cheers, Simon

2 1

RE: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 20 Jan '05

20 Jan '05

On 19 January 2005 13:50, William Lee Irwin III wrote: > On 19 January 2005 09:45, Ben Rudiak-Gould wrote: >>> Okay, my ignorance of Posix is showing again. Is it currently the >>> case, then, that every GHC thread will stop running while a disk >>> read is in progress in any thread? Is this true on all platforms? > > On Wed, Jan 19, 2005 at 01:39:05PM -0000, Simon Marlow wrote: >> It's true on Unix-like systems, I believe. Even with -threaded. It >> might not be true on Win32. > > How does forkOS fit into this picture? It's described in the > documentation as allowing concurrent execution of system calls > and other activity by other threads. forkOS doesn't fix this. It forks another OS thread which can be used to make concurrent foreign calls, if they are not marked "unsafe". However, the standard I/O library, in -threaded mode, does read like this: - non-blocking, "unsafe", read() to see what's there - if read() would block, then hand off to another Haskell thread which does select() on all the outstanding IO requests. This scheme is just for efficiency. We could (and used to) just call "safe" read() for every read - that would give you the right concurrency with -threaded, but unfortunately you'd really notice the difference if you had 1000s of threads all doing IO, because each one would need its own OS thread. The current scheme is rather snappy (even snappier than non-threaded, as it happens). You can always do System.Posix.fileRead to get around it. Cheers, Simon

3 3

RE: [Haskell-cafe] GHC for .NET?
by Simon Peyton-Jones 19 Jan '05

19 Jan '05

| "The GHC compiler for .NET is currently under development at | Microsoft Research, Cambridge". | | Hmm. That location sounds familiar :-) Does anyone know if this is | actually going to happen? Or if there's any code anywhere, however | experimental, to try? It'd make a lot of sense to give GHC a .NET back end, and it's a question that comes up regularly. The reason that we haven't done it here, at GHC HQ, is because it's a more substantial undertaking than might at first appear (see below). Furthermore, it'd permanently add a complete new back-end platform for us to maintain. Given our rather limited development effort (= Simon and me), we have so far not bitten the bullet, and we have no immediate plans to do so. It'd be a good, well-defined project for someone else to tackle, and there is some good groundwork already done: * Sigbjorn Finne did a simple interop implementation that allows a Haskell program to be compiled to native code (as now) but to call .NET programs via a variant of the FFI. I don't think this work is in active use, and I'd be surprised if it worked out of the box, but it could probably be revived with modest effort * Andre Santos and his colleagues at UFPE in Brazil are working on a .NET back end, that generates CLR IL, though I don't know where they are up to. * GHC.Net would be extra attractive if there was a Visual Studio integration for GHC. Substantial progress on this has been made in 2004 by Simon Marlow, Krasimir Angelov, and Andre Santos and colleagues. There may be others that I don't know of. If anyone wants to join in this effort, do contact the above folk. And please keep us informed! Simon Here's a summary of why it's a non-trivial thing to do: - The first thing is to generate native CLR Intermediate Language (IL). That's not really hard. Requires thinking about representations for thunks and functions, and it may not be particularly efficient, but it can surely be done. An open question is about whether to generate verifiable IL or not. The trouble here is that Haskell's type system is more expressive than the CLR's in some ways, notably the use of higher-kinded type variables. So, to generate verifiable IL one is bound to need some run-time casts, and it's not clear how to minimise these. At first blush this is *all* you need do. But it isn't! - Next, you need to think about how to inter-operate with .NET libraries. You don't really want to write "foreign import..." for each and every import. You'd like GHC to read the CLR meta-data directly. But there are lots of tricky issues here; see the paper that Mark Shields and I wrote about "Object-oriented style overloading for Haskell". - Now you need to figure out how to implement GHC's primitive operations: the I/O monad arbitrary precision arithmetic concurrency exceptions finalisers stable pointers software transactional memory Not all of these are necessary, of course, but many are used in the libraries. The CLR supports many of them (e.g. concurrency) but with a very different cost model. - Last, you have to figure out what to do for the libraries. GHC has a pretty large library, and you either have to implement the primops on which the library is based (see previous point), or re-implement it. For example, GHC's implementation of I/O uses mutable state, concurrency, and more besides. For each module, you need to decide either to re-implement it using .NET primitives, or to implement the stuff the module is based on. These challenges are mostly broad rather than deep. But to get a production quality implementation that runs a substantial majority of Haskell programs "out of the box" requires a decent stab at all of them.

2 1

RE: [Haskell-cafe] I/O interface
by Simon Marlow 19 Jan '05

19 Jan '05

On 18 January 2005 00:27, Ben Rudiak-Gould wrote: > Marcin 'Qrczak' Kowalczyk wrote: > > >Convenience. I'm worried that it uses separate types for various > >kinds of streams: files, pipes, arrays (private memory), and > sockets. >Haskell is statically typed and lacks subsumption. This > means that >even though streams are unified by using a class, code > which uses >a stream of an unknown kind must be either polymorphic > or use >existential quantification. > > Yes, this is a problem. In my original proposal InputStream and > OutputStream were types, but I enthusiastically embraced Simon M's > idea of turning them into classes. As you say, it's not without its > disadvantages. I recognised this problem, which is why TextInputStream and TextOutputStream are existential wrappers around streams. Most clients will be using the Text streams, so they won't suffer from the polymorphism problem. However, we could also provide a non-overloaded version using one of Ben's solutions: > I see several possibilities here. > > * We could adopt Avery Lee's suggestion (from the discussion in > 2003) to use field labels instead of methods. Advantages: InputStream > and OutputStream behave more like their OOP equivalents, with no loss > of extensibility. Disadvantages: potentially less efficient (no > specialization possible); loses some static type information. Unfortunately GHC isn't nearly as good at optimising records as it is at optimising type class overloading. Of course, type class overloading is just a special case of polymorphic records, but there you go. > * We could use a single type for all input and output streams in > the standard library, but retain the type classes also. > > * We could provide existential wrappers: > > data IStream = (InputStream a) => MkIStream !a > instance InputStream IStream where ... This one gets my vote. BTW, Marcin: the library in the prototype implementation differs somewhat from the version of the interface in the Haddock docs. The docs were written before I started hacking on the prototype. Cheers, Simon

1 0

Re: [Haskell] Re: Why is getArgs in the IO monad?
by Marcin 'Qrczak' Kowalczyk 19 Jan '05

19 Jan '05

Keean Schupke <k.schupke(a)imperial.ac.uk> writes: > Surely both requirements can be satisfied if the programs arguments are made > parameters of main: > > main :: [String] -> IO () >From info '(libc)Error Messages', about program_invocation_name and program_invocation_short_name: *Portability Note:* These two variables are GNU extensions. If you want your program to work with non-GNU libraries, you must save the value of `argv[0]' in `main', and then strip off the directory names yourself. We added these extensions to make it possible to write self-contained error-reporting subroutines that require no explicit cooperation from `main'. This suggests that making global parameters available only as arguments of main would be a bad idea. But they should be settable, to account for the rare case of wanting to substitute something else to a library which reads them itself. -- __("< Marcin Kowalczyk \__/ qrczak(a)knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/

2 1

Re: performance question (John Meacham)
by Stijn De Saeger 19 Jan '05

19 Jan '05

thanks Ben and John, your ideas looked like they may speed up things indeed, so i went along with them and reimplemented the whole thing.... to my surprise, the program got considerably slower even ! here is the new code. > data ILtype = II | IE | EI | EE | NII | NIE | NEI | NEE deriving (Eq, Ord) (... I found no increase in performance by using the UNPACK pragma as you suggested, so I just ommitted it in this version...) > data Interval = Range ILtype !Double !Double deriving (Eq, Ord) > instance Show Interval where > show (Range iltype x y) = case iltype of > II -> if x == y then (show x) > else "[" ++ (show x) ++ ".." ++ (show y) ++ "]" > IE -> "[" ++ (show x) ++ ".." ++ (show y) ++ ")" > EI -> "(" ++ (show x) ++ ".." ++ (show y) ++ "]" > EE -> "(" ++ (show x) ++ ".." ++ (show y) ++ ")" > NII -> "Not " ++ show (Range II x y) > NIE -> "Not " ++ show (Range IE x y) > NEI -> "Not " ++ show (Range EI x y) > NEE -> "Not " ++ show (Range EE x y) the flip of interval types: > ilFlip :: ILtype -> ILtype > ilFlip ilt = case ilt of > II -> NII > IE -> NIE > EI -> NEI > EE -> NEE > NII -> II > NIE -> IE > NEI -> EI > NEE -> EE The complement of Intervals : > intComplement :: Interval -> Interval > intComplement (Range iltype x y) = (Range (ilFlip iltype) x y) membership function for Intervals: > isIn :: Double -> Interval -> Bool > isIn r (Range iltype x y) = case iltype of > II -> r >= x && r <= y > IE -> r >= x && r < y > EI -> r > x && r <= y > EE -> r > x && r < y > NII -> r > y || r < x > NIE -> r > y || r <= x > NEI -> r >= y || r < x > NEE -> r >= y || r <= x As always, any further comments or insights greatly appreciated. stijn.

1 0

styles
by Matthew Roberts 19 Jan '05

19 Jan '05

Haskell seems to be a language that allows for lots of different programming styles. The most obvious being pointed v.s. point free. As a programmer born and raised on OO - I have found the pointed style to suit me better. However, there are other distinctions. I heavily use "let in" and "where" to break up each function into smaller parts while I see other programmers putting everything in one line. I have seen the evolution of a Haskell programmer joke and most of it goes over my head. My question is "Is there standard terminology for the different programming styles in Haskell (besides pointed and point-free)?" Matt

2 1

Re: Books on Haskell
by David Owen 19 Jan '05

19 Jan '05

Hi, I have 3 Haskell books, The Craft of Functional Programming (Thompson), Introduction to Functional Programming Using Haskell (Bird) and The Haskell School of Expression (Hudak). I recommend Thompson's book because it contains good explanations and lots of exercises, although the book is quite big and takes some time to work through. Bird's book is a bit shorter and is good for explanations too but it isn't quite so hands on as it contains fewer exercises. Hudak's I feel is a bit too advanced for a first read, it focusses on using the Hugs graphics library and I think that the graphics examples can sometimes cloud the simple ideas that are trying to be explained. I'll probably try reading it again in the future. All the best Dave O

3 2

About instance
by Ulises Juarez Martinez 19 Jan '05

19 Jan '05

Hi. I have the next definitions: type Ocurrence = (String, Int) type Inside = [Ocurrence] data Pattern = Return Inside | Abort | Filter (Ocurrence -> Bool) Pattern beyond :: Pattern -> Pattern beyond (Filter pred Abort) = Abort -- more definitions of beyond optimous :: Pattern -> Pattern optimous p = fixPoint beyond p where fixPoint f x = if(f x == x) then x else fixPoint f (f x) When I load the program an error is produced: ERROR - An instance of Eq (Event -> Bool) is required to derive Eq Pattern I put: data Pattern = Return Inside | Abort | Filter (Ocurrence -> Bool) Pattern deriving (Eq) and a new error was produced: ERROR - An instance of Eq (Ocurrence -> Bool) is required to derive Eq Pattern Who can I do an instance of Eq (Ocurrence -> Bool)? Is there another option to avoid the error? Regards Ulises _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

2 1