Translating "Why Functional Programming Matters" into Haskell

Question

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...\

Answer 1

For within and relative I would use guarded notation:

within eps (a:b:rest)
  | abs(a-b)<=eps = b
  | otherwise = within eps (b:rest)

For 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 ;)

Answer 2

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.

Answer 3

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......