May 2002 - Haskell - Haskell.org

Haddock installing problems
by Andre W B Furtado 08 May '02

08 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). Can anyone help me? Thans a lot, -- Andre

1 0

Deforestration harmful?
by Shin-Cheng Mu 07 May '02

07 May '02

Hi all, We encountered a case where elimination of intermediate data structure seeems to have a bad impact on the overall performance and we were wondering why. Relationally, our program would be as simple as: f . g where g :: Seed -> Tree1 and f :: Tree1 -> Tree2. Basically g generate some kind of tree via an unfold and f map a Tree1 to some (usually 3 or 4) Tree2. In reality we have to implement relations as set (or list) valued functions, so it becomes concat . map f. g where g looks like g seed = [ z | (s1, s2) <- split seed, x <- g s1, y <- g s2, z <- join x y ] The relation f was almost as simple as a replacing each constructor in Tree1 with one or more coresponding constructors in Tree2. They two can be fused together and becomes fg seed = [ z | (s1, s2) <- split seed, x <- fg s1, y <- fg s2, z <- join' x y ] The intermediate datatype Tree1 was thus eliminated. The problem was: the fused program ran slower than the original one! At least if you measure the total running time (either via the UNIX time command or use the CPUTime module). The time reported in the GHC time profile indeed showed that the fused program is faster, though, if GC time is excluded. We were quite curious why and my guess was: since f maps a Tree1 to more than one Tree2, in the two list comprehensions, the list produced by (fg s2) is much longer than (g s2). The fused program thus has to keep a longer list in memory. Worse heap residency results in more GCs. (Luckily GHC did not attempt to automatically perform the fusion for us! :) ) An obvious thing to try was to increase the heap size. Again we were surprised. Indeed the GC time decreased but the running time in the profile (excluding the GC time) increased a bit. Our guess was that it might have something to do with the way GHC allocates new memory cells such that larger heap results in longer allocation time. It was quite tricky to find the best heap size at which the program runs at maximal speed. Are the above guesses are plausible? Is it a known phenomena? Thank you very much. sincerely, Shin-Cheng Mu

2 2

updating labelled fields
by Hal Daume III 07 May '02

07 May '02

Hi, I often create structures like: data MyData = MyData { foo :: ..., bar :: ..., .... } and most of the time i do one of two things: 1) read values from the structure, as in: let x = (foo myData) in ... 2) update values in the structure, as in: let myData' = myData { foo = (foo myData)+1 } Only very rarely (usually only during intializization) do I actually put values into the structure that *don't* depend on their previous value. I end up with expresions like: ... myData { foo = (foo myData) + 1 ; bar = (bar myData) ++ "bar" ; ick = (ick myData) ! n ; ... } I was wondering if there existed any sort of "update" syntax. Obviously not real update, but enough to get rid of the "(foo myData)" parts of my epxression which really serve to just clutter up with expression. Perhaps something like: ... myData { foo <- (+1) ; bar <- (++"bar") ; ick <- (!n) ; ... } or the like, where "x { ... y <- e ... } is translated to "x { ... y = e (y x) ... }" (i only use "<-" because that seems to be the default extension symbol, i guess because we don't want to trample symbols people might actually use.) Anyway, does such a thing exist, and, if not, is there any chance it could exist, or is it just syntactic salt to too many people? :) - 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

3 3

Proper scaling of randoms
by oleg＠pobox.com 07 May '02

07 May '02

This message derives an integer interval mapping function that is not only provably within the given range but also "uniform". This is the function to use when mapping random integers from one interval to a smaller one. Problem: given an integer n within [0..maxn], design a scaling function sc(n) that returns an integer within [s..t], t>=s. The function sc(n) must be 'monotonic': 0<=a < b ==> sc(a) <= sc(b) and it must map the ends of the interval: sc(0) -> s and sc(maxn) -> t. One such function has been designed by Simon Thompson in his book: sct(n) = n `div` ((maxn+1) `div` (t-s+1)) + s Another function has been derived in the previous message on this list: sc1(n) = (n*(t-s)) `div` maxn + s The sct() function has a serious drawback: it is not guaranteed that sct(n) <= t (more about it below). The sc1() function is provably within the given range, and monotonic. Alas, it is not "uniform." When it comes to mapping of random integers, the mapping function must possess an extra property: it must "map uniformly." That is, given random numbers within [0..maxn] such that Prob(n==i) - const, we must aim at Prob(sc(n)==i') - const forall i' in [s..t]. The mapping function sc1(n) does not have this property. Any mapping function sc(n) from [0..maxn] to [s..t] for (t-s+1) < (maxn+1) maps several integers from the source interval to one integer of the target interval. An integer of the target interval therefore denotes an equivalence class of the integers from the source interval. The uniformity property will be satisfied only if the equivalence classes have the same size. This is only possible if (maxn+1) `rem` (t-s+1) == 0. Given this condition, the original Thompson's algorithm works. If (t-s+1) divides (maxn+1) exactly (i.e., exists denom integer. denom*(t-s+1) == maxn+1), we have j*denom <= n <= j*denom+denom-1 ==> sct(n) = j+s, all j=0..(t-s) Thus each equivalence class has the size denom, and mapping is perfectly uniform. As a consequence, s <= sct(n) <= t, given our assumption (maxn+1) `rem` (t-s+1) == 0. If this assumption does not hold, sct(n) may be greater than t (which Dimitre Novatchev has demonstrated). Alas, in this case there is no perfectly uniform mapping. The Thompson's algorithm misbehaves. The worst case for the algorithm is when t = s + (maxn+1)/2. For example, this occurs when we try to map [0..65535] to [0..32768]. In this case, t-s+1 = 32769, and denom = 65536 `div` 32769 == 1, thus the mapping becomes sct(n) = n. In almost half of the time, this mapping exceeds the upper limit 32768. OTH, the mapping sc1(n) = n*(maxn+1)/2 `div` maxn + s behaves in this pathological case rather well. Not only sc1(n) <= t (this is always guaranteed) but also the mapping is uniform: all equivalence classes of the source interval [0..65535] except the last two classes have the size of two. Thus the best solution should be to "average" sc1(n) and sct(n). This "averaging" is done by the formula sca = (n*(t-s) + (n*(denom-1) `div` denom)) `div` maxn + s where denom = (maxn+1) `div` (t-s+1) It is easy to see that sca(0) -> s. sca(maxn) = (maxn*(t-s) + (maxn*(denom-1) `div` denom)) `div` maxn + s = (maxn*(t-s) + p) `div` maxn + s {where 0<= p = (maxn*(denom-1) `div` denom) <= maxn-1 } = t-s+s = t It is easy to show that sca(n) is monotonic (as defined above). If maxn+1 is evenly divisible by (t-s+1) (that is, denom*(t-s+1) == maxn+1), we have j*denom <= n <= j*denom+denom-1 ==> sca(n) = j+s, all j=0..(t-s) This requires a proof. We have: sca(j*denom) = (j*denom*(t-s) + (j*denom*(denom-1) `div` denom)) `div` maxn + s = (j*denom*(t-s) + j*(denom-1)) `div` maxn + s = j*(denom*(t-s) + denom-1) `div` maxn + s = j*maxn `div` maxn + s = j+s sca(j*denom+denom-1) = ((j*denom+denom-1)*(t-s) + ((j*denom+denom-1)*(denom-1) `div` denom)) `div` maxn + s = ((j*denom+denom-1)*(t-s) + (j+1)*(denom-1)-1) `div` maxn + s = (j*maxn + (denom-1)*(t-s+1)) `div` maxn + s = j+s The required result then follows by the monotonicity property. In the most pathological case of maxn= 65535, s=0, t= 32768. We have denom = 1 and sca(n) becomes sc1(n), which, in this case, behaves very well. Thus the sca mapping is the optimal one. It is guaranteed to keep the result within the specified bounds at all times. When the perfect uniformity of mapping is possible, it is always achieved. The implementation isn't too complex either. > scaleSequence :: Int -> Int -> [Int] -> [Int] > scaleSequence s t > = map scale > where > scale n = (n*range + ((n*(denom-1)) `div` denom)) `div` maxn + s > range = t - s > maxn = modulus - 1 > modulus = 65536 > denom = (maxn+1) `div` (t-s+1) Main> any(>966) (scaleSequence 1 966 [0..65535]) False Main> any(==966) (scaleSequence 1 966 [0..65535]) True Main> any(>32768) (scaleSequence 0 32768 [0..65535]) False > test = let sq = [32768-1..32768+1600] in > let result = > map (\x -> let t = length x in (t `seq` t)) $! groupBy (\(a,_) (b,_) -> a == b) $! > sortBy (\(a,_) (b,_) -> compare a b) $! > zip (scaleSequence 0 32768 sq) $! sq > in (maximum $! result, minimum $! result) ==> (2,1) -- e.g., the mapping is roughly uniform

1 0

Re: updating labelled fields
by Hal Daume III 07 May '02

07 May '02

I just fudgeted around in the ghc source code and this doesn't seem to be a change that would require a lot of work. Briefly, the changes that would need to be made would be: 1) In the parser, change bind so that in addition to qname '=' exp you can also have qname 'somefunkysymbol' exp And change the return type from (a,b,Bool) to (a,b, Either () Bool) and then for the normal case, returh Right False and for the update case return Left (). 2) in the mkRecConstrOrUpdate function, when you have a conid applied to an update, make sure there are no Left () guys in the list; otoh, if the guy sitting in from of the { is an exp, do a map (mkRecUpdate exp) on the list where this function is something like: mkRecUpdate exp (a,b,Right c) = (a,b,c) mkRecUpdate exp (a,b,Left ()) = (a,HsApp b (HsApp (HsVar a) exp),False) -- warning, this isn't 100% correct, but it's the basic idea 3) recompile ghc I wouldn't at all mind making this addition if I had a sense that it would actually be accepted and that people weren't going to go crazy over the syntax. Would something like "<-" be preferred or something like "$=>"? - 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 On Tue, 7 May 2002, Bryn Humberstone wrote: > Hi Hal, > > > 2) update values in the structure, as in: > > let myData' = myData { foo = (foo myData)+1 } > > I do this a lot too, and think it would be lovely to have some sugar for > it. My original idea for the syntax was something like > myData = myData { foo $=> (+1), > bar $=> (*2) } > just because $ is a bit reminiscent of function application. But I'm not > really fussed; as long as some syntax for it appeared in the language. > > -- Bryn > > -- > Bryn Humberstone > + Email bdh(a)alphalink.com.au > + Web http://bryn.alphalink.com.au/ >

3 2

Re: Bug in the scaling of randoms ...
by oleg＠pobox.com 06 May '02

06 May '02

Dimitre Novatchev wrote on May 4, 2002: > In his excellent book Simon Thompson defines scaling of the elements of > a sequence of random numbers from the interval [0, 65535] to an > interval [s,t] in the following way (top of page 368): > > scaleSequence :: Int -> Int -> [Int] -> [Int] > > scaleSequence s t > > = map scale > > where > > scale n = n `div` denom + s > > range = t - s + 1 > > denom = modulus `div` range > > where modulus = 65536 > However, the following expression: > > e4000 = (scaleSequence 1 966 ([65231] ++ [1..965]))!!0 > evaluates to 974 -- clearly outside of the specified interval. Here's the algorithm for mapping of ranges of integers that is provably correct. We aim to find a function sc(n) defined over integers 0 <= n <= M so that sc(0) -> s (given integral number) sc(M) -> t (given integral number), t>=s and 0<=a < b ==> sc(a) <= sc(b) Such a function sc(n) is given by the following expression: sc(n) = (n*(t-s)) `div` M + s Proof: sc(0) = s sc(M) = (M*(t-s)) `div` M + s = t a<b ==> a*(t-s) < b*(t-s) ==> (a*(t-s)) `div` M <= (b*(t-s)) `div` M The assertion that 0<=a<b ==> a `div` M <= b `div` M for M >0 can easily be proven by contradiction. Indeed, given the facts (a `div` M)* M = a - ra, 0<= ra <= M-1 (b `div` M)* M = b - rb, 0<= rb <= M-1 and an assumption a `div` M > b `div` M we see a = M*(a `div` M) + ra = M*(b `div` M + x) + ra { where x >= 1 } = b - rb + ra + M*x >= min{ b - rb + ra + M*x over ra in [0,M-1], rb in [0,M-1]} >= b - (M-1) + M*x >= b + 1 + M*(x-1) { x >= 1 } > b {contradiction} Thus the correct algorithm reads > scaleSequence :: Int -> Int -> [Int] -> [Int] > scaleSequence s t > = map scale > where > scale n = (n*range) `div` maxn + s > range = t - s > maxn = modulus - 1 > modulus = 65536 Given your example, Main> any (==966) (scaleSequence 1 966 ([65231] ++ [1..965] ++[65565])) True Main> any (>966) (scaleSequence 1 966 ([65231] ++ [1..965] ++[65565])) False

2 1

Syntax highlighting for KDE's Kate
by Ralf Hinze 06 May '02

06 May '02

Dear KDE users, I've hacked syntax highlighting files for Kate, KDE's editor. Feel free to use or to modify them. http://www.informatik.uni-bonn.de/~ralf/software.html#syntax Cheers, Ralf

3 3

Re: finding sublist
by Shin-Cheng Mu 06 May '02

06 May '02

On Mon, May 06, 2002 at 09:30:02AM +0200, Ketil Z. Malde wrote: > "Garner, Robin" <Robin.Garner(a)crsrehab.gov.au> writes: > > See Dijkstra's 'Discipline of Programming' for an o(M + N) algorithm - naive > > approches are o(MN) where M and N are the length of the list and substring > > respectively. > > Essentially the algorithm calculates a sort of autocorrelation table of the > > substring, showing where to resume the search after a failed match. > There's also the KMP (Knuth, Morris, Pratt) algorithm, which is > similar. See Dan Gusfield: "Algorithms of strings, trees and > sequences" for lots of this stuff. About 13 years back there was also a paper talking about a formal derivation of such an algorithm in a functional language, based on an important property of fold and scan. R. S. Bird, J. Gibbons, and G. Jones. Formal derivation of a pattern matching algorithm. Science of Computer Programming, 12(2):93-104, July 1989. sincerely, Shin-Cheng Mu

1 0

CONFIDENTIAL
by MR ALI MWANANAGA. 06 May '02

06 May '02

CONFIDENTIAL FROM MR ALI MWANANAGA. Email; maubane_j(a)yahoo.co.uk REF: TRANSACTION REQEST. DEAR PARTNER. I am aware that it is amazing when a business proposal letter come From Some one that you Don"t know however, you address was to the consideration of your profile and i became aware of your credibility and co-operation in this transaction that would be profitable to both of us. I am Mr ALI Mwananaga. The son of Dr Nanapanga Mwananaga.Finance Minister of Democratic Republic of Congo(DRC),presently i am in the Netherlands on a senior Legal Management course. Recently I was contacted by my father over the issue am to explain.Dr Nanapanga Mwananaga was appointed the finance Minister in the government of president Laurent Desire Kabila of the Democratic Republic of congo(DRC),Being close friend and also old school mate of president Laurent Desire Kabila, make them have trust in each other. Early Last year,a contract was awarded to a foreign company in congo minig corporation on Diamond mining.Before the contract was awarded to the foreign firm,a required amount was Agreed upon and was paid by the contrecting company to ensure that it is their favour. The money paid was (US$15. 500.000.00 Million United State Dollars) and was paid to the then president kabila through his finance minister Dr Nanapanga Mwananaga. There after the whole money was de-faced to avoid being traced by their political rivals,and was moved out to the Netherland through diplomatic channel. Now the box containing the money is with a financial deposit company in the Netherlands. Deposited as photographic materials with out the deposit company knowing the exact contents of the box, because the entire money was intentionally de-faced out mint stage. The code to the deposited box and the certificate of deposit and all the transfer documents are still with my father in congo,which will be send as soon as a trusted confident partner is found. Unfortunately president Laurent Kabila whom my father had his arrangement with was attacked in his home town, by one of his own body guard, but did not survive.now that his son has succeeds him,l will want us to use this opportunity to move the money out from the Netherlands to another safe place you will provide.lf you accept this proposal and ready to corporate with out directives you will be rewarded with 25% of the total sum,All areas for the smooth transaction is already being taken care off. Be rest assured that this business will attract no risk.For more clarification,you are to use the above e-mail. Yours sincerely Mr ALI Mwananaga.

1 0

TERMGRAPH 2002 (2nd call for papers)
by Detlef Plump 06 May '02

06 May '02

======================================================================= Second Call for Papers TERMGRAPH 2002 International Workshop on Term Graph Rewriting Barcelona, Spain 7 October 2002 A satellite event of ICGT 2002 The First International Conference on Graph Transformation (http://www.lsi.upc.es/icgt2002/) ======================================================================= Background and Aims ------------------- Term graph rewriting is concerned with the representation of functional expressions as graphs and the evaluation of these expressions by rule-based graph transformation. Using graphs rather than strings or trees allows to share common subexpressions, which improves the efficiency of computations in space and time. Sharing is ubiquitous in implementations of functional and logic programming languages, systems for automated reasoning, and symbolic computation systems. Research in term graph rewriting ranges from theoretical questions to practical implementation issues. It includes such different lines as the modelling of (finite or infinitary) first-order term rewriting by (acyclic or cyclic) graph rewriting, rewrite rules on so-called sharing graphs for Levy-optimal reduction in the lambda calculus, rewrite calculi on cyclic higher-order term graphs for the semantics and analysis of functional programs, graph reduction implementations of functional programming languages, and automated reasoning and symbolic computation systems working on shared structures. The aim of this workshop is to bring together researchers working in these different domains and to foster their interaction, to provide a forum for presenting new ideas and work in progress, and to enable newcomers to learn about current activities in term graph rewriting. TERMGRAPH 2002 will be a one-day satellite event of the International Conference on Graph Transformation (ICGT 2002), which will take place October 8-11, 2002, in Barcelona. Topics of Interest ------------------ Topics of interest include all aspects of term graphs and sharing of common subexpressions in rewriting, programming, automated reasoning and symbolic computation. This includes (but is not limited to): * Theory of first-order and higher-order term graph rewriting * Graph rewriting in lambda calculus (sharing graphs, optimality) * Applications in functional, logic and functional-logic programming * Applications in automated reasoning and symbolic computation * Implementation issues * System descriptions Submissions ----------- Authors are invited to submit an extended abstract of 5 to 10 pages by e-mail to the program chair (det(a)cs.york.ac.uk) Submissions should be in PostScript format. It is strongly recommended to use LaTeX and ENTCS style files (http://math.tulane.edu/~entcs/) Publication ----------- Accepted contributions will appear in an issue of Elsevier's Electronic Notes in Theoretical Computer Science. Preliminary proceedings will be available at the workshop. Important Dates --------------- Submission deadline: June 15, 2002 Notification: July 15, 2002 Final version due: September 6, 2002 Workshop: October 7, 2002 ICGT 2002: October 8-11, 2002 Program Committee ----------------- Zena M. Ariola University of Oregon, Eugene (US) Richard Banach University of Manchester (UK) Rachid Echahed IMAG, Grenoble (FR) Richard Kennaway University of East Anglia, Norwich (UK) Jan Willem Klop Free University of Amsterdam (NL) Rinus Plasmeijer University of Nijmegen (NL) Detlef Plump University of York (UK), chair Contact ------- Dr. Detlef Plump Department of Computer Science The University of York Heslington, York YO10 5DD United Kingdom E-mail: det(a)cs.york.ac.uk Phone: +44-1904-434778 Fax: +44-1904-432767 Further Information ------------------- TERMGRAPH 2002: http://www.cs.york.ac.uk/~det/Termgraph_2002/cfp.html ICGT 2002: http://www.lsi.upc.es/icgt2002/

1 0