- Haskell-Cafe - Haskell.org

Using an accumulator, "iterating"...
by Brett Kelly 21 Jun '03

21 Jun '03

Hello all, I'm trying to write a function that takes a list and a element (same type) and returns the index of the first instance of the element in the list. like: getindex "brett" 'e' would return 2, etc. i'm trying to accomplish this using an accumulator, here's what i've got: pyindex :: Eq a => a -> [a] -> Maybe Int pyindex c l = pyindex' 0 chr (x:xs) where pyindex' count chr (x:xs) = do if x == chr then return count else pyindex' (count + 1) chr xs now, i know i've got a syntax problem, because i'm pretty sure my logic is correct (or at least MOSTLY correct). can anybody see what's wrong with my stuff? thanks! -- Brett Kelly bkelly(a)sourcereview.net This message has been digitally autographed using GnuPG. Vim - this ain't your daddy's text editor http://www.vim.org

5 6

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