haskell - 使用列表推导式求幂

Question

我正在尝试解决以下练习(我正在学习 Haskell):

Define x^n using a list comprehension.

我正在努力寻找解决方案。

使用递归或折叠，解决方案并不复杂(例如， foldr (*) 1 [x | c <- [1..n]] )。但是，仅使用列表理解会变得困难(至少对我而言)。

为了解决这个问题，我试图创建一个 x^n 元素的列表，然后获取长度。生成 x*n 元素的列表很容易，但我无法生成 x^n 元素的列表。

ppower x n = length [1 | p <- [1..x], c <- [1..n]]

返回给出错误结果的 x*n 元素列表。对此的任何想法将不胜感激。

Answer 1

一个自然发生的指数来自 sequence :

length (sequence [[1..x] | _ <- [1..n]])

如果你还没有看过 sequence然而，这是一个相当普遍的功能，但是
当与列表一起使用时，它的工作原理如下:

sequence [xs1, ... , xsk] = [[x1, ... xk] | x1 <- xs1, ... , xk <- xsk]

但这真的是作弊，因为 sequence是递归定义的。

如果你只想使用长度和列表理解，我认为
这可能是不可能的。这个答案的其余部分将是粗略的，我一半
希望有人证明我是错的。然而:

我们将尝试证明这样的表达式只能计算值
到 x 或 n 的某个有限幂，因此无法计算值
对于任意 x 和 n，与 x^n 一样大。

具体来说，我们通过对表达式结构的归纳表明，
任何表达式 expr 都有一个上限 ub(expr, m) = m^k 其中 m
是它使用的自由变量的最大值，k 是一个已知的有限
我们可以从表达式 expr 的结构中计算出幂。

(当我们查看整个表达式时，m 将是 max x n。)

我们对列表表达式的上限将是列表长度的边界，也将是任何一个的边界
它的元素(及其元素的长度等)。

例如，如果我们有 [x..y]我们知道 x <= m 和 y <= m，我们
知道所有元素<= m，长度也<= m。
所以我们有 ub([x..y], m) = m^1。

棘手的情况是列表理解:

[eleft | x1 <- e1, ... , xk <- ek]

结果的长度等于长度 e1 * ... * 长度 ek，所以
它的上限将是上限的乘积
e1 到 ek，或者如果 m^i 是其中的最大值，则为上限
将是 (m^i)^k = m^(i*k)。

要获得元素的边界，假设表达式 eleft 具有 ub(eleft, m') = m'^j。它可以使用 x1
... xk。如果 m^i 是这些的上限，如上所述，我们需要
取 m' = m^i 所以 ub(eleft, m) = (m^i)^j = m^(i*j)

作为整个列表推导式 e 的保守上限，我们
可以采用 ub(e, m) = m^(i*j*k)。

我真的还应该研究模式匹配的案例
(应该不是问题，因为匹配的部分小于
我们已经拥有的), let定义和函数(但我们禁止
递归，所以我们可以在开始之前完全扩展它们)，以及
列出像 [x,37,x,x,n] 这样的文字(我们可以抛出他们的长度
进入 m 作为初始可用值)。

如果无限列表像 [x..]或 [x,y..]被允许他们需要一些
想着。我们可以构造 head和 filter ，这意味着我们可以得到
从一个无限列表到它的第一个匹配谓词的元素，这看起来像是一种获得递归函数的方法。我不
认为这是一个问题，因为 1. 它们只是算术序列并且
2. 我们必须构造任何我们想要使用的数字
谓词。但我在这里不确定。