Wie kann ich in verschachtelte Funktionen implementieren Haskell

Question

I recently came across this question:

die im Grunde fragt, wie diese Funktion zu implementieren, um die Grenze von f (n) zu berechnen:

Wie würde ich dies in Haskell implementieren ? Ich versuche, funktionale Programmierung zu lernen, und dies scheint eine gute Herausforderung für mich jetzt

Answer 1

Es gibt eine Reihe von Möglichkeiten!

Hier ist eine rekursive Hilfsfunktion mit:

f :: (Eq a, Floating a) => a -> a 
f n = f' n n 
    where f' 1 x = x 
     f' n x = let n' = n-1 in f' n' (n'/(1 + x)) 

es von Hand Ausarbeiten:

f 1 = f' 1 1 
    = 1 
f 2 = f' 2 2 
    = f' 1 (1/(1 + 2)) 
    = 1/(1+2) 
f 3 = f' 3 3 
    = f' 2 (2/(1 + 3)) 
    = f' 1 (1/(1 + (2/(1 + 3)))) 
    = 1/(1 + (2/(1 + 3))) 

Hier ist eine andere Art und Weise mit einer rekursiven Hilfsfunktion zu tun:

f :: (Eq a, Floating a) => a -> a 
f n = f' 1 n 
    where f' a n | a == n = a 
       | otherwise = a/(1 + f' (a+1) n) 

Ausarbeiten von Hand:

f 1 = f' 1 1 
    = 1 
f 2 = f' 1 2 
    = 1/(1 + f' 2 2) 
    = 1/(1 + 2) 
f 3 = f' 1 3 
    = 1/(1 + f' 2 3) 
    = 1/(1 + (2/(1 + f' 3 3))) 
    = 1/(1 + (2/(1 + 3))) 

Der erste Ansatz war Tail-rekursive während die zweite einfach rekursiv war.

Oder, wie der Link sagt, durch eine Falte

f :: (Eq a, Floating a) => a -> a 
f n = foldr1 (\n x -> n/(1 + x)) [1..n] 

Wieder ist es aus mit der Hand arbeiten:

f 5 = foldr1 (\n x -> n/(1 + x)) [1,2,3,4,5] 
    = g 1 (g 2 (g 3 (g 4 5))) 
    = g 1 (g 2 (g 3 (4/(1 + 5)))) 
    = g 1 (g 2 (3/(1 + (4/(1 + 5))))) 
    = g 1 (2/(1 + (3/(1 + (4/(1 + 5)))))) 
    = 1/(1 + (2/(1 + (3/(1 + (4/(1 + 5))))))) 
    where g = \n x -> n/(1 + x)