- Haskell-Cafe - Haskell.org

Assembling lists start-to-end
by Mark Carroll 21 Jun '03

21 Jun '03

I am assembling a list from start to end. I can add elements to the end with "previous ++ [current]" or I can add them with "current : previous" and reverse it when I'm done. Or, maybe I should use some other data structure. (I don't know the length in advance.) Any thoughts? -- Mark

3 2

RE: Help: Stack-overflow and tail-recursive functions
by Hal Daume 21 Jun '03

21 Jun '03

> GHCi didn't have any problem even with the original code. mine didn't either, until I increased the "200" to around "1500"...it's probably OS/memory specific.

2 1

Help: Stack-overflow and tail-recursive functions
by Koji Nakahara 20 Jun '03

20 Jun '03

Hi I've written a function that is tail-recursive and takes a list(queue) as one of its arguments. However the function fails because of "Stack space overflow"(GHC) or "ERROR - Garbage collection fails to reclaim sufficient space"(hugs). For example (simplified), both of these results in stack-overflow: f1 100000 [0,1,2], and even f2 100000 [0,1,2], where, f1 0 l = l f1 n l = f (n-1) $ take 3 $ l ++ [0,1] f2 0 l = l f2 n l = f2 (n - 1) $! (take 3 $ l ++ [0,1]) Why f2 overflows? How to avoid this stack-overflow?

1 1

Re: Help: Stack-overflow and tail-recursive functions
by oleg＠pobox.com 20 Jun '03

20 Jun '03

It seems the problem is indeed in rmat: > rmat n = listArray ((1,1),(n,n)) $ map ct (randoms (mkStdGen 1) ::[Bool]) > where ct True = Unknown > ct False = Dead To be more precise, the problem is in randoms. If you replace rmat with the following rmat n = array ((1,1),(n,n)) $ zipWith (\ind v -> v `seq` (ind,v)) [(i,j) | i<-range, j<-range] $ map ct (randoms (mkStdGen 1) ::[Bool]) where ct True = Unknown ct False = Dead range = [1..n] then > main = putStrLn $ show $ forpaintbdry $ rmat 400 computes without problems (compiled with GHC 5.04.1, no flags). BTW, GHCi didn't have any problem even with the original code.

1 0

RE: Help: Stack-overflow and tail-recursive functions
by Hal Daume 19 Jun '03

19 Jun '03

The problem here is actually in the rmat function, not the forpaintbdry or whatever. The problem is that, afaik, the listArray function doesn't deforest the list argument (someone can correct me here, though). That is, you write: rmat n = listArray ... [a big list] and then this list is first built, then the array is filled in. You can see that this is a problem by replacing your main with: main = print (m ! snd (bounds m)) where m = rmat 800 This will stack overflow too. Solution: use mutable arrays and fill them in by hand :). -- Hal Daume III | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume > -----Original Message----- > From: Koji Nakahara [mailto:yu-@div.club.ne.jp] > Sent: Wednesday, June 18, 2003 7:41 PM > To: Hal Daume; haskell-cafe(a)haskell.org > Subject: Re: Help: Stack-overflow and tail-recursive functions > > > On Wed, 18 Jun 2003 17:36:28 -0700 > "Hal Daume" <t-hald(a)microsoft.com> wrote: > > > Note that there is essentially no difference between f1 and > f2. When > > you $! in f2, all it does is ensure that the argument isn't > undefined. > > It doesn't evaluate any of the list. Try $!! from the > DeepSeq module or > > write your own list-forcing function. > > Thank you very much. I understand. > > However my original program still (or maybe from the > beginning) stack-overflows > at another point, in the middle of the evaluation of "forpaintbdry". > > Please give me some advice. > ----------- > -- snippet of the program for painting a random matrix from > its boundary. > module Main where > import System > import Random > import Array > import Ix > import List > > main = putStrLn $ show $ forpaintbdry $ rmat 200 > > forpaintbdry m = [(pos, Live) | pos <- (uncurry bdryidxlist) > $ bounds m , isUnknown $ m ! pos ] > > bdryidxlist :: (Int, Int) -> (Int, Int) -> [(Int, Int)] > bdryidxlist (a1, a2) (b1, b2) = nub $ [(ab, j) | ab <- [a1, > b1], j <- [a2..b2]] ++ > [(i, ab) | ab <- [a2, b2], i <- > [a1..b1]] > > rmat n = listArray ((1,1),(n,n)) $ map ct (randoms > (mkStdGen 1) ::[Bool]) > where ct True = Unknown > ct False = Dead > > data CellColor = Live | Unknown | Dead > > isUnknown Unknown = True > isUnknown _ = False > > instance Show CellColor where > show Live = "Live" > show Unknown = "Unknown" > show Dead = "Dead" > >

1 0

RE: Help: Stack-overflow and tail-recursive functions
by Hal Daume 19 Jun '03

19 Jun '03

Note that there is essentially no difference between f1 and f2. When you $! in f2, all it does is ensure that the argument isn't undefined. It doesn't evaluate any of the list. Try $!! from the DeepSeq module or write your own list-forcing function. For me, the following works: f1 0 l = l f1 n l = f1 (n-1) $!! (take 3 $ l ++ [0,1]) f $!! x = force x `seq` f x where force [] = () force (x:xs) = x `seq` force xs whereas it doesn't without the $!!. -- Hal Daume III | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume > -----Original Message----- > From: haskell-cafe-admin(a)haskell.org > [mailto:haskell-cafe-admin@haskell.org] On Behalf Of Koji Nakahara > Sent: Wednesday, June 18, 2003 5:18 PM > To: haskell-cafe(a)haskell.org > Subject: Help: Stack-overflow and tail-recursive functions > > > Hi > > I've written a function that is tail-recursive and takes > a list(queue) as one of its arguments. > However the function fails because of > "Stack space overflow"(GHC) or "ERROR - Garbage collection > fails to reclaim sufficient space"(hugs). > > For example (simplified), both of these results in > stack-overflow: f1 100000 [0,1,2], and even f2 100000 [0,1,2], > > where, > f1 0 l = l > f1 n l = f (n-1) $ take 3 $ l ++ [0,1] > > f2 0 l = l > f2 n l = f2 (n - 1) $! (take 3 $ l ++ [0,1]) > > Why f2 overflows? > > How to avoid this stack-overflow? > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskel> l-cafe >

2 1

Re: Type classes and code generation
by Keith Wansbrough 17 Jun '03

17 Jun '03

> You need to change the first line to this: > > > data C a = C { pair :: forall b. b -> (b,a) } > > and then it works fine (with -fglasgow-exts). But you've now stepped > outside the bounds of Haskell 98. (oops, replying to myself... sure sign of madness! :) ) I hasten to add that this is *not* the same as existential quantification; note carefully the location of the forall wrt the constructor. --KW 8-) -- Keith Wansbrough <kw217(a)cl.cam.ac.uk> http://www.cl.cam.ac.uk/users/kw217/ University of Cambridge Computer Laboratory.

1 0

Re: Type classes and code generation
by Hal Daume III 17 Jun '03

17 Jun '03

(Moved to the Cafe) > Yes, exactly. Every class is translated to a data type declaration, > and every instance is translated to an element of that data type - a > dictionary. (Note that you can't actually write those declarations in > Haskell 98 in general, because they can have polymorphic fields; but > this is a simple extension to the language). Keith, could you elaborate on this parenthetical? Under what circumstances can you not create the dictionary datatype for a class in Haskell 98 (where the class itself is H98 :P)? - Hal

2 1

Protect your privacy
by Software Promote Center 17 Jun '03

17 Jun '03

Hi, Our product can protect your privacy. http://www.linren.com Your computer is spying on you now! It stores all the evidence into your hard disk. Anyone using your computer can see where you have been on Internet, what images and movies you have seen, and even anything you have done on your computer could be seen by others. The Windows built-in functions will not protect you, most of the tracks can not be erased with them. Privacy Cleaner Pro is designed to protect you by cleaning up all the unwanted history data on your computer. With simply one click, Privacy Cleaner Pro allows you to erase the cache, cookies,history,typed URLs,autocomplete memory from your browsers, and Window's temp folder,run history, search history, open/save history, recent documents,etc. With Privacy Cleaner Pro, you can easily erase the tracks of applications,such as playlist of Realplayer, Mediaplayer, QuickTime,recent files of Office, Acrobat ,Winzip,etc.Privacy Cleaner Pro can also let you customize what file(s) to be erased With Privacy Cleaner Pro's Securely Cleaning feature, you can erase the files completely, which can not be recovered by others. For more information go to: http://www.linren.com Best Regards, Software Promote Center

1 0

Please contact me
by Joseph Makale 16 Jun '03

16 Jun '03

MR. JOSEPH MAKALE DEPARTMENT OF MINERALS AND ENERGY PRETORIA, SOUTH AFRICA. JUNE16TH., 2003 Sir, It is my great pleasure to write you this letter on behalf of my colleagues. Your information was given to me by a member of the South African Export Promotion Council (SAEPC) who was with the Government delegation on a trip to your country for a United Nations bilateral conference talk on sustainable development to encourage foreign investors. I have decided to seek a confidential co-operation with you in the execution of a deal here-under for the benefit of all parties and hope you will keep it confidential because of the nature of the business. Within the Department of Minerals and Energy where I work as an assistant Director of Audit, with the co-operation of two other top officials, we have in our possession an overdue contractor payment in US Dollars funds. The said funds represent certain percentage of the contract value executed on behalf of my Department by a foreign contracting firm, (Pearls Ltd) which we the officials over-invoiced to the amount of US$15,200,000 (Fifteen Million Two Hundred Thousand US Dollars). Since the present elected Government is determined to pay foreign contractors all debts owed, so as to maintain good relations with foreign governments and non-governmental agencies, we included our bills for approvals with the Department of Finance and the Reserve Bank of South Africa (RBSA). We are 100+% sure of funds approvals to anyone or company we (The Audit Committee) recommend as part of the sub-contractors who did jobs for the Department. We are seeking your assistance to front as the sub-contractor of the unclaimed funds, since we are not allowed to operate foreign accounts. Details and change of beneficiary information upon application for claim to reflect payment and approvals will be secured on behalf of You/your Company. My colleagues and I are prepared to give you US$2.5m while we take US$7.4m and the balance of US$5.3m for taxes and miscellaneous expenses incurred. This business is completely safe and secure, provided you treat it with utmost confidentiality. It does not matter whether You/your Company does contract projects, as a transfer of rights will be secured in favor of You/your Company through the Federal high Court of South Africa before we can proceed. I have reposed my confidence in you and hope that you will not disappoint us. Kindly notify me immediately for further details upon your acceptance of this proposal. You can contact me by email. Yours Faithfully, Joseph Makale (Mr.)

1 0