March 2007 - Haskell-Cafe

Re: Maybe and partial functions
by oleg＠pobox.com 14 Mar '07

14 Mar '07

Neil Mitchell wrote: > newtype N1 = N1 Int > (put that in a module and don't export N1) > > define the constant 2, define the increment operator, change div and mod. That is precisely what I would have done. > Now we've mainly got a proof in the type checker, but we still don't > actually have a proof for our core N1 definition - but I think that is > probably ok, provided it is a common core which can be reused and is > minimal. Any proof of totality of the original digits-of-e code must first prove or postulate that incrementing a positive number gives the positive number. So, one must prove/verify/assume the basic properties one way or another. In the lightweight static capabilities approach, these basic lemmas/properties/axioms are collected in modules, which can be verified once and for all and then used in various parts of the program. Accommodating the security kernel in those parts of the program does not seem to be a burden. In return, we get assurances of the simple kernel in those parts of the program without the need to run the verification algorithm all over again (on the possibly complex pieces of code). The idea that data type abstraction can enforce complex invariants was advocated back in 1973 by James H. Morris (the father of the guy who released the `Morris worm'), in the CACM paper "Protection in Programming Languages". http://www.erights.org/history/morris73.pdf

1 0

Re: [Haskell] Haskell Weekly News: March 12, 2007
by Conrad Parker 13 Mar '07

13 Mar '07

On 13/03/07, Wolfgang Jeltsch <g9ks157k(a)acme.softbase.org> wrote: > Am Montag, 12. März 2007 03:52 schrieb Donald Bruce Stewart: > > * [41]Why Publish CS Papers Without Code? > > 41. http://billmill.org/why_no_code > > Interesting! > > This leads me to the question how copyright of code fragments included in > conference papers is handled. Say, I submit a paper containing some code > fragments to the ICFP. I have to assign the copyright of the paper to the > ACM. Does this mean that the ACM will hold the copyright of the code > fragments? Does this mean that I'm not allowed to publish the source code > containing these code fragments as open source software somewhere? (I am not a lawyer, etc) If your paper simply cites, and quotes from, code that you have already published elsewhere (eg. on your own web site), then I think that would simply count as a citation. If on the other hand your paper contains your code verbatim and doesn't cite it (ie. the code is previously unpublished) then perhaps you are assigning the copyright of it. So it may be a good idea to always make available open source projects before publishing about them in academic papers, and to always include a citation to the open source project web site or tech report. Besides, <tshirt>If it's not open source, it's not computer science</tshirt>. Science demands repeatable results, computer science demands literate programming. The solution is not to shy away from including code, or else the IP lawyers have won, science is banned and we get plunged into another Dark Age. cheers, Conrad.

4 3

Maybe and partial functions
by Dougal Stanton 13 Mar '07

13 Mar '07

The Maybe construction is very useful for explicitly handling circumstances where the function cannot produce a sensible answer. But how far should this notion be taken? When you're writing a function which you realise may not produce what you want, in what circumstances would you use a Maybe, and when would you just throw an error? I'm wondering both in terms of good engineering practise and also for correctness. Should elementary partial functions like > 5 `div` 0 or > head [] return Nothing? I guess it's a bit of a silly suggestion, but it helps to highlight why we use Maybe in the first place. So --- where's the cutoff point in your code? Cheers, D. -- Dougal Stanton

5 4

Mixed-type arithmetic, or type coercion
by Dave Hinton 13 Mar '07

13 Mar '07

Arithmetic operators in haskell appear to require their operands to have the same type. How can I do arithmetic between operands of different types? Alternatively, how do I coerce a value from being an Int to being a Double? I am new to haskell. I have read a few tutorials but they do not mention this issue. I have read the haddock documentation for Prelude and Numeric, but cannot find anything that helps here. (I saw a couple of numeric conversion functions, but they won't turn an Int into a Double.) Toy example: $ cat eg.hs calc :: Int -> Double -> Double calc count weight = count * weight $ ghc eg.hs eg.hs:2: Couldn't match `Int' against `Double' Expected type: Int Inferred type: Double In the second argument of `(*)', namely `weight' In the definition of `calc': calc count weight = count * weight

4 3

Maybe and partial functions
by oleg＠pobox.com 13 Mar '07

13 Mar '07

Neil Mitchell wrote: > I suggest you try rewriting this program to be complete: > > http://darcs.haskell.org/nofib/imaginary/digits-of-e2/Main.lhs > > (if you do, please post the result to the list) As Gen Zhang noted, the problem seems to be quite straightforward: just express in types the fact that we deal with infinite streams and so Nil just cannot happen. One way of doing this as follows. Showing totality (that is, termination of recursion in carry propagate) is harder. But re-writing the program so to avoid head/tail on the empty list is easy: module E where import Prelude hiding (head, tail, map, iterate, take) data I a = C a (I a) deriving Show -- these are total functions: they give WHNF in one step provided non-bottom -- arguments head (C a _) = a tail (C _ l) = l map f (C a l) = C (f a) (map f l) rept a = C a (rept a) take n (C a l) | n > 0 = a:take (n-1) l take _ _ = [] iterate f z = C z (iterate f (f z)) -- There are no pattern-matching failures here. -- The totality is harder to see: all digits are roughly of the same range, -- but each recursive call increments base. Eventually, base becomes bigger -- than d+9 and so the first alternative will be selected, which is in the -- WHNF and so recursion terminates. carryPropagate base (C d ds) | carryguess == (d+9) `div` base = C carryguess (C (remainder+nextcarry) fraction) | otherwise = (C (dCorrected `div` base) (C (dCorrected `mod` base) fraction)) where carryguess = d `div` base remainder = d `mod` base C nextcarry fraction = carryPropagate (base+1) ds dCorrected = d + nextcarry e = map (show.head) $ iterate (carryPropagate 2 . map (10*) . tail) $ C 2 (rept 1) en n = "2." ++ concat (take n (tail e))

4 5

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