- Haskell - Haskell.org

stack space overflow
by ketil＠ii.uib.no 20 Jun '03

20 Jun '03

Hi, I have a small function to find all indices in an array where a given subword can be found, looking like this: > ind i ws ar > | i+length ws-1 > len e = [] > | and [ar!(i+j) == ws!!j | j<-[0..length ws-1]] = i : ind (i+1) ws ar > | otherwise = ind (i+1) ws ar (i::Int is the position, ws::[a] is the word to look for, while ar::Array Int a is the array wherein to look) This occasionally blows up with a stack overflow, perhaps I'm being dense, but I'm not sure why. Any suggestions? BTW, is there a general way to track down stack overflows? I use the -xc option, are there any other tricks I should know about? And does heap profiling (GHC) imply more stack usage -- I seem to get overflows much more easily when profiling. -kzm -- If I haven't seen further, it is by standing in the footprints of giants

1 0

In search of: [a->b] -> a -> [b]
by Graham Klyne 20 Jun '03

20 Jun '03

I'm convinced I've seen a function like this somewhere: [a->b] -> a -> [b] but cannot remember where. Or maybe: Monad m => m (a->b) -> a -> m b ? I could roll my own (*), but I'm trying not to duplicate standard library functions is I can help it. Any pointers? #g -- (*) flist :: [a->b] -> a -> [b] flist fs a = map (flip ($) a) fs flist [(1*),(2*),(3*)] 5 -- = [5,10,15] ------------------- Graham Klyne <GK(a)NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E

7 8

RE: Array + memory usage
by Hal Daume 19 Jun '03

19 Jun '03

Someone else already replied with much information. I figured I'd try to add a small amount. Basically, to clarify, the problem is that at every character you read, you do something like 'arr // list'. (//) is *not* an O(1) operation as you might expect. In fact, it *copies* the entire array. Why? Because if you later reference the old one, it needs to have a "backup" version. The solution, if you want to use arrays, is basically to use a mutable state array, like IO(U)Array or ST(U)Array. However, you might be better off using a different data structure. An easy solution would be to use a finite map from Data.FiniteMap. You'll incur a little overhead, but then again, the distribution of letters in natural language text is anything but flat; some you will likely never see and you're wasting space in your array for these. Of course, you could use a more informed coding tree based on letter distributions, but this is probably overkill. -- Hal Daume III | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume > -----Original Message----- > From: haskell-admin(a)haskell.org > [mailto:haskell-admin@haskell.org] On Behalf Of mies > Sent: Thursday, June 19, 2003 2:11 AM > To: haskell(a)haskell.org > Subject: Array + memory usage > > > Hello, i'm a haskell newbie, and i'm trying to use arrays for > counting > letters. But when I input a textfile of lets say 100KB the > program uses > 75 M of memory, and I really don;t have a clue where the > problem could > be. I have searched many topics here but I didn't find a solution. I > have made an axample of how i am using the array. > > module Main where > > import Array > import IO > > main = do let fr = testUpdater f 100000 > writeFile "test.txt" (show (fr!155)) > > f :: Array Int Int > f = (array (0,255) [(i, 0) | i <- [0..255]]) > > testUpdater :: Array Int Int -> Int -> Array Int Int > testUpdater fr 0 = fr testUpdater fr x = testUpdater > ((fr//[(155, fr!(155) + 1)])) (x - 1) > > updateF :: Array Int Int -> Array Int Int > updateF x = (x//[(155, x!(155) + 1)]) > > Regards, Richard Nieuwenhuis > rnieuwen(a)cs.uu.nl > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell >

1 0

Array + memory usage
by mies 19 Jun '03

19 Jun '03

Hello, i'm a haskell newbie, and i'm trying to use arrays for counting letters. But when I input a textfile of lets say 100KB the program uses 75 M of memory, and I really don;t have a clue where the problem could be. I have searched many topics here but I didn't find a solution. I have made an axample of how i am using the array. module Main where import Array import IO main = do let fr = testUpdater f 100000 writeFile "test.txt" (show (fr!155)) f :: Array Int Int f = (array (0,255) [(i, 0) | i <- [0..255]]) testUpdater :: Array Int Int -> Int -> Array Int Int testUpdater fr 0 = fr testUpdater fr x = testUpdater ((fr//[(155, fr!(155) + 1)])) (x - 1) updateF :: Array Int Int -> Array Int Int updateF x = (x//[(155, x!(155) + 1)]) Regards, Richard Nieuwenhuis rnieuwen(a)cs.uu.nl

2 1

Re: Typesafe MRef's
by oleg＠pobox.com 19 Jun '03

19 Jun '03

> So what does the function > insert2 val1 val2 = > let > (m1,k1) = insert empty (Just val1) > (m2,k2) = insert m1 (Just val2) > m3 = update m2 k1 Nothing > in > isJust (lookup m3 k2) > return? It looks to me as if it returns True if val1 and val2 have > different types, False if they have the same type. Sorry for the delay: I was out of town. Using the Haskell98 implementation of typesafe MRef posted earlier, the insert2 function always returns True. To be more precise, the following function, insert2 val1 val2 = let (m1,k1) = insert empty () [val1] (m2,k2) = insert m1 () [val2] m3 = update m2 k1 [] in isJust (lookp m3 k2) re-written to conform to Simon Peyton-Jones' signature (modulo renaming of lookup into lookp) and to use lists rather than Maybes. The universe in the posted code had no maybes, due to my laziness. The function continues to always return True even if we replace the update statement above with m3 = update m2 k2 [] The former result is obvious from the fact that keys k1 and k2 indeed refer to different "cells" so to speak (at least in the posted implementation of the Simon Peyton-Jones' signature). Therefore, updating the cell referred to by k1 has no bearing on the cell referred to by k2.

1 0

ICFP Programming Contest
by John Hughes 18 Jun '03

18 Jun '03

ICFP Programming Contest ======================== There are just ten days to go to the sixth ICFP Programming Contest! Starting at midnight on Saturday morning, June 28th, you can prove once again that your favourite programming language is "the programming tool of choice for discriminating hackers!" Don't miss this opportunity -- check out the contest web site at http://icfpcontest.org for details -- and the tiniest little hint of this year's problem. John Hughes

2 1

Threads
by Filip 17 Jun '03

17 Jun '03

Hi, I have function f:: a -> b and I need something like this: myaccept:: Socket -> IO () myaccept g = do a <- accept g t <- forkIO (f a) myaccept g What to do to have two threads working at the same time. When I am using myaccept, program is suspending. Thanks.

3 2

RE: Type classes and code generation
by Bayley, Alistair 17 Jun '03

17 Jun '03

> > Is there > > some way of preventing the type mechanism from generating > code for the > > instance type, as opposed to the class? > > I don't understand this question - does the explanation above help? I could have been clearer with my questions. What I was wondering was: is there some situation where the compiler can't statically determine the type to be used? > The function "double" will work on any type in the class Num, so the > compiler can't know which "+" function to use. When it's applied, the compiler will know the types of the arguments, won't it?. Which means that you would generate a version of double for each (applied) instance of Num. I don't doubt that there's a good reason this is not done: code bloat? or are there simply some expressions that can't be statically resolved? I suppose I was thinking: is the language design sufficiently clever that it's *always* possible for the compiler to infer the type instance in use, or are there some situations where it's not possible to infer the instance, so some kind of function dispatch mechanism is necessary? > Yes, roughly. In Haskell, the compiler always figures out > the types of > everything at compile time. This means it can often figure out which > bit of code to use at compile time as well - but because of > polymorphism, not always. Consider this bit of code: > > double :: Num a => a -> a > double x = x + x > > The function "double" will work on any type in the class Num, so the > compiler can't know which "+" function to use. But it *doesn't* solve > this by run-time dispatch, like in C++. Instead, it compiles double > like this: > > double' :: NumDict a -> a -> a > double' d x = let f = plus d > in x `f` x > > where NumDict is a record a bit like this: > > data NumDict a = NumDict { plus :: a -> a -> a, > minus :: a -> a -> a, > fromInteger :: Integer -> a > ... > } > > NumDict is called a "dictionary", and any time double' is called, the > caller must supply the right dictionary. If you write > > double 2.0 > > then the compiler sees that you've written a Double, and so supplies > the NumDict Double dictionary: > > double' doubleNum 2.0 > > where doubleNum :: NumDict Double contains the methods for adding > Doubles, subtracting them, and converting from Integers to them. This looks like a dispatching mechanism to me. However, I think I see that this can still be done at compile-time. When double is applied to 2.0, the compiler generates the double' doubleNum 2.0 code, which is still statically resolvable. The advantage seems to be that you don't generate a double function for each Num instance. Does this also mean that a dictionary class is created for every class, and a dictionary created for every instance? > Getting back to your original question, there's a little subtlety in > Haskell to do with literals. Whenever you type an integer > literal like "2", what the compiler actually sees is "fromInteger 2". > Another little subtlety called "defaulting" (see > the Haskell 98 Report, in section 4.3.4) arranges that in this I knew about the "fromInteger" and similar treatment of literals, but the defaulting system is news to me. I've skimmed over the Haskell report, but details like this never sink in until you encounter them in practice... > Instance exporting is not easy to control in Haskell; if you export a > type, then all its instances are exported along with it automatically. Thanks. I wasn't sure how the export mechanism worked with regard to classes and instances; I just took a (wrong) guess that you could control export of classes and types separately. ***************************************************************** The information in this email and in any attachments is confidential and intended solely for the attention and use of the named addressee(s). This information may be subject to legal professional or other privilege or may otherwise be protected by work product immunity or other legal rules. It must not be disclosed to any person without our authority. If you are not the intended recipient, or a person responsible for delivering it to the intended recipient, you are not authorised to and must not disclose, copy, distribute, or retain this message or any part of it. *****************************************************************

3 2

C++ class structure mapping
by Abraham Egnor 17 Jun '03

17 Jun '03

I'd like to make a haskell binding for a C++ library. Most of the tools out there seem oriented towards c bindings, so it looks like I'll be writing the FFI code generator myself. While I'm at it I figure I might as well just make a general C++ binding tool. I've been thinking about this, and I'd like some feedback on the ideas I've had. First - it seems natural to use template haskell to do the code generation. That way, the library could either write the generated code to a file using the pretty-printers, or just be spliced in directly. Now comes the question of how to map a C++ class hierarchy into haskell. It seems natural to try to map C++ classes into haskell typeclasses; however, there are a few issues involved with that. A separate datatype would have to be made for each C++ class to allow it to actually be instantiated, which isn't too bad. However, to allow haskell instances of the typeclass to call the old behavior it seems that there'd have to be duplicate functions of the ones in the typeclass, i.e. class A a where foo :: a -> IO () foo_cpp :: (A a) => a -> IO () That seems to be needed to allow haskell instances to call the old implementation in their definition, but it rubs me the wrong way. Can anyone suggest an alternate method, or suggest a different direction entirely? Abe

4 3

Type classes and code generation
by Bayley, Alistair 17 Jun '03

17 Jun '03

I had a discussion with someone over the type class mechanism and would like to clarify something. When I compile this trivial program: > module Main where > main = putStrLn (show (1 + 2)) with ghc -Wall, the compiler says: Main.lhs:3: Warning: Defaulting the following constraint(s) to type `Integer' `Num a' arising from the literal `2' at Main.lhs:3 This implies to me that the compiler is generating the code for (+) for the particular instance, rather than using a run-time dispatch mechanism to select the correct (+) function. Is this correct, or am I way off? Does the compiler *always* know what the actual instances being used are? Is there some way of preventing the type mechanism from generating code for the instance type, as opposed to the class? If I am correct, does it work the same way across module boundaries? (I would think so.) If a module exports a class but no instances for that class, then a user of that class would have to install their own instances. OTOH, if the class plus one or more instances were exported, then a user could use the supplied instance types, and the compiler would still generate code to use the specific instances. ***************************************************************** The information in this email and in any attachments is confidential and intended solely for the attention and use of the named addressee(s). This information may be subject to legal professional or other privilege or may otherwise be protected by work product immunity or other legal rules. It must not be disclosed to any person without our authority. If you are not the intended recipient, or a person responsible for delivering it to the intended recipient, you are not authorised to and must not disclose, copy, distribute, or retain this message or any part of it. *****************************************************************

3 2