ハスケルの2次元グリッドに関する最近の質問からインスピレーションを得て、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]]
は、我々は効率的にだけでなく、左と右が、アップして、ここで、グリッド内の下に移動するジッパーデータ構造のいくつかの種類を作成することができます。しかし、我々はこのような二次元を持っていると言うことができますか？そうであれば、リストのリストを無限リストの無限リストで置き換えると、効率的な動きを得ることができますか？
なしかなり、いいえ。ジッパーの機能の重要な点の1つは、構造に含まれる場所を、それに到達するために使用されたパスと途中で作成された余分なフラグメントによって表し、その結果としてそのパスに戻って構造を再構築できるということです。あなたが行く。データ構造を介して利用可能な経路の性質は、このようにジッパーを制約する。
場所はパスで識別されるため、それぞれの個別のパスは異なる場所を表します。したがって、同じ値への複数のパスを持つデータ構造は、ジッパーでは使用できません。ルーピングパスを持つ他の構造。
2D空間での任意の動きは実際には上記の要件に適合しないため、2Dジッパーは必然的にいくらか限定されると推測できます。おそらく、起点から出発して、構造を通る道を歩き、次にその道に沿ってある距離だけ後退して、他の地点に到達するでしょう。これはまた、構造内の任意の点について、起点を介してのみ到達可能な他の点が存在することを意味する。
はになります。データ構造に2D距離の概念があるので、構造を通ってパスをたどると、下の点が互いに近くなります。 2D空間で短距離を移動するために必要なバックトラックの量を最小限に抑えることです。これは、距離 - 最近傍検索、効率的な幾何学的交差、そのようなものによって - 2D空間を検索するために必要なおおよそ同じアプローチであり、同じ種類のデータ構造、つまりspace partitioningで作成することができますより高次の探索木。 quadtree、kd-tree、または同様の構造のジッパーを実装することは、他のツリーと同様に簡単です。
まあ、次のコードのような単純なものを使うことができます。選択された要素の上の行、選択された要素の下の行、選択された要素の左にある要素、および選択された要素の右にある要素によってテーブルが表されます。
効率的な移動を可能にするために、上の行と左の要素が逆の順序で格納されます。
データ構造内に「場所」があるにもかかわらず、これが「パス」ではないため、これがジッパーとして機能するかどうかはわかりません。
-- Table sel left right top bottom
data Table a = Table a [a] [a] [[a]] [[a]] deriving Show
left :: Table a -> Table a
left [email protected](Table _ [] _ _ _) = tab
left (Table sel (l:ls) rs ts bs) = Table l ls (sel:rs) ts bs
right :: Table a -> Table a
right [email protected](Table _ _ [] _ _) = tab
right (Table sel ls (r:rs) ts bs) = Table r (sel:ls) rs ts bs
up :: Table a -> Table a
up [email protected](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 [email protected](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
これはジッパーと同じ操作を提供しますが、1つではありません。 Huetによって導入されたジッパーは、ナビゲーションステップごとに一定量の割り当てを行います。実装には、データ構造全体のサイズに依存する割り当てコストがあります。だから、これはあなたのユースケースの役に立つデータ構造かもしれませんが、わかりません。しかし、私はそれをジッパーと呼んでいません。 – jmg
ああ、意味がある...私は何を考えているのかわからない。 –
@jmg：公正であるために、これは*ジッパーである - 具体的には、ネストされたリストで動作するネストされた2つの標準リストジッパー。実際のナビゲーションステップは、内側のリストに沿って移動するか、または選択が内側のリストの最初の要素であるときに外側のリストに沿って移動しています。問題は、「上」と「下」はこのジッパーのナビゲーションの一部ではないということです。 –
「ジッパーがどのように動作するかの重要な側面の一つは、彼らはそれに到達するために使用されているパスによって構造内の位置を表していることです」。ユニークなパスをジッパーの重要な要件としているのはなぜですか？私は、データ構造内の "場所"を表すどんな方法でも十分であると考えていたでしょう。 –
@AnupamJain：再構築に使用されたフラグメントは元の不変構造の一部であるため、あなたがそれを再構築するとき、そのパスはまだ元の値を持ちます。それを処理する唯一の方法は、両方のパスを歩き回り、両方の交換を行うことです。つまり、両方のパスを「一意の」パスとみなします。 –
@AnupamJain：可能な冗長パスが多いほど、非効率性が増します。最悪のシナリオはサイクリックリストのようなもので、無限のパスがあり、各パスに構造全体が含まれているため、すべてを再構築する必要があります。 –