16

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

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] 等重写它。有没有更清洁的方法呢？

4

4 回答 4

12

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]
于 2011-08-21T21:46:30.723 回答
4

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

这是使用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上面的规范。

于 2011-08-21T22:28:51.237 回答
2

使用CodeCatalogdiagonal中的代码段：

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
于 2011-08-22T07:26:00.903 回答
1

捎带哈马尔的回答：他的方法似乎很容易扩展到更高的维度：

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)]
于 2011-08-22T01:28:36.167 回答