无限列表的 Haskell 笛卡尔积

Question

我想从一个基对生成一个向量空间，它看起来像:

genFromPair (e1, e2) = [x*e1 + y*e2 | x <- [0..], y <- [0..]]

但是，当我检查输出时，似乎我得到了 [0, e2, 2*e2,...] (即 x 永远不会超过 0)。当我考虑如何编写代码来执行此列表理解时，哪种方式是有意义的。

我编写了一些代码来从原点获取扩展“shell”(首先是范数为 0 的整数，然后是范数 1，然后是范数 2 ......)，但这有点烦人，并且是 Z^2 特有的——我会有为 Z^3 或 Z[i] 等重写它。有没有更清洁的方法呢？

Answer 1

data-ordlist package 有一些函数对于处理有序的无限光照非常有用。其中之一是 mergeAllBy ，它使用一些比较函数组合了无限列表的无限列表。

然后的想法是构建一个无限列表，这样 y在每个列表中是固定的，而 x成长。只要我们能保证每个列表都是排序的，并且列表的头部是排序的，根据我们的排序，我们得到一个合并的排序列表。

这是一个简单的例子:

import Data.List.Ordered
import Data.Ord

genFromPair (e1, e2) = mergeAllBy (comparing norm) [[x.*e1 + y.*e2 | x <- [0..]] | y <- [0..]]

-- The rest just defines a simple vector type so we have something to play with
data Vec a = Vec a a
    deriving (Eq, Show)

instance Num a => Num (Vec a) where
    (Vec x1 y1) + (Vec x2 y2) = Vec (x1+x2) (y1+y2)
    -- ...

s .* (Vec x y) = Vec (s*x) (s*y)     
norm (Vec x y) = sqrt (x^2 + y^2)

在 GHCi 中尝试这个，我们得到了预期的结果:

*Main> take 5 $ genFromPair (Vec 0 1, Vec 1 0)
[Vec 0.0 0.0,Vec 0.0 1.0,Vec 1.0 0.0,Vec 1.0 1.0,Vec 0.0 2.0]