[Haskell-cafe] Debugging Newton's method for square roots
I am new to Haskell and need help in debugging my code. I wrote the following function for calculating square roots using Newton's method: my_sqrt :: Float - Float my_sqrt x = improve 1 x where improve y x = if abs (y * y - x) epsilon then y else improve ((y + (x/y))/ 2) x epsilon = 0.1 This works for several examples that I tried out but goes into an infinite loop for my_sqrt 96. How do I go about debugging this code in GHC or Hugs? (The equivalent code is well-behaved on MIT Scheme) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] searching haskell.org
Hi, I noticed that searching on Haskell.org (using the Search feature at the bottom) doesn't work as I expected. For example, searching for memoise produces no results. http://www.google.com/search?q=memoise+site%3Ahaskell.org produces 18 hits. Is this intentional? Thanks, Tamas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskellers in London (UK)?
Hi, Just thought I'd send out a quick mail to see if there are any other Haskellers based in London who might be interested in getting together occasionally. Anyway, if you're interested please reply to this. Cheers, --Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Debugging Newton's method for square roots
Vraj Mohan [EMAIL PROTECTED] writes: I am new to Haskell and need help in debugging my code. I wrote the following function for calculating square roots using Newton's method: my_sqrt :: Float - Float my_sqrt x = improve 1 x where improve y x = if abs (y * y - x) epsilon then y else improve ((y + (x/y))/ 2) x epsilon = 0.1 This works for several examples that I tried out but goes into an infinite loop for my_sqrt 96. Generally it's better to separate out the different parts of the algorithm. So sqrt_step x candidate = (candidate + x/candidate)/2 Now you can try take 20 $ iterate (sqrt_step 2) 1 and watch the convergence. When you're happy with that, you can use something like “head . dropWhile unconverged”. (The equivalent code is well-behaved on MIT Scheme) Is it? Is there equivalent code to “my_sqrt :: Float - Float”? (that might be pertinent). -- Jón Fairbairn [EMAIL PROTECTED] http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html (updated 2006-09-13) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] searching haskell.org
On Sun, Oct 15, 2006 at 08:37:19AM -0400, Tamas K Papp wrote: I noticed that searching on Haskell.org (using the Search feature at the bottom) doesn't work as I expected. For example, searching for memoise produces no results. This is searching haskellwiki. http://www.google.com/search?q=memoise+site%3Ahaskell.org produces 18 hits. This is finding hits outside the wiki. Is this intentional? It's expected, but not exactly intentional. It's probably not worth setting up a haskell.org search tool, but adding a form for doing a search with something like google restricted to the site might be useful. Thanks Ian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskellers in London (UK)?
On Sun, Oct 15, 2006 at 01:42:37PM +0100, Ben Moseley wrote: Just thought I'd send out a quick mail to see if there are any other Haskellers based in London who might be interested in getting together occasionally. Did you see http://www.haskell.org/pipermail/haskell/2006-October/018635.html ? Not quite London, but close. See http://www.oxfordbus.co.uk/espress1.shtml or http://www.oxfordtube.com/ for public transport between London and Oxford. Thanks Ian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] searching haskell.org
Hi I noticed that searching on Haskell.org (using the Search feature at the bottom) doesn't work as I expected. For example, searching for memoise produces no results. This is searching haskellwiki. Does anyone have the search logs for this page? If they were available, we might get a better idea of what people were searching for, and could then make the results more appropriate. For example, its entirely possible people are searching for functions (better prodivided by Hoogle search), wiki concepts (as currently searched for), haskell stuff (a google site search), or possibly something entirely different. My experience from Hoogle suggests that people don't use your search like you think they do! Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Debugging Newton's method for square roots
I wrote: Vraj Mohan [EMAIL PROTECTED] wrote: (The equivalent code is well-behaved on MIT Scheme) Is it? Is there equivalent code to “my_sqrt :: Float - Float”? (that might be pertinent). By which I mean HINT. (And one of the places to look for bugs is where you have hand coded a constant without due consideration of the implications). -- Jón Fairbairn [EMAIL PROTECTED] http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html (updated 2006-09-13) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Debugging Newton's method for square roots
On Sun, Oct 15, 2006 at 12:17:20PM +, Vraj Mohan wrote: I am new to Haskell and need help in debugging my code. I wrote the following function for calculating square roots using Newton's method: my_sqrt :: Float - Float my_sqrt x = improve 1 x where improve y x = if abs (y * y - x) epsilon then y else improve ((y + (x/y))/ 2) x epsilon = 0.1 This works for several examples that I tried out but goes into an infinite loop for my_sqrt 96. How do I go about debugging this code in GHC or Hugs? (The equivalent code is well-behaved on MIT Scheme) Hi Vraj, 1. First, generally about debugging: I asked this question a month ago, on this mailing list. See this thread: http://www.haskell.org/pipermail/haskell-cafe/2006-September/017858.html 2. Newton's method is not guaranteed to converge. For examples, and a nice introduction to uni- and multivariate rootfinding, see Numerical Methods in Economics, Kenneth L Judd, Chapter 5. I suggest that you use bisection, it is much more robust. I have written a bisection routine which I have been planning to post after a bit of testing, maybe you will find it useful: bisection tol reltol f a b | tol 0 || reltol 0 = error bisection needs positive tolerances | abs fa = tol = Just a -- a is a root | abs fb = tol = Just b -- b is a root | fa*fb 0 = Nothing -- IVT not guaranteed | a b = bis b a fb fa -- exchange endpoints | otherwise = bis a b fa fb -- standard case where fa = f a -- function evaluated only once at each fb = f b -- endpoint, store them here bis a b fa fb = let m = (a+b)/2 fm = f m in if (b-a) = reltol*(1+abs(a)+abs(b)) || abs fm = tol then Just m -- implicit assumption: fa * fb 0 else if fm*fa 0 -- new interval: [a,m] then bis a m fa fm else bis m b fm fb -- new interval: [m,b] -- uniroot is a specialisation of bisection, with commonly used -- tolerance values uniroot = bisection 1e-20 1e-15 Untested code: mysqrt x = uniroot f 0 x where f y = y**2-x It will give you a Maybe a type value, ie Nothing for negative numbers. Comments about my code are of course welcome, I am a newbie myself. Best, Tamas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] searching haskell.org
On Sun, Oct 15, 2006 at 03:41:53PM +0100, Neil Mitchell wrote: Hi I noticed that searching on Haskell.org (using the Search feature at the bottom) doesn't work as I expected. For example, searching for memoise produces no results. This is searching haskellwiki. Does anyone have the search logs for this page? If they were available, we might get a better idea of what people were searching for, and could then make the results more appropriate. For example, its entirely possible people are searching for functions (better prodivided by Hoogle search), wiki concepts (as currently searched for), haskell stuff (a google site search), or possibly something entirely different. My experience from Hoogle suggests that people don't use your search like you think they do! Typing haskell.org takes you to a page which has a search box at the bottom, so if the user doesn't look at the browser address bar (which does display http://haskell.org/haskellwiki/Haskell, indicating that you are inside the wiki), it is reasonable to suppose that the search box will search the whole site. I think it would be good to have multiple buttons, eg Search haskell.org (includes next two), Search HaskellWiki, Search mailing lists. Tamas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
Jim Apple wrote: On 10/14/06, Brian Hulley [EMAIL PROTECTED] wrote: User defined fixities are an enormous problem for an interactive editor This is the second or third time you've proposed a language change based on the editor you're writing. I don't think this is a fruitful avenue. Bertram Felgenhauer wrote: Brian Hulley wrote: infixr 9 .!! 99.9 Ouch. As far as editors go I have little sympathy. Nicolas Frisby wrote: I think it's unreasonable to tie programmers' hands for the sake of off-loading rather trivial tasks to editors. J. Garrett Morris wrote: On 10/14/06, Nicolas Frisby [EMAIL PROTECTED] wrote: Perhaps the editor could assume a default precedence ... I agree that changing the language in such an unintuitive way - breaking existing code in the process - to suit an editor is counterproductive and ridiculous. I feel that the example I used of an interactive editor has somewhat eclipsed the purpose of my post, which was basically to see if there is some way to arrive at an agreed association of operator precedences with symbolic ops such that this would include the current Prelude operators and have some kind of intuitive extension to all other possible symbolic ops which would respect one's expectations that * and + should be similar to * and + in terms of relative precedence and absolute associativity. After all, if a library writer decided to make * bind more loosely than + one might justifiably be frustrated at the apparent inconsistency therefore why not just make all this systematic and fixed down to remove these problems? I had thought perhaps someone might have already made such a global operator table suitable for functional programming, or some suitable algorithm hence the inclusion of my first stumbling attempt at one to try and set the ball rolling and at least save someone else several hours of hard work going down the same dead end if such it is. Jim Apple wrote: There are three ways to change Haskell's lexical structure: 1. DIY on an open-source compiler/interpreter of your choice. 2. Write your own compiler/interpreter. 3. Get the change into Haskell''. If the Haskell'' procedure is like the Haskell' procedure, you'll have to do 1 or 2 before you do 3. It's possible that you will convince someone that your syntax changes are worth doing, and that this person will do step 1 or step 2 for you, but I don't think so. I haven't done the research myself, but I think if you look at the source control logs for Your Favorite Haskell Compiler/interpreter and the HCAR, you will find very few commits/projects devoted to syntax. I think this is because Haskellers are much more interested in semantics. Afaiu the whole concept of type classes arose because of the desire to avoid having to think up different names for related functions and MPTCs were suggested by the syntax for single parameter TCs (though I can't remember the reference where I think I remember reading this latter point). Proposing changes that break existing code or segment the Haskell code base just doesn't seem like a win. Since all syntactic and many semantic changes necessarily break existing code or segment the code base this would seem to imply that the language should not be changed at all or that everything must be backwards compatible, so that we have to drag the Achilles heel of original mistakes around for all eternity. I'd have thought a solution would be to just use a tool to automatically convert existing code to whatever new syntax is found to be better, thus allowing the language to be gradually perfected as more and more issues are brought to light. Still I agree with you that a more sensible approach in terms of someone like me writing an editor is simply for me to take Haskell as an inspiration and incorporate my ideas in it so that any changes can later be seen in relation to a (hopefully facilitated and enjoyable) programming experience rather than trying to share my ideas piecemeal and insufficiently contextualized as they arise. Thanks to all who replied, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Debugging Newton's method for square roots
Vraj Mohan wrote: my_sqrt :: Float - Float my_sqrt x = improve 1 x where improve y x = if abs (y * y - x) epsilon then y else improve ((y + (x/y))/ 2) x epsilon = 0.1 This works for several examples that I tried out but goes into an infinite loop for my_sqrt 96. How do I go about debugging this code in GHC or Hugs? 1) As Jon said, by seperating the iteration from the selection of the result. iterate, filter, head, etc. are your friends. Makes the code more readable and maintainable, too. 2) By learning more about floating point numbers. There is no Float y such that | y*y - 96 | 0.1. That's why such an iteration is better terminated not when the result is good enough, but when it stops getting better. It's also the reason why you code might work with -fexcess-precision or in an untyped language or with the next or previous compiler release or on rainy days or whatever else. Udo. -- Walk softly and carry a BFG-9000. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[4]: [Haskell-cafe] windows file locking
Hello Stefan, Wednesday, October 11, 2006, 4:53:19 PM, you wrote: So far the windows API seems to work for me. Currently I'm still struggling to not write garbage to the file but the shared access works now. Does anyone have an example how to use it (e.g. the implementation of hPutStr on windows or something, i did not find it in the ghc source code)? I tried to use Streams before but without the windows API. sorry, i'm a bit to fool you. there is a way to apply Handle API to HANDLE. you should just 1) open file using win32 API and get HANDLE 2) convert this HANDLE to FD using _open_osfhandle from win32 api 3) open Handle over FD using fdToHandle function from GHC.Handle module alternatively, you can use Streams with the same mechanism: 1) open file using win32 API and get HANDLE 2) convert this HANDLE to FD using _open_osfhandle from win32 api // it's in C language: fd = _open_osfhandle (someHANDLE, _O_TEXT | _O_WRONLY); 3) use bufferBlockStream to make full-featured Stream from this FD: do stream - bufferBlockStream fd it is from MS docs: SUMMARY There are multiple types of file handles that can be opened using the Win32 API and the C Run-time: Returned Type File Creation API API Set - HANDLE CreateFile() Win32 HFILE OpenFile()/_lcreat() Win32 int_creat()/_open() C Run-time FILE * fopen()C Run-time In general, these file I/O families are incompatible with each other. On some implementations of the Win32 application programming interfaces (APIs), the OpenFile()/_lcreat() family of file I/O APIs are implemented as wrappers around the CreateFile() family of file I/O APIs, meaning that OpenFile(), _lcreat(), and _lopen() end up calling CreateFile(), returning the handle returned by CreateFile(), and do not maintain any state information about the file themselves. However, this is an implementation detail only and is NOT a design feature. NOTE: You cannot count on this being true on other implementations of the Win32 APIs. Win32 file I/O APIs may be written using different methods on other platforms, so reliance on this implementation detail may cause your application to fail. The rule to follow is to use one family of file I/O APIs and stick with them--do not open a file with _lopen() and read from it with ReadFile(), for example. This kind of incorrect use of the file I/O APIs can easily be caught by the compiler, because the file types (HFILE and HANDLE respectively) are incompatible with each other and the compiler will warn you (at warning level /w3 or higher) when you have incorrectly passed one type of file handle to a file I/O API that is expecting another, such as passing an HFILE type to ReadFile(HANDLE, ...) in the above example. MORE INFORMATION Compatibility - The OpenFile() family of file I/O functions is provided only for compatibility with earlier versions of Windows. New Win32-based applications should use the CreateFile() family of file I/O APIs, which provide added functionality that the earlier file I/O APIs do not provide. Each of the two families of C Run-time file I/O APIs are incompatible with any of the other file I/O families. It is incorrect to open a file handle with one of the C Run-time file I/O APIs and operate on that file handle with any other family of file I/O APIs, nor can a C Run-time file I/O family operate on file handles opened by any other file I/O family. _get_osfhandle() For the C Run-time unbuffered I/O family of APIs [_open(), and so forth], it is possible to extract the operating system handle that is associated with that C run-time handle via the _get_osfhandle() C Run-time API. The operating system handle is the handle stored in a C Run-time internal structure associated with that C Run-time file handle. This operating system handle is the handle that is returned from an operating system call made by the C Run-time to open a file [CreateFile() in this case] when you call one of the C Run-time unbuffered I/O APIs [_open(), _creat(), _sopen(), and so forth]. The _get_osfhandle() C Run-time call is provided for informational purposes only. Problems may occur if you read or write to the file using the operating system handle returned from _get_osfhandle(); for these reasons we recommend that you do not use the returned handle to read or write to the file. _open_osfhandle() - It is also possible to construct a C Run-time unbuffered file I/O handle from an operating system handle [a CreateFile() handle] with the _open_osfhandle() C Run-time API. In this case, the C Run-time uses the existing operating system handle that you pass in rather than opening the file itself. It is possible to use the original operating system handle to read or write to the file, but it is very important that you use only the original handle or the returned C
Re: [Haskell-cafe] Debugging Newton's method for square roots
Vraj Mohan wrote: This works for several examples that I tried out but goes into an infinite loop for my_sqrt 96. How do I go about debugging this code in GHC or Hugs? (The equivalent code is well-behaved on MIT Scheme) There was some excellent advice in the other responses, but I thought it worth mentioning that your Haskell code converges if you step up from Float - Float to Double - Double. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: optimization help
[EMAIL PROTECTED] wrote: Paul Hudak wrote: In fact avoiding space leaks was one of the motivations for our moving to an arrow framework for FRP (now called Yampa). Arrows amount to a point-free coding style, although with "arrow syntax" the cumbersomeness of programming in that style is largely alleviated. I think that's an entirely different thing. You changed representation of signal transformers from newtype SF a b = SF ([a] - [b]) to data SF a b = SF (a - (b, SF a b)) I think that you misunderstood what I said. When we went from FRP to Yampa, we changed from using signals directly, i.e. Signal a, to using signal functions, i.e.: SF a b = Signal a - Signal b When we did this, we made SF abstract, and we adopted the arrow framework to allow composing, etc. signal functions. This meant that you could not get your hands on Signals directly, which helped to prevent space leaks. What you describe above is a change that we made in the implementation of signal functions (specifically, from streams to continuations), which indeed is an entirely different thing. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Debugging Newton's method for square roots
Hello Udo, Sunday, October 15, 2006, 7:02:05 PM, you wrote: stops getting better. It's also the reason why you code might work with -fexcess-precision or in an untyped language or with the next or previous compiler release or on rainy days or whatever else. our brand-new GHC 22.6 has a mood! on the rainy days it meditates about life meaning and can make some errors due to inattention. we have added to our BugTrac system field where you should describe weather at the moment of bug - this will greatly simplify our debugging work :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Debugging Newton's method for square roots
G'day all. Quoting Tamas K Papp [EMAIL PROTECTED]: 2. Newton's method is not guaranteed to converge. For computing square roots, it is. The square root function is exceedingly well-behaved. But you can make things better by choosing a smart initial estimate. The initial estimate in this version is so good that you only need a fixed number of iterations, so there are no loops here. mysqrt :: Double - Double mysqrt x | x = 0= if x == 0 then 0 else error mysqrt domain error | r == 1= sqrt2 * sqrtx | otherwise = sqrtx where (q,r) = exponent x `divMod` 2 sqrtx = scaleFloat q (sqrtSignificand (significand x)) -- Feel free to add more digits if this is insufficient sqrt2 = 1.41421356237309504880168872420969807856967 -- Compute the square root of a number in the range [0.5,1) sqrtSignificand :: Double - Double sqrtSignificand x = iter . iter . iter $ d0 where -- d0 is a third-order Chebyshev approximation to sqrt x x' = x * 4.0 - 3.0 d2 = -6.177921038278929e-3 d1 = 2 * x' * d2 + 0.14589875298243973 d0 = x' * d1 - d2 + 0.5 * 1.7196949654923188 iter sx = 0.5 * (sx + x / sx) Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
