typically the first thing i do when learning a new programming language is to write newton’s method for root-finding (locating the y value where a function evaluates to 0) in it. here’s my (probably silly) haskell version. i’ll go through it piece by piece so i understand it better.
converge (old:new:xs) t = if reldiff old new <= t
then new
else converge (new:xs) t
where reldiff old new = abs (old-new) / old
here i define a function ‘converge’ which, because there are two chunks before the equals sign, takes two arguments. function arguments (both defining and calling) in haskell are separated by spaces, much like in lisp. the second argument is just a threshold value; once the relative difference between successive newton iterates becomes less than t, the recursion stops and the most recent iterate is returned.
the first argument is more complicated. the parenthesized thing is a pattern matching expression; it takes a list with at least two values, binds the first two to ‘old’ and ‘new’, and the rest of the list (possibly empty) to xs. haskell lists are linked lists just like in lisp. ‘:’ is the list constructor, which you can see both in the pattern matching and in the else (recursive) clause. since we split the original first parameter apart we can’t just call ‘tail’ (lisp ‘cdr’) on it, we have to put it back together. so what is this mysterious list? it’s an infinite list of newton iterates, of course. i’ll come back to this.
finally, the where clause at the bottom lets me specify bound variables to be used in the definition of converge. functions are just a type of variable, so i can define the local function reldiff here. it just computes the relative (percentage) difference between its two parameters, old and new.
newton f f' x0 = x1:xs
where x1 = x0 - f x0 / f' x0
xs = newton f f' x1
yes, all the work here is done in the where clause. newton takes three parameters: in order, a function f, f’s derivative f’, and an initial guess x0. x1 is simple; it’s the next iterate, computed via the iteration function in the wikipedia article i linked to at the top. the definition for xs would be doing something really scary in just about every other language: non-terminating recursion. also since newton generates a list, we end up with an infinite list too. happily, haskell does lazy evaluation, which means that new newton iterates are only computed when they are asked for by converge.
main = putStrLn (show (converge (newton f f' 3) 1e-3))
where f x = sin x
f' x = cos x
nothing much to see here, just some i/o. show converts things to strings so they can be printed. this applies newton’s method to sin(x) with an initial guess of 3 and a threshold of one thousandth. when it is run it prints out a value for pi accurate to ten significant digits, since sin(pi) = 0 and 3 is pretty close to that zero crossing.
