Haskell无限列表的笛卡尔积

Question

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

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

当我检查输出时，似乎我得到的是 [0, e2, 2*e2,...] （即 x 从不超过0）。如果我考虑如何编写这个列表推导的代码，这种情况似乎很有道理。

我编写了一些代码来从原点扩展“壳层”（首先是范数为0的整数，然后是范数为1的整数，然后是范数为2的整数...），但这有点烦人，并且仅适用于Z^2 - 我必须为Z^3或Z[i]等重写它。是否有更简洁的方法来做到这一点？

- Xodarap

---

这就像是展示有理数是可数的。不要按照 (1,1), (1,2), (1,3), ..., (2,1), ... 这样的方式，因为这样永远无法到达第二行，而是按照固定的和递增：(1,1); (1,2), (2,1); (1,3), (2,2), (3,1); ... - Kerrek SB

@Kerrek SB：谢谢，这就是我所说的“扩展壳”的意思。我只是想知道是否有一种 Haskell 的方法来实现它。 - Xodarap

我不懂 Haskell，但在 C 语言中，它将是一个双重循环：for (sum = 1; ; ++sum) for (i = 1; i < sum; ++i) print (i, sum - i); - Kerrek SB

在 Haskell 中：[(x, s-x) | s <- [0..], x <- [0..s]] 的意思是生成一个无限长的列表，其中每个元素都是二元组 (x, s-x)，满足 s 从 0 开始递增，x 在 0 到 s 之间取值。 - hammar

@hammar：谢谢 - 令人惊讶的自我描述 :-) - Kerrek SB

Answer 1

在处理排序无限列表时，data-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]

- hammar

---

曼哈顿范数不是更高效一些吗？ ;) - Rotsor

@Rotsor：可能吧 :) 但这只是一个玩具示例，只要列表和列表头遵守该顺序，您可以使用任何排序。 - hammar

通过使用 continuation monad 和 monad comprehensions，这段代码几乎可以像原始代码一样编写：https://gist.github.com/1162126 - Sjoerd Visscher

Answer 2

你可以将你的空间看作一棵树。在树的根部，你选取第一个元素，在其子节点中选择第二个元素。

以下是使用 ListTree 包定义的树：

import Control.Monad.ListT
import Data.List.Class
import Data.List.Tree
import Prelude hiding (scanl)

infiniteTree :: ListT [] Integer
infiniteTree = repeatM [0..]

spacesTree :: ListT [] [Integer]
spacesTree = scanl (\xs x -> xs ++ [x]) [] infiniteTree

twoDimSpaceTree = genericTake 3 spacesTree

这是一棵无限的树，但我们可以以深度优先搜索（DFS）的方式枚举它：

ghci> take 10 (dfs twoDimSpaceTree)
[[],[0],[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7]]

您需要的树形排序方式在计算机科学中属于最佳优先搜索的变种，用于无限树，这里假设树节点的子节点已排序（由于子节点数量是无限的，不能像普通最佳优先搜索那样比较所有子节点）。幸运的是，这个变种已经实现了：

ghci> take 10 $ bestFirstSearchSortedChildrenOn sum $ genericTake 3 $ spacesTree
[[],[0],[0,0],[0,1],[1],[1,0],[1,1],[0,2],[2],[2,0]]

您可以使用任何您喜欢的标准来扩展您的外壳，而不是上面的sum。

- yairchu

Answer 3

使用来自CodeCatalog的diagonal代码片段：

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

diagonal :: [[a]] -> [a]
diagonal = concat . stripe
    where
    stripe [] = []
    stripe ([]:xss) = stripe xss
    stripe ((x:xs):xss) = [x] : zipCons xs (stripe xss)

    zipCons [] ys = ys
    zipCons xs [] = map (:[]) xs
    zipCons (x:xs) (y:ys) = (x:y) : zipCons xs ys

- Landei

Answer 4

借鉴Hammar的回答：他的方法似乎很容易扩展到更高的维度：

Prelude> import Data.List.Ordered
Prelude Data.List.Ordered> import Data.Ord
Prelude Data.List.Ordered Data.Ord> let norm (x,y,z) = sqrt (fromIntegral x^2+fromIntegral y^2+fromIntegral z^2)
Prelude Data.List.Ordered Data.Ord> let mergeByNorm = mergeAllBy (comparing norm)
Prelude Data.List.Ordered Data.Ord> let sorted = mergeByNorm (map mergeByNorm [[[(x,y,z)| x <- [0..]] | y <- [0..]] | z <- [0..]])
Prelude Data.List.Ordered Data.Ord> take 20 sorted
[(0,0,0),(1,0,0),(0,1,0),(0,0,1),(1,1,0),(1,0,1),(0,1,1),(1,1,1),(2,0,0),(0,2,0),(0,0,2),(2,1,0),(1,2,0),(2,0,1),(0,2,1),(1,0,2),(0,1,2),(2,1,1),(1,2,1),(1,1,2)]

- dainichi