Haskell infinite recursion in list comprehension

问题:

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)

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)

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

and so on.

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!

回答1:

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

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

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

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

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)

---

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

回答2:

You want:

1. To construct a list [(u, v)] with the head of this list equal (0, 0)
2. And then map this list with the function \(u, v) -> (u^2 - v^2 + x, 2 * u * v + y), appending results of this function to the list.

We can write this function as described:

func :: (Num t) => (t, t) -> [(t, t)]
func (x, y) = (0, 0) : map functionP (func (x, y))
    where functionP (u, v) = (u^2 - v^2 + x, 2 * u * v + y)

GHCi > take 5 $ func (1, 2)
     > [(0,0),(1,2),(-2,6),(-31,-22),(478,1366)]