Translating "Why Functional Programming Matters" into Haskell
functional-programming, haskell
Solution
4.1 Newton-Raphson square roots
These two lines
sqroot a0 eps n = within eps (iterate (next n) a0)
relativesqrt a0 eps n = relative eps (iterate (next n) a0)
are almost identical, so you could abstract things one step further:
sqroot method a0 eps n = method eps (iterate (next n) a0)
relativesqrt = sqroot relative
withinsqrt = sqroot within
4.2 Numerical differentiation
I don't see the point in having `h0` as an argument to the `differentiate` function as it's just the starting point for the `0` limiting sequence. (The same is not true for `a0` in the Newton-Rhapson case, where the starting point might matter).
I think it is equally appropriate to abstract over the rate of which this limit approaches zero:
differentiate rate f x = map (easydiff f x) (iterate rate 1)
Of course one could do both:
differentiate rate h0 f x = map (easydiff f x) (iterate rate h0)
In any case, it's a pretty arbitrary decision.
4.2 Integration
You can use
zipWith (+) (integ f a m fa fm) (integ f m b fm fb)
instead of
map (uncurry (+)) (zip (integ f a m fa fm) (integ f m b fm fb))
which I think is more readable.
Problem
For cultural and intellectual enrichment, I've decided to learn a bit of Haskell. I've been reading Hughes' "Why Functional Programming Matters" and am trying to translate its code into true Haskell. I've attached some of my attempt below (for the numerical parts of the paper; the alpha-beta algorithm is even more interesting but I'd also have to write a game evaluator from scratch!). At this point it's been more of an exercise in Haskell syntax than anything else. I've already done simple things like translate `repeat` into the native Haskell `iterate`, translate a few functions that used a lot of parentheses to function composition (making them more point-free in the process), etc. But my code certainly works, and I wonder if it's sufficiently "Haskell-ish". Can any experts out there give me some hints? ``` -- 4.1 Newton-Raphson square roots next n x = (x + n/x)/2.0 -- -- this is "iterate::(a->a)->a->[a]" -- repeat f a = a : iterate f (f a) within eps (a:b:rest) = if abs(a-b) <= eps then b else within eps (b:rest) sqroot a0 eps n = within eps (iterate (next n) a0) relative eps (a:b:rest) = if abs(a-b) <= eps*abs(b) then b else relative eps (b:rest) relativesqrt a0 eps n = relative eps (iterate (next n) a0) -- 4.2 numerical differentiation easydiff f x h = (f (x+h) - f x) / h differentiate h0 f x = map (easydiff f x) (iterate (/2) h0) -- diff1a h0 eps f x = within eps (differentiate h0 f x) diff1 h0 eps f = within eps . differentiate h0 f elimerror n (a:b:rest) = (b*(2**n)-a)/(2**n-1) : elimerror n (b:rest) -- need fromIntegral to make a non-integer out of the Int which comes out of round order (a:b:c:rest) = fromIntegral (round (logBase 2 ((a-c)/(b-c)-1))) improve s = elimerror (order s) s --diff2a h0 eps f x = within eps (improve (differentiate h0 f x)) diff2 h0 eps f = within eps . improve . differentiate h0 f --super s = map second (iterate improve s) -- how can we make this point-free? super :: (RealFrac t, Floating t) => [t] -> [t] -- w/o this it wants to be [double]->[double] super = map second . iterate improve -- second (a:b:rest) = b second = head . tail diff3 h0 eps f = within eps . super . differentiate h0 f -- 4.3 integration easyintegrate f a b = (f a + f b)*(b-a)/2 -- addpair becomes (uncurry (+)) integrate f a b = integ f a b (f a) (f b) integ f a b fa fb = (fa+fb)*(b-a)/2 : map (uncurry (+)) (zip (integ f a m fa fm) (integ f m b fm fb)) where m = (a+b)/2 fm = f m -- test: following should be about pi approxpi eps = within eps (improve (integrate (\x -> 4/(1+x*x)) 0 1)) superpi eps = within eps (super (integrate (\x -> 4/(1+x*x)) 0 1)) -- is there any way to keep track of the number of iterations? state monad, but seems like a lot of work...\ ```