Haskell无限列表的笛卡尔积

Question

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

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

当我检查输出时,它就像我得到的那样[0, e2, 2*e2,...](即x永远不会超过0).当我考虑如何编写代码来执行此列表理解时,哪种有意义.

我写了一些代码来从原点扩展"shell"(首先是0的整数,然后是norm 1,然后是norm 2 ......)但是这有点烦人且特定于Z ^ 2 - 我有为Z ^ 3或Z [i]等重写它.有更清洁的方法吗？

Answer 1

该数据ordlist封装具有一些功能,这对于与排序的无限双床工作极为有用.其中之一是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]