Übersetzen von "Why Functional Programming Matters" in Haskell

Question

Zur kulturellen und intellektuellen Bereicherung habe ich beschlossen, ein wenig Haskell zu lernen. Ich habe Hugh's "Why Functional Programming Matters" gelesen hier lesen und versuche, den Code in echtes Haskell zu übersetzen. Ich habe hier meinen Versuch angehängt (für die numerischen Teile des Papiers; der Alpha-Beta-Algorithmus ist noch interessanter, aber ich müsste auch einen Spielbewerter von Grund auf schreiben!).

Bis jetzt war es eher ein Übung in der Haskell-Syntax als alles andere. Ich habe bereits einfache Dinge wie die Übersetzung von repeat in das native Haskell iterate, die Übersetzung einiger Funktionen, die viele Klammern verwendet haben, in Funktionskomposition (wodurch sie im Prozess mehr punktfrei wurden), usw., gemacht.

Aber mein Code funktioniert sicherlich, und ich frage mich, ob er ausreichend "haskellhaft" ist. Können mir Experten dort draußen einige Hinweise geben?

-- 4.1 Newton-Raphson-Quadratwurzeln
next n x = (x + n/x)/2.0

-- -- Dies ist "iterate::(a->a)->a->[a]"
-- wiederholen 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 numerische Differenzierung

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)

-- benötigen fromIntegral, um aus dem Int, der von round herauskommt, einen Nicht-Integer zu machen
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) -- wie können wir das punktfrei machen?
super :: (RealFrac t, Floating t) => [t] -> [t] 
           -- ohne dies will es [double]->[double] sein
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 wird zu (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: Das Folgende sollte etwa pi sein
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))

-- Gibt es eine Möglichkeit, die Anzahl der Iterationen im Auge zu behalten? Status-Monad, aber das scheint wie viel Arbeit...\

Answer 1

4.1 Newton-Raphson-Quadratwurzeln

Diese zwei Zeilen

sqroot a0 eps n = within eps (iterate (next n) a0)
relativesqrt a0 eps n = relative eps (iterate (next n) a0)

sind fast identisch, sodass man die Dinge noch einen Schritt weiter abstrahieren könnte:

sqroot methode a0 eps n = method eps (iterate (next n) a0)
relativesqrt = sqroot relative
withinsqrt   = sqroot within

4.2 Numerische Differentiation

Ich sehe keinen Sinn darin, h0 als Argument der Funktion differentiate zu haben, da es nur der Startpunkt für die 0 Grenzfolge ist. (Das gleiche trifft nicht auf a0 im Newton-Rhapson-Fall zu, wo der Startpunkt wichtig sein könnte).

Ich denke, es ist genauso angemessen, über die Geschwindigkeit nachzudenken, mit der diese Grenze gegen Null geht:

differentiate rate f x = map (easydiff f x) (iterate rate 1)

Natürlich könnte man auch beides tun:

differentiate rate h0 f x = map (easydiff f x) (iterate rate h0)

In jedem Fall ist es eine ziemlich willkürliche Entscheidung.

4.2 Integration

Sie können verwenden

zipWith (+) (integ f a m fa fm) (integ f m b fm fb)

anstatt

map (uncurry (+)) (zip (integ f a m fa fm) (integ f m b fm fb))

was meiner Meinung nach lesbarer ist.

Answer 2

Für within und relative würde ich die bewachte Notation verwenden:

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

Für second könnten Sie !! 1 schreiben. Besonders das letzte ist persönliche Vorliebe, denke ich.

Sie sollten auch die Typsignaturen angeben.

Bearbeiten: Wenn Sie auf Verschleierung stehen, probieren Sie dies:

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

(Typ überprüft, nicht getestet -- und ich weiß nie, ob ich den Filter richtig bekomme oder ob er verneint werden muss ;)

Answer 3

Roger Costello hat eine zweiteilige Zusammenfassung des John Hughes Papiers geschrieben, in dem der originale Miranda-Code ins Haskell übersetzt wird. Hier sind Teil eins und Teil zwei seiner Ausarbeitung.