- Haskell - Haskell.org

Second IFL 2002 announcement
by Ricardo Pe~na 16 May '02

16 May '02

(Apologies for multiple postings) ============================================================ IFL 2002 14th International Workshop on the IMPLEMENTATION OF FUNCTIONAL LANGUAGES Madrid Spain September 16 - 18, 2002 ============================================================= Important dates --------------- Registration deadline: July 30th, 2002 Submission deadline : August 26th, 2002 further details : http://dalila.sip.ucm.es/ifl02 ============================================================= Scope of IFL 2002 ----------------- The aim of the workshop is to bring together researchers and users actively engaged in the implementation and application of functional programming languages to discuss results and new directions of research. The workshop is intended to provide an open forum for researchers who wish to present and discuss new ideas and concepts, work in progress, preliminary results etc. related primarily but not exclusively to the implementation of functional or function-based languages. A not necessarily exhaustive list of topics includes language concepts type checking compilation techniques (abstract) interpretation automatic program generation (abstract) machine architectures array processing concurrent/parallel programming and program execution heap management runtime profiling and performance measurements debugging and tracing verification of functional programs tools and programming techniques Contributions on applications of functional programming, e.g., in teaching, or on theoretical work in any of the above areas are also welcome. Contributions ------------- All attendees are encouraged to submit papers to be published in the draft proceedings and to give presentations at the workshop. Submitted papers must be written in English, conform to the LNCS format (available at: http://www.springer.de/comp/lncs/authors.html) and not exceed 16 pages. Papers should be submitted by August 26th as postscript or pdf files using the submission page of the workshop accessible through http://dalila.sip.ucm.es/ifl02. After the workshop, we intend to publish a high-quality subset of contributions in the Springer LNCS series. All speakers attending the workshop are invited to submit a paper. Papers for the LNCS proceedings will be refereed according to normal conference standards. Ricardo Pe~na (IFL 2002 Organizing Committee Chairman) Departamento de Sistemas Informaticos y Programacion Facultad de Informatica Universidad Complutense de Madrid, 28040 MADRID e-mail: ricardo(a)sip.ucm.es Ph: (+ 34) 91 394 4313 FAX: (+ 34) 91 394 4602 http://dalila.sip.ucm.es/~ricardo

1 0

Newbie attempts to generate permutations
by Mark Phillips 16 May '02

16 May '02

Hi, I have recently started learning Haskell and, in writing a HUGS module to generate permutations, have been told I have an error but I don't understand why. The module is: module Arrange where -- -- perms :: [a] -> [[a]] perms [] = [[]] perms (a:as) = concatMap (\b -> fst b:perms (snd b)) (del (a:as)) del :: [a] -> [(a,[a])] del [] = [] del (a:as) = (a,as):(map (\b -> (fst b,a:(snd b))) (del as)) and it comes back with error message: Type checking ERROR Arrange.hs:6 - Type error in application *** Expression : concatMap (\b -> fst b : perms (snd b)) (del (a : as)) *** Term : \b -> fst b : perms (snd b) *** Type : ([a],[a]) -> [[a]] *** Does not match : (a,[a]) -> [[a]] *** Because : unification would give infinite type But why does it say that the term "\b -> fst b : perms (snd b)" has type "([a],[a]) -> [[a]]"? perms requires a type "[a]" as input so "snd b" should be of type "[a]" but "fst b" should be allowed to be anything. What's going on? Any help would be much appreciated. Thanks, Mark. -- Dr Mark H Phillips Research Analyst (Mathematician) AUSTRICS - Smarter Scheduling Solutions - www.austrics.com Level 2, 50 Pirie Street, Adelaide SA 5000, Australia Phone +61 8 8226 9850 Fax +61 8 8231 4821 Email mark(a)austrics.com.au

1 1

Re: State monads don't respect the monad laws in Haskell
by Ashley Yakeley 16 May '02

16 May '02

At 2002-05-15 09:48, John Launchbury wrote: >Will the next version of Haskell have something better. I hope so, but I >fear not. Rename it "unsafeSeq"? No puns please... But I think breaking Monad laws etc. is a different kind of unsafeness from usPIO etc. -- Ashley Yakeley, Seattle WA unsafePerformIO is NOT Haskell!

1 0

Re: State monads don't respect the monad laws in Haskell
by Jan-Willem Maessen 15 May '02

15 May '02

Dylan Thurston writes: > Do you ever use floating point addition? > > I rarely use floating point, but it is sometimes more useful than the > alternatives, as long as you bear in mind its limitations. Yep, floating point is by necessity a bit of a mess. On the other hand, I don't think we ought to be claiming that addition of Nums is associative, because it just isn't true. (Indeed, if we trap overflow then even Int addition is non-associative; I'm agin overflow trapping on Int for this among other reasons.) I see four "solutions" to the problem of non-associativity of floating point, in approximate order of flexibility: 1) Declare that Num is never associative. Compilers may re-associate (+) only if the types involved can be shown to be associative. Programmers may of course re-associate (+) in other cases as well, if they know what they are doing. 2) Provide a compiler flag which indicates that the compiler can assume assocativity of Num and optimize accordingly. Similar flags exist for other compilers (gcc's -ffast-math comes to mind). 3) Provide an associative floating-point hierarchy, to be used with the knowledge that "associativity" of such a type is only an approximate notion. 4) Provide a way of annotating Num instances to indicate the associativity property. I have no idea what form such an annotation would take. I therefore suspect (1) or (2) is good enough. (3) is way more trouble than it's worth, I bet; (4) is a nifty research problem with (so I hear) a certain amount of related research already out there. The real problem of course is things like this: "Solve y = x + b for x given y and b". We can't technically even *solve* the equation if addition is non-associative. But this is, of course, a problem in *every* language with limited-precision floating point. We probably need to be forthright about this when educating new programmers. I'm less clear how to couch this when presenting Num to the experienced programmer. Note that non-associativity is only one difficulty in working with floating point. Instability caused by different register and memory precision on x86 has proven to be a very noticable problem for me during compiler development. The -fforce-mem option on gcc addresses this issue at the cost of performance; my (limited) understanding of the problem indicates that this flag sacrifices (false) extra precision for predictability and thus for better accuracy (if you know what you are doing). This has nothing to do with declared semantics and everything to do with implementation hackery. > This sounds very interesting! Is your dissertation available? I'm making the last few fixes; it will be signed at the end of the week and I'll gladly send out a link to the Haskell mailing list when it's done. -Jan-Willem Maessen

1 0

MPC 2002: Deadline extended until 11 February
by mpc02 15 May '02

15 May '02

[Apologies for multiple copies] The deadline for MPC 2002, 6th International Conference on MATHEMATICS OF PROGRAM CONSTRUCTION, 8-10 July, Dagstuhl, Germany (see http://www.cs.ukc.ac.uk/conf/mpc2002/ for a full CFP) has been extended until 11 February 2002. Full papers should be submitted in Postscript or pdf format by e-mail to mpc02(a)ukc.ac.uk. -- Mathematics of Program Construction '02 at Dagstuhl Eerke Boiten, Computing Laboratory, University of Kent at Canterbury, UK +44.1227.827615 (fax 762811)

1 1

`seq` breaks the foldr/build-rule
by Janis Voigtlaender 15 May '02

15 May '02

Hello, while we are talking about strange semantic inequalities in the presence of `seq` (supposed monads not satisfying the monad laws anymore...), I just wanted to reiterate a point I made in a previous post, namely that `seq` also makes the foldr/build-rule of shortcut deforestation [1] wrong. Consider the following (admittedly artificial) program: build:: (forall b . (a -> b -> b) -> b -> b) -> [a] build g = g (:) [] original :: [Int] -> Int original l = foldr const 0 (build g) where g c n = let h [] = n h (x:xs) = let f=h xs in (c x f) `seq` (c 1 f) in h l The foldr/build-rule says that for all g of appropriate type holds: foldr k z (build g) = g k z i.e., the function "original" should be equivalent to the following: optimized :: [Int] -> Int optimized l = g const 0 where g c n = let h [] = n h (x:xs) = let f=h xs in (c x f) `seq` (c 1 f) in h l But now we have a problem! In Hugs: Main> original [undefined] 1 (19 reductions, 35 cells) Main> optimized [undefined] Program error: {undefined} (10 reductions, 57 cells) i.e. on the argument list [undefined] the "original" function yields a nice result, while the "optimized" function fails at runtime. This is not quite an optimization, right? For list producers expressed with build in the Prelude this incorrectness shouldn't be harmful (if they do not use `seq`). But if one wants to write ones own list producers for shortcut deforestation, or to use Olaf Chitil's type-inference based deforestation [2], one has to be extremely careful with using `seq`. [1] A. Gill, J. Launchbury and S.L. Peyton Jones. A Short Cut to Deforestation. In Functional Programming Languages and Computer Architecture, Copenhagen, Denmark, Proceedings, pages 223-232. ACM Press, June 1993. [2] O. Chitil. Type Inference Builds a Short Cut to Deforestation. In International Conference on Functional Programming, Paris, France, Proceedings, volume 34 of ACM SIGPLAN Notices, pages 249-260, September 1999. -- Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

1 0

RE: Haddock installing problems
by Simon Marlow 15 May '02

15 May '02

> I was trying to install/compile Haddock 0.1 in my computer > (Windows98 + Cygwin, GHC-5.02.3), but I got the following error message: > > You must install the version of Perl shipped with GHC > (or a compatible one) in /bin. > > I though I already had a version of Perl in my computer, since HOpenGL > (which uses it) was compiled succesfully. My /bin dir also > contains a file > called perl.exe and another dir called Perl (which contains > perl.exe too). This works for me, but I'm not a Cygwin/Windows expert so I'm not sure what the canonical answer should be. On my system I have the Cygwin perl.exe in /cygwin/bin, and this is also /bin under cygwin, because by default Cygwin seems to want to mount /cygwin as /. I've just successfully build Haddock on WinXP with a fresh install of Cygwin, GHC 5.02.3, and surprisingly little fiddling about (I think I had to set PATH to include GHC, but that was it). Cheers, Simon

2 1

(no subject)
by LAURENT MPETI KABILA 15 May '02

15 May '02

REQUEST FOR URGENT BUSINESS ASSISTANCE -------------------------------------- I stumbled into your contact by stroke of luck after a long search for an honest and trust worthy person who could handle issue with high confidentiality. I was so dilghted when i got your contact and i decided to contact you and solicite for your kind assistance. i hope you will let this issue to remain confidential even if you are not interested because of my status. I am Laurent Mpeti Kabila (Jnr) the second son of Late President LAURENT DESIRE KABILA the immediate Past president of the DEMOCRATIC REPUBLIC OF CONGO in Africa who was murdered by his opposition through his personal bodyguards in his bedroom on Tuesday 16th January, 2001. I have the privilege of being mandated by my father,s colleagues to seek your immediate and urgent co-operation to receive into your bank account the sum of US $25m. (twenty-five million Dollars) and some thousands carats of Diamond. This money and treasures was lodged in a vault with a security firm in Europe and South-Africa. SOURCES OF DIAMONDS AND FUND In August 2000, my father as a defence minister and president has a meeting with his cabinet and armychief about the defence budget for 2000 to 2001 which was US $700m. so he directed one of his best friend. Frederic Kibasa Maliba who was a minister of mines and a political party leader known as the Union Sacree de,opposition radicale et ses allies (USORAL) to buy arms with US $200m on 5th January 2001; for him to finalize the arms deal,my father was murdered. f.K. Maliba (FKM) and I have decided to keep the money with a foreigner after which he will use it to contest for the political election. Inspite of all this we have resolved to present you or your company for the firm to pay it into your nominated account the above sum and diamonds. This transaction should be finalized within seven (7) working days and for your co-operation and partnership, we have unanimously agreed that you will be entitled to 5.5% of the money when successfully receive it in your account. The nature of your business is not relevant to the successful execution of this transaction what we require is your total co-operation and commitment to ensure 100%risk-free transaction at both ends and to protect the persons involved in this transaction strict confidence and utmost secrecy is required even after the uccessful conclusion of this transaction. If this proposal is acceptable to you, kindly provide me with your personal telephone and fax through my E-mail box for immediate commencement of the transaction. I count on your honour to keep my secret, SECRET. Looking forward for your urgent reply Thanks. Best Regards MPETI L. KABILA (Jnr)

1 0

Re: State monads don't respect the monad laws in Haskell
by S.M.Kahrs 14 May '02

14 May '02

> "S.M.Kahrs" wrote: > [snip] > > I don't think this really solves the problem with the left unit > > (not in general, and not for IO either), > > it merely pushes it to a different place. > [snip] > Not being a category theorist I find this all a bit confusing. Nothing to do with category theory. I took the law you cited and checked it out. > Can you > give an example where with GHC and the fix I suggested you can show that > the associative law has been broken? I didn't try to find a counter example. I tried to prove the result and got stuck: This is the law I was stuck with: m >>= (\x -> k x >>= h) === (m >>= k) >>= h There were two cases to consider, m=R a, and m=M a - the former works out nicely, but with the latter you get: m >>= (\x -> k x >>= h) = M a >>= (\x -> k x >>= h) = M (a >>= \a'->case (\x -> k x >>= h) a' of R b -> return b M c -> c) = M (a >>= \a'->case (k a' >>= h) of R b -> return b M c -> c) and on the other side: (m >>= k) >>= h = (M a >>= k) >>= h = M (a >>= \a'->case k a' of R b -> return b M c -> c) >>= h = M ((a >>= \a'->case k a' of R b -> return b M c -> c) >>= \a''->case h a'' of R b -> return b M c -> c) Assuming that the associativity law holds for the original monad (the one we try to fix for its dodgy left unit) then this can be changed to: M (a >>= \a' -> (\a'->case k a' of R b -> return b M c -> c) a' >>= \a''->case h a'' of R b -> return b M c -> c) = M ((a >>= \a' -> case k a' of R b -> return b M c -> c) >>= \a''->case h a'' of R b -> return b M c -> c) Using associativity again: = M (a >>= \x->(\a' -> case k a' of R b -> return b M c -> c)x>>=(\a''->case h a'' of R b -> return b M c -> c)) = M (a >>= \a' -> (case k a' of R b -> return b M c -> c) >>= \a''->case h a'' of R b -> return b M c -> c) Assuming further that >>= is left-strict we can change that to: = M (a >>= \a' -> (case k a' of R b -> return b >>= \a''->... M c -> c >>= \a''->...)) where the ... is twice the old case h a'' expression. Now, this is the expression why I claimed the left-unit property of the underlying monad would still show: if (return b>>=f) is the same as f b (in the monad we try to fix) then the first part of this case expression simplifies to exactly the same thing as we had derived from the other side of the equation. But if it does not hold, we should be able to construct a counter example using the left-unit counter example from the underlying monad together with, say, k=R. This all under the assumptions that the original monad m satisfied the assoc law and that its >>= is left-strict. Stefan Kahrs

1 0

using error x as a placeholder
by Hal Daume III 14 May '02

14 May '02

I've seen 'error "foo"' or simply 'undefined' used as a placeholder for elements in a structure which we, as programmers, know will be filled in soon. Often this makes the code clearer because the creation of the data structure and filling in its values is separated (you could argue with this, but that's not the point). This troubles me, though, because even though *we* know the elements will be filled in, maybe the strictness analyser doesn't. So, to test this, I wrote the following program: module Main where import Array sumArray :: Array Int Integer -> Integer sumArray arr = sumArray' 0 low where (low,high) = bounds arr sumArray' acc pos | pos > high = acc | otherwise = sumArray' (acc + (arr!pos)) (pos+1) mkArray1 :: Array Int Integer mkArray1 = fillInArr 1 (listArray (1,9999) (repeat undefined)) where fillInArr 5000 arr = arr // [(5000,arr!4999 + arr!5001)] fillInArr 1 arr = fillInArr 2 (arr // [(1,1),(9999,2)]) fillInArr n arr = fillInArr (n+1) (arr // [(n,(arr!(n-1))+(arr!(10001-n))),(10000-n,(arr!(n-1))+(arr!(10001-n))+1)]) mkArray2 :: Array Int Integer mkArray2 = fillInArr 1 (listArray (1,9999) (repeat 0)) where fillInArr 5000 arr = arr // [(5000,arr!4999 + arr!5001)] fillInArr 1 arr = fillInArr 2 (arr // [(1,1),(9999,2)]) fillInArr n arr = fillInArr (n+1) (arr // [(n,(arr!(n-1))+(arr!(10001-n))),(10000-n,(arr!(n-1))+(arr!(10001-n))+1)]) main = print $ (sumArray mkArray1) `mod` 1024 And compiled it using both mkArray1 (which has undefined elements, supposedly) and mkArray2, which doesn't. (I tried to come up with a function with which to fill in the array that was nontrivial, in the sence that it would be difficult to code using accumulators without the explicit recursive 'fillInArr' function.) The timing results were: mkArray1: 11.42u 0.79s 0:13.47 90.6% mkArray2: 24.55u 2.31s 0:30.12 89.1% Which is actually *slower*. Any ideas why? (These were compiled with ghc 5.02.3 -O2 -fvia-c -fall-strict) - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

1 0