November 2001 - Haskell-Cafe

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 10 Nov '01

10 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 06 Nov '01

06 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

Re: using haskell as a shell language
by Juan Carlos Arevalo-Baeza 06 Nov '01

06 Nov '01

On Tue, 6 Nov 2001 04:32:05 +0000 (GMT), D. Tweed wrote: >[Suggest moving any followup to haskell-cafe to avoid boring people] Sure. >On Mon, 5 Nov 2001, Juan Carlos Arevalo-Baeza wrote: > >> On Tue, 6 Nov 2001 03:42:51 +0000 (GMT), D. Tweed wrote: >> >> >The name that >> >gets passed to the interpreter is `the top-level name of the script', so >> >if /home/tweed/bin/myscript.hs is actually a symlink to >> >/home/tweed/src/haskell/myscript.hs and I invoke it from /home/tweed/odd/ >> >with ../bin/myscript.hs, what gets passed is "../bin/myscript.hs" (at >> >least under bash on linux). So whilst the interpreter could in principlex >> >get to thinking it should look in /home/tweed/bin/ for imports by applying >> >"../bin/myscript.hs" to $cwd, AFAICS there's no way it can get hold of the >> >directory /home/tweed/src/haskell. When I figured this out I just decided >> >that the method that would lead to least banging of my head against wall >> >was just to absolute path any imports of non standard distribution code. >> >> Well... I still disagree. From my point of view, it could be argued the order in which directories are searched for modules, but I don't think there's any need to exclude any directories. The interpreter should search not just the current directory, but also the directory of the file where the source was found. At least. I'd even add subdirectories "./modules/" (or "./haskell.modules/" or something like that) of both of them, just for added value :) >> >> IMHO, there's no reason not to search a reasonable place for a needed piece of information. It's like Koenig lookups in C++. It just makes sense to look there, just in case. > >I entirely agree it would be great if this could be done. However it seems >that runhugs at least _doesn't_ do it, and I suspect that may be because >it technically can't. Oh, it sure can. If a file has hard-links, it just means that it can be accessed through two different paths. I'm just saying that, looking in the path that was used for accessing the file sounds like a very good (and easily implementable) idea to me. >I never use unix hardlinks myself (only symlinks), >but IIRC if you've got two or more hardlinks to a file there's no way to >find out from the filesystem what the directories of the other links to >the file are, so if you invoke via a hardlink then it's really difficult >to do automatic imports correctly. (I may be wrong about this.) Oh, yes. I understand you perfectly. But that's not a good reason not to try the one known path. Just in case. >Incidentally, I do have a setup with >symlinks as described above; it's not just hypothetical. > >> Anyway... This is not my war. Just my opinion. O:-) > >Oh, you make very good points, I just suspect that it `can't be done'. I'd >love to be proved wrong :-) Remember that I'm just advocating in favor of "looking in additional places" for the files, nothing more. That's neither technically impossible nor unreasonable. What I'm saying, if you will, is that the fact that the needle _might_ be in the haystack doesn't mean that it's not worth bothering to look in the needle box. So to speak. :) Salutaciones, JCAB email: jcab(a)roningames.com ICQ: 101728263 The Rumblings are back: http://www.JCABs-Rumblings.com

2 1

Using the std libraries in Ghc(i)
by Jorge Adriano 04 Nov '01

04 Nov '01

How can I use the std functions (listed in the 'Standard Libraries for Haskell 98' documentation) in ghc(i)? I've read the ghc documentation, and seen the several categories (which can be added with '-package category_name') available, but I still don't know how to access functions like unfoldr, transpose etc... Thanks in advance, J.A.

2 1

Re: URGENT: File exists
by Richard Uhtenwoldt 03 Nov '01

03 Nov '01

bracaman(a)box.sk writes: >I am trying to emulate bash in haskell, and i got a function called shell that waits fot the command and then executes it. The problem is that if the file does not exist, the program returns to Main (it gets out of the shell). The only thing i want to do is to return to the shell after an IOError. > >How can i perform such a thing? You could test if the file exists, like you said before, but that test would fail once in a while, when another process deletes the file after your test but before the file is opened. This is called a "race condition" and should be avoided when possible. The best thing is to use catch which has the type IO a -> (IOError -> IO a) -> IO a. An example (untested code) is catch (do hdl<-openFile "/home/bracaman/foo" ReadMode char<-hGetChar hdl string<-hGetLine hdl ) --we caught an exception: (\errorCode-> if isDoesNotExistError errorCode then "return to shell" else if isPermissionError errorCode then "return to shell" else --something strange happened. --re-raise the exception, which will probably return control to Main. ioError errorCode ) P.S. Instead of (do hdl<-openFile "/home/bracaman/foo" ReadMode char<-hGetChar hdl string<-hGetLine hdl ... ) you could have (do fileContentsAsABigString<-readFile "/home/bracaman/foo" ... ) but I try to stay away from readFile and getContents because they're not referentially transparent.

1 0

Evolution of a Haskell Programmer
by Dmitry Astapov 01 Nov '01

01 Nov '01

It's a pity that such a link is not mentioned in "Haskell Bookshelf" :) http://www.willamette.edu/~fruehr/haskell/evolution.html -- Dmitry Astapov //ADEpt E-mail: adept(a)umc.com.ua GPG KeyID/fprint: F5D7639D/CA36 E6C4 815D 434D 0498 2B08 7867 4860 F5D7 639D

1 0

HaXml, emeory usage and segmentation fault
by Dmitry Astapov 31 Oct '01

31 Oct '01

I have Hugs version February 2001, HaXml version 1.02 and this program: > module Main where > import XmlLib > > main = processXmlWith (invoices `o` tag "invoice") > > invoices = > html > [ hhead > [ htitle [ ("Invoices"!)] ], > hbody > [ customers `o` children `with` tag "customer" ] > ] > > customers = > cat > [ h2 [ ("Customer"!) ], > contracts `o` children `with` tag "contract" > ] > > contracts = > cat > [ h3 [ ("Id:"!), ("id"?)], > hpara [ ("Access:"!), keep /> txt ] `o` children `with` tag "access", > hpara [ ("Intl:"!), keep /> txt] `o` children `with` tag "inter" > ] This program can process following file: <?xml version='1.0'?> <invoice> <customer> <contract id='1'> <access>1</access> <inter>1</inter> </contract> <contract id='2'> <access>2</access> <inter>2</inter> </contract> </customer> </invoice> (I use "runhugs translate.hs invoice.xml invoice.html") Now increase amount of <customer>s to 10, and amount of <contract>s within each customer to 999. After that, "runhugs -h6000000 translate.hs invoice.xml invoice.html" dumps core :( What's the reason: bug in hugs, bug in HaXml, or my own bad programming techniques? -- Dmitry Astapov //ADEpt E-mail: adept(a)umc.com.ua GPG KeyID/fprint: F5D7639D/CA36 E6C4 815D 434D 0498 2B08 7867 4860 F5D7 639D

2 6