- Haskell - Haskell.org

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

06 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 06 May '02

06 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

RE: Deforestration harmful?
by Simon Marlow 06 May '02

06 May '02

> 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? It is entirely plausible that as you increase the heap size the mutator time increases: this is because you get fewer cache hits with a larger heap. GHC starts off with a small heap size so as to try to make the most of the cache. However, on most examples we've seen the benefits of reducing garbage collections by increasing the heap size tend to outweigh the benefits from staying in the cache. Did you try heap profiling to discover what structure was filling up the heap? Cheers, Simon

1 0

RE: finding sublist
by Garner, Robin 06 May '02

06 May '02

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. For example, if you're matching the substring [1,2,3,4], and fail on the last comparison, you already know that there's no point in advancing one element and attempting another match - you can actually start again at the element that failed. When matching the string [1,2,1,3], you can resume at the current element of the main string, and the second element of the search string. How you would do this in a functional implementation is another question - Dijkstra's example is comparing two arrays, and there may be inefficiencies translating it to a list-based implementation. Cheers -----Original Message----- From: Serge D. Mechveliani [mailto:mechvel@botik.ru] Sent: Thursday, 2 May 2002 17:37 To: haskell(a)haskell.org Subject: finding sublist Thanks to people who helped me with the task >> Import two space separated columns of integers from file. Claus Reinke <claus.reinke(a)talk21.com> recommends to exploit `lines'. Indeed, it bocomes shorter now: main = readFile "data" >>= (putStr . show . twoIntLists) where twoIntLists str = case span (not . null) $ dropWhile null $ lines str of (lns, lns') -> (readInts lns, readInts lns') readInts = map (\ str -> read str :: Integer) . dropWhile null Another question: has the Haskell Standard library a function for such a usable task as finding of occurence of a segment in a list? Say findSegmentBy (...) [2,2,3] [0,0,2,2,1,2,2,3,1,2,3] --> ([0,0,2,2,1], [2,2,3,1,2,3]) I have heard, an efficient algorithm (for large lists) for this is not so simple. ----------------- Serge Mechveliani mechvel(a)botik.ru _______________________________________________ Haskell mailing list Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell

4 4

(no subject)
by timeismonie＠btamail.net.cn 06 May '02

06 May '02

SPECIAL SITUATION ALERTS NEWSLETTER HOT PICK OF THE YEAR Environmental Remediation Holding Corp. (d.b.a. Chrome Energy Corp) (OTCBB: ERHC) RECENT PRICE: $.20 SELL TARGET: $1.25 INVESTORS: WE HAVE FOUND THE HIDDEN GEM: (OTCBB: ERHC) The IMF (International Monetary Fund) states in a worldwide published report [February 2002 IMF Country Report No. 02/30 (page 10 of 82)] that ERHC's working interest in their offshore West African oil blocks will generate $1,446,800,000 in cumulative income over the next 22 years. The IMF provides this evaluation to its 183 Member Nations while promoting international monetary exchange and fostering economic trade and growth with an arsenal of $272 Billion! Dow Jones News: ERHC enters into joint-venture license agreements with Schlumberger LTD (NYSE: SLB, $53) and Baker Hughes, INC. (NYSE: BHI, $34) for seismic data on some of the richest offshore oil blocks in West Africa, where ERHC controls a huge working interest. Investor Alert: ERHC's joint-venture with SCHLUMBERGER and BAKER HUGHES puts them in world class company with these leaders in oil exploration and reservoir imaging services. The involvement of SLB and BHI reinforces the MULTI-BILLION DOLLAR VALUE that has been placed in this offshore drilling haven. ERHC's goal is to maximize shareholder value from existing contractual rights, making them a significant player in this region. THE BIG MONEY ROLLS IN: The seismic data from this joint venture is being made available for further involvement by the LARGEST OIL COMPANIES IN THE WORLD over the next 2 weeks! Bidding wars have already developed between major oil companies such as: SHELL, CHEVRON/TEXACO, CONOCO, EXXON/MOBIL, PHILIPS, and MARATHON who are willing to pay Hundreds of Millions to drill in the oil blocks that border on ERHC's offshore zones. STOCK SET TO EXPLODE ON EARNINGS BOOM: "UPSTREAM", the International Oil and Gas Newspaper considered to be the equivalent of the "Wall Street Journal" for the Oil Industry, has stated in a number of articles that EXXON/MOBIL believes that the oil blocks "housing ERHC's working interest" contain over 8 BILLION BARRELS OF RECOVERABLE OIL TAKEOVERS RUNNING RAMPANT: Oil Companies of all sizes have been the target of significant mergers and takeovers during the past year. Many of these takeovers or buyouts have occurred due to the value of the acquired Company's offshore oil holdings in West Africa. One such example is Marathon Oil (NYSE: MRO, $28) paying $900 MILLION for the West African holdings of CMS Energy (NYSE: CMS, $23). We believe that ERHC and/or the Company's offshore oil interests could be the next target of a takeover. This is largely because of their exclusive right to participate in exploration and production along with OIL INDUSTRY GIANTS, as these oil blocks are adjacent to Billion Barrel producing regions! Global Stock Participation - On March 27, 2002--Chrome Energy Corporation ("Chrome") (OTCBB:ERHC), announced that its common stock has been approved for listing on the Berlin Stock Exchange in Germany. The Berlin Stock Exchange is the leading stock exchange in Europe for dual listings with over 6,000 American companies listed. Chrome's common stock began trading on March 28, 2002 Special Situation Alerts' Newsletter offers valuable research for serious investors with our Hot Pick Of The Year - ERHC This is a commercial email only and if you want to be removed email timeismonie(a)btamail.net.cn

1 0