Translating "Why Functional Programming Matters" into Haskell

Go To StackoverFlow.com

14

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...\
2009-06-16 08:15
by Andrew Jaffe
The last edit by @Juliet seems to have botched the example starting from within (inside :) within - ShiDoiSi 2009-06-17 09:34
Yes, noticed and fixed. I've now removed "pre" since it was screwing up the text; will have to live with bad syntax coloring.

Is this a bug?? - Andrew Jaffe 2009-06-17 11:06

Yes, StackOverflow's syntax highlighting sucks at Haskell. Looking at Uservoice, it seems that, as usual, 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
When you are done here, it would be good if you post whatever you've done to (say) the Haskell mailing list — a Haskell version of "Why Functional Programming Matters" would be much appreciated by many - ShreevatsaR 2009-06-17 16:38
Yes, Haskell coloring doesn't work. But actually the real problem was the "pre" tag which actually deleted some text within the code - Andrew Jaffe 2009-06-17 19:48
When using
, you need still to use HTML entity references in the text, e.g., "<" rather than "<" - Curt J. Sampson 2009-06-18 10:13


10

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.

2009-06-16 09:00
by Jonas


4

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

2009-06-16 08:30
by ShiDoiSi


2

Roger Costello has written a two parts summary of the John Hughes paper translating the original Miranda code to Haskell. Here are part one and part two of his writeup.

2014-07-21 12:39
by The Dude


0

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

2010-05-14 16:18
by BMeph
Ads