23

Haskellの2Dグリッドに関する最近の質問に触発されて、リストのリスト内の位置を追跡するために2次元ジッパーを作成できるかどうか疑問に思っています。リスト上の1次元のジッパーを使用すると、大きなリスト内でローカルに非常に効率的に移動できます（一般的な例はテキストエディターです）。しかし、次のような2番目の次元があるとしましょう。

grid = 
    [[ 1, 2, 3, 4, 5]
    ,[ 6, 7, 8, 9,10]
    ,[11,12,13,14,15]
    ,[16,17,18,19,20]
    ,[21,22,23,24,25]]

ここでグリッド内を左右だけでなく上下に効率的に移動するために、ある種のジッパーデータ構造を作成できますか？もしそうなら、リストのリストを無限のリストの無限のリストに置き換えても、効率的な移動を得ることができますか？

4

3 に答える 3

21

そうではありません。ジッパーがどのように機能するかの重要な側面の 1 つは、構造内の場所を、それに到達するために使用されるパスと、途中で作成される追加のフラグメントによって表すことです。最終的に、そのパスに沿ってバックトラックし、構造をあなたが行く。したがって、データ構造を介して使用可能なパスの性質により、ジッパーが制約されます。

場所はパスによって識別されるため、個別のパスはそれぞれ異なる場所を表すため、同じ値への複数のパスを持つデータ構造をジッパーで使用することはできません。パス。

2D 空間での任意の動きは、実際には上記の要件に適合しないため、2D ジッパーは必然的にある程度制限されると推測できます。たとえば、原点から出発し、構造物を通る道を歩いてから、その道に沿って少し戻って、たとえば他のポイントに到達します。これは、構造内の任意の点について、原点を介してのみ到達できる他の点があることも意味します。

できることは、2D 距離の概念をデータ構造に組み込むことです。これにより、構造内のパスをたどると、「下」のポイントが互いに近くなります。アイデアは、2D 空間で短い距離を移動するために平均して必要なバックトラックの量を最小限に抑えることです。これは、 2D 空間を距離で検索するのに必要なほぼ同じアプローチ(最近傍検索、効率的な幾何学的交差など) になり、同じ種類のデータ構造、つまりより高い空間を作成するための空間分割で実行できます。 -次元検索ツリー。quadtree、kd-tree 、または同様の構造のジッパーの実装は、他のツリーと同様に簡単です。

于 2012-01-18T04:39:32.600 に答える
7

次のコードのような単純なものを使用できます。テーブルは、選択した要素の一番上の行、選択した要素の一番下の行に加えて、選択した要素の左側の要素、および選択した要素の右側の要素で表されます。

効率的な移動を可能にするために、上の行と左側の要素は逆の順序で格納されます。

データ構造に「場所」を保持していても、「パス」ではないため、これがジッパーとして適格かどうかはわかりません。

-- Table sel left right top bottom
data Table a = Table a [a] [a] [[a]] [[a]] deriving Show

left :: Table a -> Table a
left tab@(Table _ [] _ _ _) = tab
left (Table sel (l:ls) rs ts bs) = Table l ls (sel:rs) ts bs

right :: Table a -> Table a
right tab@(Table _ _ [] _ _) = tab
right (Table sel ls (r:rs) ts bs) = Table r (sel:ls) rs ts bs

up :: Table a -> Table a
up tab@(Table _ _ _ [] _) = tab
up (Table sel ls rs (t:ts) bs) = Table sel' ls' rs' ts (b:bs)
  where
    (ls',(sel':rs')) = splitAt (length ls) t
    b = ls ++ (sel:rs)

down :: Table a -> Table a
down tab@(Table _ _ _ _ []) = tab
down (Table sel ls rs ts (b:bs)) = Table sel' ls' rs' (t:ts) bs
  where
    (ls',(sel':rs')) = splitAt (length ls) b
    t = ls ++ (sel:rs)

tableToList :: Table a -> [[a]]
tableToList (Table sel ls rs ts bs) = (reverse ts) ++ [ls ++ (sel:rs)] ++ bs

listToTable :: [[a]] -> Table a
listToTable [] = error "cannot make empty table"
listToTable ([]:_) = error "cannot make empty table"
listToTable ((t:tr):ts) = Table t [] tr [] ts

これは無限のリストでも機能します-

selected :: Table a -> a
selected (Table sel _ _ _ _) = sel

a :: Table Int
a = listToTable $ replicate 10 [1..]

selected a                   #=> 1
selected $ down a            #=> 1
selected $ right $ down a    #=> 2
于 2012-01-18T07:18:56.360 に答える