在一个表达式中打印斐波那契数列的前 n 个数
Print the first n numbers of the fibonacci sequence in one expression
所以我最近一直在弄乱 Python，我试图找到一种方法来在单个表达式中输出斐波那契数列的第 n 个数。这是我到目前为止编写的代码：
(lambda f: f if f<2 else (f-1)+(f-2))(n)
# n == 1 -> 1
# n == 2 -> 1
# n == 3 -> 3
# n == 4 -> 5
# n == 5 -> 7
....
然而，正如我在上面评论的那样，这只会输出一组奇数。我很困惑为什么会这样，因为如果我将其重写为命名的 lambda 函数，它看起来像这样：
f = lambda n: n if n<2 else f(f-1)+f(f-2)
# f(1) -> 1
# f(2) -> 1
# f(3) -> 2
# f(4) -> 3
...
# f(10) -> 55
...
现在我添加 Lambda 微积分标签的原因是因为我不确定这个问题是否属于简单理解 Python 如何处理这个问题的范畴。我读过一些关于 lambda 演算中 Y 组合器的内容，但这对我来说是一门外语，无法从我找到的关于 lambda 演算的资源中得到任何信息。
现在，我尝试在一行代码中执行此操作而不是命名它的原因是因为我想尝试将此 lambda 函数放入列表理解中。所以做这样的事情：
[(lambda f: f if f<2 else (f-1)+(f-2))(n) for n in range(10)]
并创建斐波那契数列中前 x 个数字的数组。
我正在寻找的是一种在一个表达式中完成所有事情的方法，如果这属于 Lambda 演算的范畴，我相信它属于，有人可以解释这是如何工作的。
欢迎使用 JavaScript、C# 或其他支持 Lambda 函数的类 C 语言提供答案。
编辑： 我找到了解决我试图做的事情的方法：
[(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f:(lambda n: n if n<2 else f(n-1)+f(n-2)))(y) for y in range(10)]
我知道这根本不实用，永远不应该使用这种方法，但我担心的是我能否这样做，而不是我是否应该这样做。
您需要将您的 lambda 分配给一个实际变量，然后 调用 lambda 内部的 lambda：
>>> g = lambda f: f if f < 2 else g(f-1)+g(f-2)
>>> [g(n) for n in range(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
您必须以某种方式为其分配名称才能使用递归定义——否则递归 lambda 函数在 Python 中是不可能的，因为它没有任何引用它的特殊反身关键字.
正如@TerryA 提到的，您可以使用 this post 中的技巧，以便在具有递归定义的一条语句中生成一系列 x 斐波那契数列。
或者，您可以使用 closed form，这样会更快：
[int(round((lambda n: ((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))(x)))
for x in range(10)]
不过，这假设 x 不是很大，因为浮点运算会在 x=600 附近溢出，并且可能在该点之前有很大的舍入误差——正如@cdlane 指出的那样，这开始与x=71 处的实际序列，即 x in range(72).
编辑：@cdlane 共享了一个只有整数运算的封闭形式，理论上它应该适用于任何 x。我可能会用这个代替上面的表达式。
[0, 1] + [(4<<n*(3+n)) // ((4<<2*n)-(2<<n)-1) & ((2<<n)-1)
for n in range(10)][1:]
怎么样：
(lambda f: (4 << f * (3 + f)) // ((4 << 2 * f) - (2 << f) - 1) & ((2 << f) - 1))(n)
它没有以通常的方式启动序列：
0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, ...
但是一旦你过了 1，你就没事了。您将在博客条目 An integer formula for Fibonacci numbers 中找到详细说明以及大量相关信息。
在我的系统上，@lehiester 基于黄金比例的解决方案在 F71 处偏离 rails，产生 308061521170130，而不是 308061521170129，并继续偏离那里。
我有一个符合您标准的单行解决方案，但它是我写过的最疯狂的代码之一。它不使用列表理解，而是在一行中混合了动态解决方案和 lambda 函数。
fib = (lambda n: (lambda fib: fib(fib, [], n, None))(lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))))
稍微解释一下。第一部分 (lambda fib: fib(fib, [], n, None)) 将 lambda 函数作为参数，然后使用它期望的参数调用它。这个技巧允许我们为 lambda 函数分配一个名称，并将这个名称传递给它自己。这就是魔法。
相反，第二部分，即核心功能，lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))) 使用另一个技巧来实现动态解决方案。第一个参数 fib 是对自身的引用，第二个参数 arr 是包含我们的解决方案的数组，它是从左到右递归调用 fib 恰好 n 次。当第三个参数i变为0时，递归结束。第四个参数是个丑陋的把戏：它不被函数使用，而是用来调用arr.[=27的append方法=]
这绝对是最不优雅的解决方案，但也是最快的解决方案。我在下面报告 N=500 的时间。
天真的解决方案是不可行的，但在这里您可以找到一次计算一个元素的代码（这可能是您想要混合 lambda 函数和递归的方法）：
(lambda n: ((lambda fib: fib(fib,n+1))(lambda fib, i: (1 if i <= 2 else fib(fib,i-2) + fib(fib,i-1)))))(N)
@cdlane提出的解决方案：
%timeit [0, 1] + [(4<<n*(3+n)) // ((4<<2*n)-(2<<n)-1) & ((2<<n)-1) for n in range(N)][1:]
10 loops, best of 3: 88.3 ms per loop
@lehiester提出的解决方案：
%timeit [int(round((lambda n: ((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))(x))) for x in range(N)]
1000 loops, best of 3: 1.49 ms per loop
我丑陋的解决方案：
%timeit (lambda n: (lambda fib: fib(fib, [], n, None))(lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))))(N)
1000 loops, best of 3: 434 us per loop
另一个不使用递归的丑陋且更快的解决方案：
%timeit (lambda n: (lambda arr, fib_supp: [arr] + [fib_supp(arr) for i in xrange(n)])([], (lambda arr: arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2])))[0])(N)
1000 loops, best of 3: 346 us per loop
更新
我终于找到了一种优雅的方式来表达单行函数。想法总是一样的，只是使用 setitem 方法而不是 append。我使用的一些技巧可以在这个 link 中找到。这种方法只是有点慢，但至少是可读的：
%timeit (lambda n: (lambda arr, fib_supp: any(fib_supp(i, arr) for i in xrange(2,n)) or arr)([1] * n, (lambda i, arr: arr.__setitem__(i,(arr[i-1]+arr[i-2])))))(N)
1000 loops, best of 3: 385 us per loop
lambda 演算通过 Python
因为这是用 lambda-calculus 标记的，而不是写一个依赖于 python 特有的巧妙技巧或语言功能的答案，我是只会使用简单的 lambdas
U = lambda f: f (f)
Y = U (lambda h: lambda f: f (lambda x: h (h) (f) (x)))
loop = Y (lambda recur: lambda acc: lambda a: lambda b: lambda n:
acc if n == 0 else
recur (acc + [a]) (a + b) (a) (n - 1))
fibonacci = loop ([]) (0) (1)
print (fibonacci (10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
当然，我们使用了四个 named lambdas U、Y、loop 和 fibonacci——因为每个 lambdas是一个纯函数，我们可以用它的值
替换对其名称的任何引用
# in Y, replace U with its definition
Y = <b>(lambda f: f (f))</b> (lambda h: lambda f: f (lambda x: h (h) (f) (x)))
# in loop, replace Y with its definition
loop = <b>(lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x)))</b> (lambda recur: lambda acc: lambda a: lambda b: lambda n:
acc if n == 0 else
recur (acc + [a]) (a + b) (a) (n - 1))
# in fibonacci, replace loop with its definition
fibonacci = <b>(lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
acc if n == 0 else
recur (acc + [a]) (a + b) (a) (n - 1))</b> ([]) (0) (1)
fibonacci 现在是一个单一的纯表达式——我们可以在 print 语句中直接调用 lambda...
# in print, replace fibonacci with its definition
print (<b>(lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
acc if n == 0 else
recur (acc + [a]) (a + b) (a) (n - 1)) ([]) (0) (1)</b> (10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
再次使用另一个程序
我写了一个非常 （也在 Python 中）但是在不同程序的上下文中 - 它可能有助于帮助了解 generality 的技巧
再一次，用另一种语言
我们将在 JavaScript 中再次完成整个操作。 JS 更适合演示 这个练习，因为我们可以在浏览器中显示这里的代码，而且 lambda 语法更宽松（在代码格式方面）——除此之外，你会发现程序几乎是一样的
const U = f =>
f (f)
const Y =
U (h => f => f (x => h (h) (f) (x)))
const loop = Y (recur => acc => a => b => n =>
n === 0
? acc
: recur (acc.concat ([a])) (a + b) (a) (n - 1))
const fibonacci =
loop ([]) (0) (1)
console.log (fibonacci (10))
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
// 在 Y 中，用它的定义替换 U
Y = <b>(f => f(f))</b> (h => f => f (x => h(h) (f) (x)))
// 在循环中，用它的定义替换 Y
loop = <b>(f => f (f)) (h => f => f (x => h (h) (f) (x)))</b> (recur => acc => a => b => n =>
n === 0
？ acc
: 重复 (acc.concat ([a])) (a + b) (a) (n - 1))
// 在斐波那契中，用它的定义替换循环
斐波那契 = <b>(f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
n === 0
？ acc
: 重复 (acc.concat ([a])) (a + b) (a) (n - 1))</b> ([]) (0) (1)
fibonacci 现在是一个单一的纯表达式——我们可以在 console.log 语句中直接调用 lambda...
oh and it's really fast, too
console.time ('fibonacci (500)')
console.log ((f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
n === 0
? acc
: recur (acc.concat ([a])) (a + b) (a) (n - 1)) ([]) (0) (1) (500))
console.timeEnd ('fibonacci (500)')
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 490 more items ]
// fibonacci (500): 3 ms
熟能生巧
lambda 演算一直是我的 favourite areas of study. With just the Y-combinator alone, I've spent countless hours exploring its beauty and sophistication。我希望这些探索对您有所帮助。如果您对主题有任何其他问题，请不要害羞地问^_^
所以我最近一直在弄乱 Python，我试图找到一种方法来在单个表达式中输出斐波那契数列的第 n 个数。这是我到目前为止编写的代码：
(lambda f: f if f<2 else (f-1)+(f-2))(n)
# n == 1 -> 1
# n == 2 -> 1
# n == 3 -> 3
# n == 4 -> 5
# n == 5 -> 7
....
然而，正如我在上面评论的那样，这只会输出一组奇数。我很困惑为什么会这样，因为如果我将其重写为命名的 lambda 函数，它看起来像这样：
f = lambda n: n if n<2 else f(f-1)+f(f-2)
# f(1) -> 1
# f(2) -> 1
# f(3) -> 2
# f(4) -> 3
...
# f(10) -> 55
...
现在我添加 Lambda 微积分标签的原因是因为我不确定这个问题是否属于简单理解 Python 如何处理这个问题的范畴。我读过一些关于 lambda 演算中 Y 组合器的内容，但这对我来说是一门外语，无法从我找到的关于 lambda 演算的资源中得到任何信息。
现在，我尝试在一行代码中执行此操作而不是命名它的原因是因为我想尝试将此 lambda 函数放入列表理解中。所以做这样的事情：
[(lambda f: f if f<2 else (f-1)+(f-2))(n) for n in range(10)]
并创建斐波那契数列中前 x 个数字的数组。
我正在寻找的是一种在一个表达式中完成所有事情的方法，如果这属于 Lambda 演算的范畴，我相信它属于，有人可以解释这是如何工作的。
欢迎使用 JavaScript、C# 或其他支持 Lambda 函数的类 C 语言提供答案。
编辑： 我找到了解决我试图做的事情的方法：
[(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f:(lambda n: n if n<2 else f(n-1)+f(n-2)))(y) for y in range(10)]
我知道这根本不实用，永远不应该使用这种方法，但我担心的是我能否这样做，而不是我是否应该这样做。
您需要将您的 lambda 分配给一个实际变量，然后 调用 lambda 内部的 lambda：
>>> g = lambda f: f if f < 2 else g(f-1)+g(f-2)
>>> [g(n) for n in range(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
您必须以某种方式为其分配名称才能使用递归定义——否则递归 lambda 函数在 Python 中是不可能的，因为它没有任何引用它的特殊反身关键字.
正如@TerryA 提到的，您可以使用 this post 中的技巧，以便在具有递归定义的一条语句中生成一系列 x 斐波那契数列。
或者，您可以使用 closed form，这样会更快：
[int(round((lambda n: ((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))(x)))
for x in range(10)]
不过，这假设 x 不是很大，因为浮点运算会在 x=600 附近溢出，并且可能在该点之前有很大的舍入误差——正如@cdlane 指出的那样，这开始与x=71 处的实际序列，即 x in range(72).
编辑：@cdlane 共享了一个只有整数运算的封闭形式，理论上它应该适用于任何 x。我可能会用这个代替上面的表达式。
[0, 1] + [(4<<n*(3+n)) // ((4<<2*n)-(2<<n)-1) & ((2<<n)-1)
for n in range(10)][1:]
怎么样：
(lambda f: (4 << f * (3 + f)) // ((4 << 2 * f) - (2 << f) - 1) & ((2 << f) - 1))(n)
它没有以通常的方式启动序列：
0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, ...
但是一旦你过了 1，你就没事了。您将在博客条目 An integer formula for Fibonacci numbers 中找到详细说明以及大量相关信息。
在我的系统上，@lehiester 基于黄金比例的解决方案在 F71 处偏离 rails，产生 308061521170130，而不是 308061521170129，并继续偏离那里。
我有一个符合您标准的单行解决方案，但它是我写过的最疯狂的代码之一。它不使用列表理解，而是在一行中混合了动态解决方案和 lambda 函数。
fib = (lambda n: (lambda fib: fib(fib, [], n, None))(lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))))
稍微解释一下。第一部分 (lambda fib: fib(fib, [], n, None)) 将 lambda 函数作为参数，然后使用它期望的参数调用它。这个技巧允许我们为 lambda 函数分配一个名称，并将这个名称传递给它自己。这就是魔法。
相反，第二部分，即核心功能，lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))) 使用另一个技巧来实现动态解决方案。第一个参数 fib 是对自身的引用，第二个参数 arr 是包含我们的解决方案的数组，它是从左到右递归调用 fib 恰好 n 次。当第三个参数i变为0时，递归结束。第四个参数是个丑陋的把戏：它不被函数使用，而是用来调用arr.[=27的append方法=]
这绝对是最不优雅的解决方案，但也是最快的解决方案。我在下面报告 N=500 的时间。
天真的解决方案是不可行的，但在这里您可以找到一次计算一个元素的代码（这可能是您想要混合 lambda 函数和递归的方法）：
(lambda n: ((lambda fib: fib(fib,n+1))(lambda fib, i: (1 if i <= 2 else fib(fib,i-2) + fib(fib,i-1)))))(N)
@cdlane提出的解决方案：
%timeit [0, 1] + [(4<<n*(3+n)) // ((4<<2*n)-(2<<n)-1) & ((2<<n)-1) for n in range(N)][1:]
10 loops, best of 3: 88.3 ms per loop
@lehiester提出的解决方案：
%timeit [int(round((lambda n: ((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))(x))) for x in range(N)]
1000 loops, best of 3: 1.49 ms per loop
我丑陋的解决方案：
%timeit (lambda n: (lambda fib: fib(fib, [], n, None))(lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))))(N)
1000 loops, best of 3: 434 us per loop
另一个不使用递归的丑陋且更快的解决方案：
%timeit (lambda n: (lambda arr, fib_supp: [arr] + [fib_supp(arr) for i in xrange(n)])([], (lambda arr: arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2])))[0])(N)
1000 loops, best of 3: 346 us per loop
更新
我终于找到了一种优雅的方式来表达单行函数。想法总是一样的，只是使用 setitem 方法而不是 append。我使用的一些技巧可以在这个 link 中找到。这种方法只是有点慢，但至少是可读的：
%timeit (lambda n: (lambda arr, fib_supp: any(fib_supp(i, arr) for i in xrange(2,n)) or arr)([1] * n, (lambda i, arr: arr.__setitem__(i,(arr[i-1]+arr[i-2])))))(N)
1000 loops, best of 3: 385 us per loop
lambda 演算通过 Python
因为这是用 lambda-calculus 标记的，而不是写一个依赖于 python 特有的巧妙技巧或语言功能的答案，我是只会使用简单的 lambdas
U = lambda f: f (f)
Y = U (lambda h: lambda f: f (lambda x: h (h) (f) (x)))
loop = Y (lambda recur: lambda acc: lambda a: lambda b: lambda n:
acc if n == 0 else
recur (acc + [a]) (a + b) (a) (n - 1))
fibonacci = loop ([]) (0) (1)
print (fibonacci (10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
当然，我们使用了四个 named lambdas U、Y、loop 和 fibonacci——因为每个 lambdas是一个纯函数，我们可以用它的值
# in Y, replace U with its definition
Y = <b>(lambda f: f (f))</b> (lambda h: lambda f: f (lambda x: h (h) (f) (x)))
# in loop, replace Y with its definition
loop = <b>(lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x)))</b> (lambda recur: lambda acc: lambda a: lambda b: lambda n:
acc if n == 0 else
recur (acc + [a]) (a + b) (a) (n - 1))
# in fibonacci, replace loop with its definition
fibonacci = <b>(lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
acc if n == 0 else
recur (acc + [a]) (a + b) (a) (n - 1))</b> ([]) (0) (1)
fibonacci 现在是一个单一的纯表达式——我们可以在 print 语句中直接调用 lambda...
# in print, replace fibonacci with its definition
print (<b>(lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
acc if n == 0 else
recur (acc + [a]) (a + b) (a) (n - 1)) ([]) (0) (1)</b> (10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
再次使用另一个程序
我写了一个非常
再一次，用另一种语言
我们将在 JavaScript 中再次完成整个操作。 JS 更适合演示 这个练习，因为我们可以在浏览器中显示这里的代码，而且 lambda 语法更宽松（在代码格式方面）——除此之外，你会发现程序几乎是一样的
const U = f =>
f (f)
const Y =
U (h => f => f (x => h (h) (f) (x)))
const loop = Y (recur => acc => a => b => n =>
n === 0
? acc
: recur (acc.concat ([a])) (a + b) (a) (n - 1))
const fibonacci =
loop ([]) (0) (1)
console.log (fibonacci (10))
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
// 在 Y 中，用它的定义替换 U
Y = <b>(f => f(f))</b> (h => f => f (x => h(h) (f) (x))) // 在循环中，用它的定义替换 Y
loop = <b>(f => f (f)) (h => f => f (x => h (h) (f) (x)))</b> (recur => acc => a => b => n =>
n === 0
？ acc
: 重复 (acc.concat ([a])) (a + b) (a) (n - 1))
// 在斐波那契中，用它的定义替换循环
斐波那契 = <b>(f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
n === 0
？ acc
: 重复 (acc.concat ([a])) (a + b) (a) (n - 1))</b> ([]) (0) (1)
fibonacci 现在是一个单一的纯表达式——我们可以在 console.log 语句中直接调用 lambda...
oh and it's really fast, too
console.time ('fibonacci (500)')
console.log ((f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
n === 0
? acc
: recur (acc.concat ([a])) (a + b) (a) (n - 1)) ([]) (0) (1) (500))
console.timeEnd ('fibonacci (500)')
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 490 more items ]
// fibonacci (500): 3 ms
熟能生巧
lambda 演算一直是我的 favourite areas of study. With just the Y-combinator alone, I've spent countless hours exploring its beauty and sophistication。我希望这些探索对您有所帮助。如果您对主题有任何其他问题，请不要害羞地问^_^