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...\
Is this a bug?? - Andrew Jaffe 2009-06-17 11:06
codinghorror(Jeff Atwood) quickly closes all bug reports as "declined". Probably the only way to get this fixed would be to directly report it upstream: http://code.google.com/p/google-code-prettify - ShreevatsaR 2009-06-17 16:34
, you need still to use HTML entity references in the text, e.g., "<" rather than "<" - Curt J. Sampson 2009-06-18 10:13
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.
You can use
zipWith (+) (integ f a m fa fm) (integ f m b fm fb)
map (uncurry (+)) (zip (integ f a m fa fm) (integ f m b fm fb))
which I think is more readable.
relative I would use guarded notation:
within eps (a:b:rest) | abs(a-b)<=eps = b | otherwise = within eps (b:rest)
second, you could write
!! 1. Especially that last one is personal preference, I guess.
You should also give the type signatures.
Edit: If you are into obfuscation, try:
within :: (Ord a, Num a) => a -> [a] -> a within eps l@(_:xs) = snd. head . filter ((<= eps) . fst) $ zip zs xs where zs = zipWith (\ a b -> abs (a-b)) l xs
(Type checked, not tested -- and I never know if I get the filter right or if it has to be negated ;)
So, is this a straight-across translation (i.e., try to keep the code looking as similar as possible) or an embedded (i.e., make as many idiomatic tweaks to the code as possible, without making the examples tougher to understand,of course) one?
Assuming that this "project" is still going on......