- Haskell-Cafe - Haskell.org

Consequences of newtype deriving implementation w.r.t. base classes
by Twan van Laarhoven 13 Mar '07

13 Mar '07

I just noticed some unexpected consequences of the way newtype deriving is implemented in GHC. Because the dictionary of the underlying type is reused, so are base classes. This message is a literate Haskell program illustrating the problem. > {-# OPTIONS_GHC -fglasgow-exts #-} This problem comes up when an instance method calls a method of a base class. Consider the following useless example: > class Show a => Show2 a where > show2 :: a -> String > show2 = show > > instance Show2 Int Now consider a type deriving Show2, but having a different implementation of Show (also derived). > newtype Meter = Meter Int > deriving (Eq, Show, Show2) Now, for show2 the derived Show instance (which also shows the constructor name) is *not* used, instead the Show Int instance is used: ] > show2 (Meter 1) ] "1" ] > show (Meter 1) ] "Meter 1" This is quite unexpected, unless you consider what is going on behind the scenes. Even more confusingly, GHC requires that there is a Show instance for Meters, even if it will not be used! ] No instance for (Show Meter) ] arising from the superclasses of an instance declaration at ... ] Probable fix: add an instance declaration for (Show Meter) ] In the instance declaration for `Show2 Meter' This problem can come up whenever a class instance uses a function from a base class. Right now this not likely happen, but it will become more common if the standard classes are split up: > class Additive a where > add :: a -> a -> a > class Additive a => Subtractive a where > neg :: a -> a > sub :: a -> a -> a > sub x y = add x (neg y) -- calls base class function add > class Functor m => Monad' m where > return' :: a -> m a > join' :: m (m a) -> m a > join' x = bind' x id > bind' :: m a -> (a -> m b) -> m b > bind' ma k = join' (fmap k ma) -- calls base class function fmap As a solution I would suggest that newtype deriving a class instance is only allowed if all base classes instances are also derived using newtype deriving. This presents problems for Show and Read, because they cannot be derived in that way. It will, however, catch problems with most other classes. Twan van Laarhoven

2 1

ICFP07 Final CFP & Note from the Program Chair
by Matthew Fluet (ICFP Publicity Chair) 13 Mar '07

13 Mar '07

Call for Papers ICFP 2007: International Conference on Functional Programming Freiburg, Germany, 1-3 October 2007 Important Dates ~~~~~~~~~~~~~~~ Submission: 11:00 6 April 2007, Samoa time (AST) Author response: 11:00 23 May to 11:00 25 May 2007 (AST) Notification: 8 June 2007 Final papers due: 20 July 2007 Note from the ICFP07 Program Chair As the April 6 deadline for ICFP approaches, we thought it might be useful to call potential authors' attention to several significant points in the Call for Papers, the full text of which can be found at http://icfp07.eecs.harvard.edu/cfp.html Experience Reports ~~~~~~~~~~~~~~~~~~ This year ICFP is soliciting a new category of paper: the Experience Report. An Experience Report is a short paper of 2--4 pages. Unlike a normal ICFP paper, it is not intended to add to the body of *knowledge* of the functional-programming community. Rather, each Experience Report will add to a body of published, refereed, citable *evidence* that functional programming really works--or will describe obstacles that prevented it from working. Double-blind review ~~~~~~~~~~~~~~~~~~~ A reviewer's attitude toward a submission may be affected, even unconsciously, by the identity of the author. Our reviewers want to be able to approach each submission without such involuntary reactions as ``Peyton Jones; he writes a good paper'' or ``Who are these people? I have never heard of them.'' We especially want to ensure that work submitted by newcomers to our community gets the same careful consideration and scrutiny as the work of our best-known people. We are therefore requesting that authors make it possible for their submissions to be reviewed without forcing the reviewers to know who the authors are. Once all reviews are written, identities will be revealed at the PC meeting. For authors, this process should be simple: * Omit authors' names from your title page (or list them as ``omitted for submission''), and when you cite your own work, please make it difficult to figure out exactly who you are, even if a reviewer might be able to make a good guess. * If your submission is supported by other material, such as a technical report containing lengthy proofs, please do not cite this material on the web---instead, submit a zip file including both your paper and the technical report. Detailed guidelines can be found at http://icfp07.eecs.harvard.edu/blind.html Firm length limit; no appendices ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The 12-page limit (for full papers) and 4-page limit (for Experience Reports) are *firm*. Papers exceeding these limits will be rejected summarily by the program chair. If an author wishes to include an appendix which would put the main submission over the limit, the appendix must be submitted as a separate document, in a zip file with the main submission. It is understood that the reviewers' only obligation is to read the main submission; material beyond the 12-page limit may well go unread. Other details ~~~~~~~~~~~~~ We are encouraging author-date citations (Peyton Jones and Wadler 1993) rather than the default numbered citations [27]. LaTeX users can \usepackage{natbib} and \bibliographystyle{plainnat}. The submission deadline is late morning Samoan time, but in many times zones of interest, this is equivalent to late afternoon or early evening.

1 0

haskell and webapplications + a WASH and a WebFunction question
by Marc Weber 13 Mar '07

13 Mar '07

Hello, I've noticed that the summer of code tickets contain one item: "lightweight web framework". I've dropped out university one year ago. So I can't participate, right? Do you want to explore with me how this might be done propably using HAppS or fastcgi ? I just need another person to talk to to. (mailinglist will do as well ;) I think webfunction is a very good starting point. Would it be worth adding a page like haskellIDE http://haskell.org/haskellwiki/HIDE to collect ideas ? There are still some question I could not answer yet eg: WASH: How is askContinuously used? did anyone use WASH with FastCGI ? I've tried looking at the apis. FastCGI (mantained by Bringert) seems to need the HTTP response as plain text (either ByteString or lazy String) whereas WASH wants to write to a handle (see function start wehere initEnv stdin stdout) is called and sets cgiHandle which seems to be the handle to be written to. Did I get this right? Is there an easier way then rewriting WASH? WebFunctions: When using dog http:localhost:8080.. dog prints the html page and waits still 10s because the WebFunction webserver waits for another request. This is caused by b <- myHWaitForInput h 10 in file LLWebServer.hs which makes it impossible to use benchmarking tools such as ab2 from apache. Do you know wether this is bug? Marc

1 0

Re: Type and State Confusion
by Hans van Thiel 13 Mar '07

13 Mar '07

Albert, Thanks very much for your explanation. I see now that I confused the state function with the f, but it's still not quite clear. data MyState a b = MyStateC ([a] -> ([a], b)) This defines an algebraic data type (...why is it called algebraic?) with two type variables and a unary constructor. instance Monad (MyState a) where return x = MyStateC (\tb -> (tb, x)) (MyStateC st) >>= f = MyStateC (\tb -> let (newtb, y) = st tb (MyStateC trans) = f y in trans newtb ) Now, if the instantiated a has type String, Int or whatever, I would understand, but the type of the Monad seems to be built up from two types. You write: ...y has type String. In more detail: in order for foo >>= toMyState to make sense, these must be the types: foo :: MyState String String st :: [String] -> ([String], String) y is forced to have type String for the sake of toMyState. But how do the two occurrences of String in the foo type, in general a and b, match to the single a in the instance declaration? In particular when I have: toMyState :: String -> MyState String Int toMyState x = MyStateC (f x) This is mapped onto a list of strings, on which the Prelude sequence is applied. sequence :: Monad m => [m a] -> m [a] You write: The >>= used by sequence is the same >>= in the MyState monad, since you instantiate m to MyState String. Therefore, sequence performs all the state transformations correctly, since >>= is correct. So the m becomes MyState String, and therefore the list elements have type (MyState String Int), or the other way around. I understand, from your explanation, how this works from there on, but I'm still confused about what the Monad is. Is it MyState which takes two types, or (MyState String) which takes one type? Or neither? Does it involve some 'sort of currying' of type parameters? Thanks again, Hans

2 2

GHC optimization changes evaluation strategy?
by Dusan Kolar 13 Mar '07

13 Mar '07

Hello all, the following program changes behavior if translated using different options for ghc compiler. Is this correct or not? I used The Glorious Glasgow Haskell Compilation System, version 6.6. And I would expect in both cases behavior 1. But I may be wrong... Thanks for any resolution. Dusan *Program:* $ cat Test.hs import System.IO.Unsafe import System.IO main = do putStr "Start...\n" putStr $ show $ falling' falling10000 putStr "\n" putStr $ show $ sorted' rising10000 putStr "Stop...\n" sorted' [] = True sorted' [_] = True sorted' l = sx l 1 where sx [] _ = True sx [_] _ = True sx (x:l@(y:ys)) n = if n==1000 then unsafePerformIO (putChar '.' >> hFlush stdout) `seq` x<=y && sx l 1 else x<=y && (sx l $! n+1) falling' [] = True falling' [_] = True falling' l = sx l 1 where sx [] _ = True sx [_] _ = True sx (x:l@(y:ys)) n = if n==1000 then unsafePerformIO (putChar '.' >> hFlush stdout) `seq` x>=y && sx l 1 else x>=y && (sx l $! n+1) rising10000 = [0..100000] falling10000 = [100000,99999..0] -- EOF *Behavior 1:* $ ghc Test.hs -o test $ ./test Start... ....................................................................................................True ....................................................................................................TrueStop... *Behavior 2:* $ rm test Test.o Test.hi $ ghc -O2 Test.hs -o test $ ./test Start... .True .TrueStop... -- Dusan Kolar tel: +420 54 114 1238 UIFS FIT VUT Brno fax: +420 54 114 1270 Bozetechova 2 e-mail: kolar(a)fit.vutbr.cz Brno 612 66 Czech Republic --

2 1

Ann: regex-base-0.91
by Chris Kuklewicz 13 Mar '07

13 Mar '07

I have updated the darcs repository and the hackage repository to have regex-base-0.91 Changes: GHC uses late instance overlap detection, whereas Hugs demands no potential overlap. Thus Hugs rejected some of the polymorphic results for matching given by RegexContext instances. The solution in version 0.91 of regex-base is to use newtypes. To this end there are 4 newtypes which are used to disambiguate some of the more complicated return types of match/matchM/=~/=~~. The new haddock documentation for Text.Regex.Base.Context has more details and lists all the instances. The 4 newtypes are: > newtype AllSubmatches f b = AllSubmatches {getAllSubmatches :: (f b)} > newtype AllTextSubmatches f b = AllTextSubmatches {getAllTextSubmatches :: (f b)} > newtype AllMatches f b = AllMatches {getAllMatches :: (f b)} > newtype AllTextMatches f b = AllTextMatches {getAllTextMatches :: (f b) } The 'f' parameters are containers types, such as [] or (Array Int). The two *Submatches types report all the captured (i.e. parenthesized) groups of the first match found. The two *Matches types report on the all the non-overlapping matches found. This clarifies the desires of the programmer and allows choice of either result to be made. The two *Text* version have the type of the searched text included in the type of the result 'b', unlike the other two types. This avoids overlapping. These newtypes are not used for all the instances, but only where they are needed to either avoid overlapping or remove possible confusion. Using this newtype schema has allowed a few new instances to be added. In particular all the instances should have a [] or (Array Int) option for the returned container. -- Chris Kuklewicz

1 0

idea for avoiding temporaries
by David Roundy 13 Mar '07

13 Mar '07

Hi all, I was just teaching a class on minimization methods, with a focus on conjugate gradient minimization in particular, and one of my main points was that with conjugate gradient minimization we only need three or four arrays of size N (depending on whether we use the Fletcher-Reeves or Polak-Ribiere variant), that this was a huge win, and I was explaining that in my code we use Fletcher-Reeves even though it's generally got less stable convergence behavior, because avoiding one extra copy is well worth it, when each copy is on the order of a gigabyte (which is not unusual in my line of work). This got me thinking about one of the largest problems with writing serious numerical code in Haskell, which is that of memory consumption and avoiding temporary variables. The count of three arrays requires assumes that we do in-place updates, which presupposes an imperative model. But the main reason I'd like to switch to Haskell is so that I can write pure functional code, which is easier to read, easier to reason with, and easier to get right. So I started wondering whether there's a solution that would allow us to write pretty high-level pure functional code, while the RTS can realize at run-time that we have the only reference to the input argument and that it is therefore safe to consume it destructively. My thought is to move some of the amazing rewriting streams stuff that's going on with Data.ByteStream and Manuel's array fusion work onto the memory management level. If we can rewrite high-level array manipulations into a form in which the compiler can fuse the loops and write good low-level code, why not also allow automatic in-place updates (when possible)? My thought is to create a function like the following: copy :: ForeignPtr a -> IO (ForeignPtr a) This function ordinarily copies its input into a new chunk of memory, and then calls the initialization function to update that memory. So we could call it with something like a `plus` b = do a' <- copy a a' `plusEqual` b return a' Of course, in practice I imagine this whole business being encapsulated in a module where it's called with unsafePerformIO (but it's really perfectly safe, a la Data.ByteString). The key is that copy will ask the GC to check whether there is more than one reference to its input, and if there isn't, then it'll return its input without making a copy. Obviously, we'd want to be careful in making calls to copy (since the GC overhead could overwhelm the potential (transient) memory savings. And I've got no idea how hard it would be to find out if there are no other references, or how effective this would be... that is, whether the compiler might generate "false" references to the input that would prevent the savings from ever being realized. There are also other questions. My copy above is simple, but probably we'd be better off with a more general: copy :: a -> (a -> IO a) -> IO a which could be used in the base libraries for other sorts of objects, such as Array, which might not have a ForeignPtr at their back end. We might also want a more general copy that would handle the case where we would like to copy either one variable or another, and we don't care which. i.e. we in my `plus` example above, if "a" can't be discarded, but "b" can, we'll be out of luck. Perhaps we want something like reuseOrNot :: a -> (a -> IO b) -> (a -> IO b) -> IO b which would call one function or the other, depending on whether the input is deemed expendible by the GC, so we could write a `plus` b = reuseOrNot a (\a' -> do { a' `plusEqual` b; return a' }) (\a' -> reuseOrNot b (\b' -> do { b' `plusEqual` a'; return b' }) (\b' -> a' `boringAdd` b')) where boringAdd is an addition that doesn't reuse either array. Anyhow, all this would be predicated on the possibility of asking the GC whether anyone else has a reference to a given object, and I've no idea how tough (or slow) this would be. It'd also be effectively predicated on someone like dons having the time and interest to write good fusion code which would allow one to make use of this in referentially transparent high-level pure functional code. I think it'd be pretty cool, and would certainly (not immediately, but as my research group ramps up) be interested in being a guinea pig user of this stuff. Any thoughts? Am I crazy? Is this infeasible for some reason? Should I have patented this idea before mentioning it on the list? Has someone else already patented it? -- David Roundy Department of Physics Oregon State University

18 50

Random/StdGen/read: there is something unclear (or misunderstood!)
by Zara 13 Mar '07

13 Mar '07

Sorry if this question is too basic, but I am trying to learn Haskell and from tiem to time I get stuck. (And forgive me, I haev a heavy procedural background, so functional programming is hard for me) I am trying to use 'read' to create a random generator, applying it on some text. As the Report, says: # In addition, 'read' may be used to map an arbitrary string (not # necessarily one produced by 'show') onto a value of type 'StdGen'. # In general, the 'read' instance of 'StdGen' has the following # properties: # # * It guarantees to succeed on any string. # # * It guarantees to consume only a finite portion of the string. # # * Different argument strings are likely to result in different # results. But it does not succeed on "any string". Code follows \begin{code} module Pepe where import Random pepin :: StdGen pepin = read "cosita" pepe :: StdGen pepe = read "cositaLinda" \end{code} If I evaluate pepin, results are: Hugs> pepin 38273 1 :: StdGen (360 reductions, 554 cells) But if I evaluate pepe, all changes: Hugs> pepe Program error: Prelude.read: no parse (380 reductions, 694 cells) Am I misunderstanding something, or is StdGen -> read buggy? As you can see, I am using Hugs, version Sep 2006 to test. TIA, best regards, Zara

2 1

Church Encoding Function
by Joachim Breitner 13 Mar '07

13 Mar '07

Hi, some more ideas following from the last post. I noticed how the function Data.Maybe.maybe converts a Haskell Maybe into a Church encoded Maybe. Also, the if construct, interpreted as a function, converts a Bool into a church encoded Bool. If lists are encoded as forall b. (a -> b -> b) -> b -> b, then foldr, with the right order of arguments, converts a haskell [] to a Church encoded List. Is there a name for these functions? “Characteristic Church Encoding Functions” maybe? Are there more than these: Maybe -- maybe Bool -- ifthenelse List -- foldr (,) -- uncurry Just a short idea while waiting at the airport... Greetings, Joachim -- Joachim "nomeata" Breitner mail: mail(a)joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: joachimbreitner(a)amessage.de | http://www.joachim-breitner.de/ Debian Developer: nomeata(a)debian.org

9 9

Haskell for Accessibility
by Tom Hawkins 13 Mar '07

13 Mar '07

I love programming in Haskell, yet even its concise expressions have not saved my tendons from chronic RSI. Has anyone put any thought into building an accessible Haskell development interface for those who may not be able to use a keyboard? One inspirational program is Dasher (http://www.inference.phy.cam.ac.uk/dasher/) Not only is it godsend for people with a wide range of disabilities, Dasher is also a lot of fun to use. Though Dasher is good at general text entry, it's not well suited for programming. However, combining Dasher's statistical inference with Haskell's type inference might yield a graphical, cursor driven interface even more efficient than the conventional keyboard. Is there interested in such a project? I don't have the expertise or typing strength (pun intended) to go it alone, but I could lend a hand. Here are a few random ideas: - A tree viewer to navigate and manage directories, modules, module declarations, and expressions. Similar to a directory explorer, nodes in the tree can be collapsed and expanded. Collapsed module definitions would display the type annotation, while hiding the definition. - Another interface for composing expressions. This interface could be similar to Dasher, but use both statistical inference and type inference to weight and prune the decision tree. The expression composer interface could directly assemble the abstract syntax tree, thus eliminating the need for whitespace and ()s. Of course, the tree viewer would pretty print all expressions in the familiar Haskell layout. - The development environment could be hosted as a web server, delivering SVG and minimal JavaScript for the client-side interface, allowing Haskell program development from any web browser with a 2 button mouse -- head mounted or eye tracked, of course. The client-server architecture would allow developers to concurrently work from the same source code. - >From the tree viewer, click any expression to view the compiler's inferred type, with the ability to turn any inferred type into a concrete type annotation. And the ability to compare inferred types to type annotations. Type violations highlighted in red. - Variable references would not have to be explicitly spelled out. Instead, variables could be selected from either the tree viewer or expression composer, forming a hard link. When a variable's name changes, all references could be automatically updated. When an expression is either moved or copied into a new lexical scope, the variable references could be automatically rebound to variable definitions in the new scope. Unmatched referenced names and ambiguous names would be highlighted in red. -Tom

3 2