16

次のような基底ペアからベクトル空間を生成したいと思います。

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

ただし、出力を調べると、取得しているように見えます[0, e2, 2*e2,...]（つまりx、0を超えることはありません）。このリスト内包表記を行うためのコードをどのように書くかを考えると、どのような意味がありますか。

原点から拡張する「シェル」を取得するためのコードをいくつか作成しました（最初にノルム0のint、次にノルム1、次にノルム2 ...）が、これは一種の煩わしく、Z^2に固有です-私はZ ^3やZ[i]などに書き換えます。これを行うためのよりクリーンな方法はありますか？

4

4 に答える 4

12

data-ordlistパッケージには、ソートされた無限点灯を処理するのに非常に役立ついくつかの関数があります。これらの1つは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

あなたは自分の空間を木として見ることができます。ツリーのルートで最初の要素を選択し、その子で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。

于 2011-08-21T22:28:51.237 に答える
2

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
于 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 に答える