haskell - 如何在haskell中实现嵌套函数

Question

I recently came across this question:
这基本上是问如何实现这个函数来计算 f(n) 的极限:

我将如何在haskell中实现这一点？我正在尝试学习函数式编程，现在这对我来说似乎是一个很好的挑战

Answer 1

有很多方法!

这是一个使用递归辅助函数的例子:

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

手工解决:

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

这是使用递归辅助函数的另一种方法:

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)

手工解决:

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

第一种方法是 尾递归 而第二个只是递归的。

或者，正如链接所说，折叠

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

再次，手动解决:

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)