Haskell无限列表笛卡尔积 [英] Haskell cartesian product of infinite lists

问题描述

  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]等。有没有一种更干净的方式来做到这一点？

data-ordlist 包中有一些函数对于使用分类的无限元函数非常有用。其中之一是 mergeAllBy ，它使用一些比较函数将无限列表的无限列表结合在一起。 然后这个想法是建立列表的无限列表，使得 y 在每个列表中固定，而 x 增长。只要我们可以保证每个列表都被排序，并且列表的头部按照我们的排序排序，我们就可以得到一个合并的排序列表。

下面是一个简单的例子：

  import Data.List.Ordered 
 import Data.Ord 
 
 genFromPair（e1，e2）= mergeAllBy（比较范数）[[x。* e1 + y。* e2 | x < -  [0 ..]] | y<  -  [0 ..]] 
 
  - 其余的只是定义了一个简单的矢量类型，所以我们可以用
数据来玩Vec a = Vec aa 
派生（Eq，Show）
 
实例Num a => Num（Vec a）其中
（Vec x1 y1）+（Vec x2 y2）= Vec（x1 + x2）（y1 + y2）
  -  ... 
 
s 。*（Vec xy）= Vec（s * x）（s * y）
 norm（Vec xy）= sqrt（x ^ 2 + y ^ 2）
  

在GHCi中试试这个结果：

pre $ code > *主>取$ 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]


I want to generate a vectorspace from a basis pair, which looks something like:

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

When I examine the output though, it sems like I'm getting [0, e2, 2*e2,...] (i.e. x never gets above 0). Which sort of makes sense when I think about how I would write the code to do this list comprehension.

I wrote some code to take expanding "shells" from the origin (first the ints with norm 0, then with norm 1, then norm 2...) but this is kind of annoying and specific to Z^2 - I'd have to rewrite it for Z^3 or Z[i] etc. Is there a cleaner way of doing this?

解决方案

The data-ordlist package has some functions which are extremely useful for working with sorted infinite lits. One of these is mergeAllBy, which combines an infinite list of infinite lists using some comparison function.

The idea is then to build an infinite list of lists such that y is fixed in each list, while x grows. As long as we can guarantee that each list is sorted, and that the heads of the lists are sorted, according to our ordering, we get a merged sorted list back.

Here's a quick example:

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)

Trying this in GHCi we get the expected result:

*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]

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