Haskell在列表理解中的无限递归 [英] Haskell infinite recursion in list comprehension

问题描述

我试图定义一个接受点（x，y）作为输入的函数，并返回一个与递归调用相对应的无限列表

I am trying to define a function that accepts a point (x,y) as input, and returns an infinite list corresponding to recursively calling

P =（u ^ 2 - v ^ 2 + x，2uv + y）

P = (u^2 − v^2 + x, 2uv + y)

u和v的初始值都是0。

The initial values of u and v are both 0.

• 第一个电话会是
  

• The first call would be

p =（0 ^ 2 - 0 ^ 2 + 1,2（0）（0）+ 2）=（1,2）

然后那个结果元组（1,2）将是u和v的下一个值，那么它将是

Then that resulting tuple (1,2) would be the next values for u and v, so then it would be

P =（1 ^ 2 - 2 ^ 2 + 1,2（1）（2）+ 2）=（ - 2,6）

P = (1^2 - 2^2 + 1, 2(1)(2) + 2) = (-2,6)

等等。

我试图弄清楚如何在Haskell中进行编码。这是我到目前为止：

I'm trying to figure out how to code this in Haskell. This is what I have so far:

o :: Num a =>(a,a) -> [(a,a)]
o (x,y) = [(a,b)| (a,b)<- [p(x,y)(x,y)]]   
  where p(x,y)(u,v) = ((u^2)-(v^2)+x,(2*u*v)+y)

我真的不知道做这个工作。任何帮助，将不胜感激！

I'm really not sure how to make this work. Any help would be appreciated!

推荐答案

让我们首先忽略您的确切问题，并专注于让循环工作。基本上，你想要的东西有一些初始值 iv （即（0，0）为（u，v）），并返回列表

Let's first ignore the exact question you have, and focus on getting the loop working. What you want, essentially, is to have something that takes some initial value iv (namely, (0, 0) for (u, v)), and returns the list

f iv : f (f iv) : f (f (f iv)) : f (f (f (f iv))) : ...

对于某些函数 f （从 p 和（x，y））。而且，您希望结果重用列表中先前计算的元素。如果我自己写一个这样做的函数，它可能会像这样（但也许有一些不同的名字）：
$ b

for some function f (constructed from your p and (x, y)). Moreover, you want the result to reuse the previously computed elements of the list. If I would write a function myself that does this, it might looke like this (but maybe with some different names):

looper :: (a -> a) -> a -> [a]
looper f iv = one_result : more_results
  where
    one_result   = f iv
    more_results = looper f one_result

但是，当然，我会先查看是否存在该类型的函数。它的确如此：它被称为 Data.List.iterate 。它唯一错误的是列表的第一个元素是 iv ，但是可以通过使用 tail iterate 将永远生成一个无限列表）。

But, of course, I would first look if a function with that type exists. It does: it's called Data.List.iterate. The only thing it does wrong is the first element of the list will be iv, but that can be easily fixed by using tail (which is fine here: as long as your iteration function terminates, iterate will always generate an infinite list).

现在让我们回到您的案例。我们确定它通常看起来像这样：

Let's now get back to your case. We established that it'll generally look like this:

o :: Num a => (a, a) -> [(a, a)]
o (x, y) = tail (iterate f iv)
  where
    f (u, v) = undefined
    iv = undefined

正如您所指出的，（u，v）是（0,0），所以这就是我们对 iv 的定义。 f 现在必须用（x，y） p c>来自 o 的参数，以及该迭代的（u，v）：

As you indicated, the initial value of (u, v) is (0, 0), so that's what our definition of iv will be. f now has to call p with the (x, y) from o's argument and the (u, v) for that iteration:

o :: Num a => (a, a) -> [(a, a)]
o (x, y) = tail (iterate f iv)
  where
    f (u, v) = p (x, y) (u, v)
    iv = (0, 0)
    p = undefined

：从 o 的定义中的（x，y）实际上在其中 -clause。你甚至可以决定合并 f 和 p ，最后加上

It's as simple as that: the (x, y) from o's definition is actually in scope in the where-clause. You could even decide to merge f and p, and end up with

o :: Num a => (a, a) -> [(a, a)]
o (x, y) = tail (iterate p iv)
  where
    iv = (0, 0)
    p (u, v) = (u^2 - v^2 + x, 2 * u * v + y)

---

另外，我可以建议你为你的应用程序使用 Data.Complex 吗？这使得对 a 的限制更严格一些（因为 Num，您需要 RealFloat a .signum ），但在我看来，它使您的代码更易于阅读： $ b

---

Also, may I suggest that you use Data.Complex for your application? This makes the constraints on a a bit stricter (you need RealFloat a, because of Num.signum), but in my opinion, it makes your code much easier to read:

import Data.Complex
import Data.List (iterate)

{- ... -}

o :: Num (Complex a) => Complex a -> [Complex a]
o c = tail (iterate p iv)
  where
    iv = 0  -- or "0 :+ 0", if you want to be explicit
    p z = z^2 + c

这篇关于Haskell在列表理解中的无限递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！