- Haskell-Cafe - Haskell.org

Re: Counting recursive calls
by John Hughes 13 Nov '01

13 Nov '01

Hi all, got some questions on recursive functions. I got a simple recursive function (f3) In *some* situations I'll want to know how many recursive calls did it make. I came up with two simple implementations to do that (f1) and (f2) f [] w = (w,0) f (x:xs) w = (nextw, steps+1) where (nextw, steps) = f xs (g x w) f2 [] k w = (w,k) f2 (x:xs) k w = f2 xs (k+1) (g x w) f3 [] w = w f3 (x:xs) w = f3 xs (g x w) ... Anyway like I said I don't *always* want to know the n. of steps, so I could chose either to: - use 2 different functions, one when I want the n. of steps (f or f2) another one when I don't need it (f3) - use just one function (f or f2) if I don't need the n. of steps, use fst. The second choice seemed to make more sense to me. Lazy evaluation should do the trick, and the n. of steps would not have to be evaluated, so efficiency-wise it would be the same as calling f3. Oh oh --- lazy evaluation isn't what you want here! Certainly it will avoid *computing* the number of steps, but it will do so by building up a gigantic unevaluated closure of the form (((((((((0+1)+1)+1)+1)+1)+1)+1)+1)+1). So you'll be using memory linear in the running time -- not good. Moreover, when you finally come to evaluate that closure, you'll need a *huge* stack to do it on. ... [2] Any tips on which function(s) should I choose, or any way to make them more efficient. Most efficient will be to force strict evaluation of the count. In GHC you can do that by using an unboxed integer. ----- (**) would I get a different behavior if I had compiled the program. I've had some problems when trying to compile and use getCPUTime. Some stack overflows for big values of w, and for smaller values 0 in the execution time... I'll try to figure out what I'm doing wrong here... What did I say about the stack? If you compile your code, and especially if you use an unboxed integer as I suggest, then the cost for counting steps should be very low. In particular, it will certainly be cheaper to *compute* k+1 (single unboxed addition) than to build a suspension for it (memory allocation). You might get a different result in the interpreter, because of all the interpretation overhead, but in compiled code there should be no question about it. John

3 2

RE: Here is a tiny idea for a QT based GUI library
by Simon Marlow 13 Nov '01

13 Nov '01

> -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > On Tuesday 13 November 2001 06:18, Manuel M. T. Chakravarty wrote: > > The time consuming part in creating such a system are the C > > bindings, not the XML stuff. In fact, similar functionality > > is available for GTK+ already for a long while. The cool > > point about it is that the graphical interface builder Glade > > > > http://glade.gnome.org/ > > > > can generate these XML files, which you just load into your > > application using a library called libglade (that > > corresponds to the QWidgetFactory that you mention above). > > I guess, KDE's interface builder can do the same. > > > > Yes, I know. I used to be a poor GTK+ coder myself. :) I'm a konvert. > > The C bindings are already available, so you can just use > them it seems. The point Manuel was making is that it takes a lot of time & effort to code up the Haskell binding to the C libraries. Just having a way to load up the interface from the XML spec isn't enough - you need a complete enough binding to be able to manipulate the interface from Haskell at run time. This is not a GTK vs. Qt argument. We *have* most of a GTK+ binding and it would be a shame to divide our efforts when said efforts are in short supply. When we have one complete GUI binding, then let's think about making another one. Cheers, Simon

2 1

Having contraints like 'Fractional Int => IO ()'
by Jesper Louis Andersen 13 Nov '01

13 Nov '01

This problem has had my attention for a while now. I hope someone would like to help me out on the problem. I have a simple average function defined as: mean :: (Fractional a) => [a] -> a mean l = (sum l)/ fromIntegral (length l) Which imposes a type constraint (of course). My problem is, that i cannot ``let go'' of this constraint. The constraint travels through the call tree of my functions and ends at the top-level function, which is defined as a Monad (I need some IO operations on some files). Now, I have tried to solve the problem, but the closest I have got is to make my main function be of type: main :: Fractional Int => IO () But that is not something that Hugs likes as it tells me that I have a ``unresolved overloading'' at the expression ``main'' on the type. So... Is there a way to get rid of the constraint by converting the function to something more sensible. I seem to have missed a point here, as I have migrated from Standard ML to Haskell (the latter being a far more complicated language it seems). As SML doesn't have type classes, they seem to have bitten me hard. If anyone could point to the relevant information, it would be very nice. Thanks in advance -- Jesper

3 2

Re: Having contraints like 'Fractional Int => IO ()'
by Ashley Yakeley 13 Nov '01

13 Nov '01

At 2001-11-12 18:06, Jesper Louis Andersen wrote: >mean :: (Fractional a) => [a] -> a >mean l = (sum l)/ fromIntegral (length l) > >Which imposes a type constraint (of course). My problem is, that i >cannot ``let go'' of this constraint. ... >main :: Fractional Int => IO () It sounds like you're trying to use your 'mean' function on Ints. Int is not a Fractional type (unless you make it one), and so '/' isn't defined on it. What's "mean [3::Int,4::Int]"? It can't be "3.5::Int" because 3.5 is not an integer and so not an Int. -- Ashley Yakeley, Seattle WA

1 0

Haskell coding environment for windows users?
by Srineet 13 Nov '01

13 Nov '01

Hi, I am not sure whether this is the right place to ask this question. I want to know what's the Haskell coding environment used by GHC users on windows? What 's the preferred editor? Is there any Haskell tags for vim? Also, is there any program which will convert Haskell modules to HTML with cross-links so that one can use the HTML files to browse the source? Please let me know. Thanks. Bye. - Srineet.

3 2

Counting recursive calls
by Jorge Adriano 11 Nov '01

11 Nov '01

Hi all, got some questions on recursive functions. I got a simple recursive function (f3) In *some* situations I'll want to know how many recursive calls did it make. I came up with two simple implementations to do that (f1) and (f2) f [] w = (w,0) f (x:xs) w = (nextw, steps+1) where (nextw, steps) = f xs (g x w) f2 [] k w = (w,k) f2 (x:xs) k w = f2 xs (k+1) (g x w) f3 [] w = w f3 (x:xs) w = f3 xs (g x w) It's easy to see that f xs = f2 xs 0 fst (f xs w) = fst(f2 xs 0 w) = f3 xs w Even though f looks better, I'd say f2 is more efficient as it uses an accumulation process to calculate the number of steps - tested it in ghci and seems like I was right. Anyway like I said I don't *always* want to know the n. of steps, so I could chose either to: - use 2 different functions, one when I want the n. of steps (f or f2) another one when I don't need it (f3) - use just one function (f or f2) if I don't need the n. of steps, use fst. The second choice seemed to make more sense to me. Lazy evaluation should do the trick, and the n. of steps would not have to be evaluated, so efficiency-wise it would be the same as calling f3. I have tested this functions in ghci with g = (+) -------------------------------------- Main> f [0..100000] 0 (5000050000,100001) (3.65 secs, 20702676 bytes) Main> f2 [0..100000] 0 0 (5000050000,100001) (3.15 secs, 14718856 bytes) Main> fst (f [0..100000] 0) 5000050000 (2.04 secs, 18720784 bytes) Main> fst (f2 [0..100000] 0 0) 5000050000 (2.36 secs, 13372372 bytes) Main> f3 [0..100000] 0 5000050000 (1.90 secs, 10315336 bytes) ------------------------------------- (**) So, - f3 is better then f and f2, if I don't need the n. of steps. - f2 is better then if if I want the n. of steps. - f is better then f2 if I don't want the n. of steps. Now what I want: [1] I would appreciate if someone could explain this behavior. I tried simulating what this functions do, and see if by using 'fst' they will, or will not, need to evaluate the n. of steps. (obviously it is not that simple, because fst always makes some difference, more in f than f2) I have some ideas that might explain what is happening, but I since I still do not feel confortable with this sort of efficiency reasoning, so I have some trouble expressing myself about it. (##) Yes, I am going to start reading about efficiency in haskell :) I'd just prefer to have the answer sooner. [2] Any tips on which function(s) should I choose, or any way to make them more efficient. Thanks in advance J.A. ----- (**) would I get a different behavior if I had compiled the program. I've had some problems when trying to compile and use getCPUTime. Some stack overflows for big values of w, and for smaller values 0 in the execution time... I'll try to figure out what I'm doing wrong here... (##) OK, I can't say my english is perfect, mainly when it comes to technical issues, so sometimes I have trouble expressing about many other things things. Feel free to correct my spelling, grammar, etc... :)

1 0

independant monads used together?
by Jan-Willem Maessen 11 Nov '01

11 Nov '01

Pixel <pixel(a)mandrakesoft.com> asks: > I'm trying to achieve something like (ocaml) > [code deleted] > which is a foldl on 2 iterators. I've managed to use monads for one iterator, > but i completly miss the way to work with 2 monads. Is there really no other > solution than creating a monad over the 2 iterators?? Why monadic iterators at all? One of the great things about lazy lists is they encapsulate iteration nicely: Elements can be generated as they're consumed. This is pretty much what a regular folding zip would buy you: zipFoldl f z a b = foldl (\sofar (a,b) -> f sofar a b) z (zip a b) You're having trouble combining the results of two state monads precisely because they're manipulating two *independent* pieces of state, and you're trying to combine the *states* of the monads in some fashion. What should the type of the result of the manipulation be? Where are the initial states of each computation coming from? Some computations really are much more easily done in the value domain then under a wrapper like a monad which obscures their real structure. -Jan-Willem Maessen jmaessen(a)mit.edu

3 2

independant monads used together?
by Pixel 09 Nov '01

09 Nov '01

I'm trying to achieve something like (ocaml) let rec zipfold f init it1 it2 = if it1#is_end || it2#is_end then init else let v1, v2 = it1#value, it2#value in it1#next ; it2#next ; zipfold f (f v1 v2 init) it1 it2 which is a foldl on 2 iterators. I've managed to use monads for one iterator, but i completly miss the way to work with 2 monads. Is there really no other solution than creating a monad over the 2 iterators?? -- using the StateTrans as in http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm newtype StateTrans s a = ST( s -> (s, a) ) -- can't write l == [] otherwise it need Eq on elem of lists is_empty_list [] = True is_empty_list _ = False is_empty = ST(\l-> (l, is_empty_list l)) val = ST(\l -> (l, head l)) next = ST(\l -> (tail l, ())) myfoldl f init = do b <- is_empty if b then return init else do e <- val next myfoldl f (f e init) thanks -- Pixel

1 0

random (unspecified behaviour)
by Jorge Adriano 09 Nov '01

09 Nov '01

>From the std libraries description: "randomR takes a range (lo,hi) and a random number generator g, and returns a random value uniformly distributed in the closed interval [lo,hi], together with a new generator. It is unspecified what happens if lo>hi." Shouldn't everything be specified? J.A.

1 0

A newbie's proud first code
by Luke Maurer 07 Nov '01

07 Nov '01

Hi! I'm glad to have run accross Haskell, as a project I've been toying with in my mind seems very well-suited for this. It involves the numeric solution of differential equations. I'm thrilled to see how easy this is, as shown in my first little code snippet: {snip} -- Euler's method for solution of first-order differential equations -- In function arguments, the initial value problem under consideration is: -- df/dt = f'(f, t) -- f(0) = f0 -- The euler function returns an infinite list of the values at each interval -- of length dt of the solution. euler :: (Num a) => (a -> a -> a) -> a -> a -> [a] euler f' dt f0 = euler' f' dt f0 0 -- t "defaults" to 0 -- This function does the actual work, sparing the user from having to supply -- a value for t (which should always be 0 in the initial call, anyway) euler' :: (Num a) => (a -> a -> a) -> a -> a -> a -> [a] euler' f' dt f t = f : euler' f' dt fnext (t + dt) where fnext = f + dt * (f' f t) {snip} (Only three lines of actual code (not counting declarations)! Consider me a convert :-) Yes, you could do it like this in Lisp, I'm sure, but this is so much more succinct and expressive ... and Lisp can't do this cool infinite list stuff, can it?) My only issue (and it is nitpicky) is that I don't really like having to declare an extra function (euler') in the same scope as euler. I tried playing with where clauses or let expressions, but I couldn't find a way to make GHC happy without introducing a bunch of extra variables (since I'd need new versions of the arguments to euler; in euler', I just used the same names. Also, nested "where" doesn't work as I'd like it to.) Is there, in fact, a more concise way to express what I'm doing? Would anyone like to comment on my style (or lack thereof), idiom, etc., so I can squelch any bad habits before they start :-) ? Thanks! Jyrinx jyrinx_list at mindspring dot com

7 7