SML -

Question

をインタリーブ双方向無限と有限シーケンスIは、データ型や関数の次の宣言をしている：

datatype direction = Back | Forward 
datatype 'a bseq = bNil | bCons of 'a * (direction -> 'a bseq) 

fun bHead (bCons (x, _)) = x 
    | bHead bNil = raise EmptySeq 

fun bForward(bCons(_, xf)) = xf Forward 
    | bForward bNil = raise EmptySeq 

fun bBack (bCons (_, xf)) = xf Back 
    | bBack bNil = raise EmptySeq 

fun intbseq k = 
    let fun go Forward = intbseq (k+1) 
     | go Back = intbseq (k-1) 
    in bCons (k, go) end 

は次の機能がそのような二つの配列インタリーブするために私が書いている：最初のseqが... ,1,2,3,4,5, .....ある場合 をし、

... ,3,-1,4,0,5,1,6,2,7,3, ...... 

コード：

第二は、そのインタリービングの新しいsequanceがある ...,5,6,7,8,9,... です

fun binterleaving_aux _ bNil yq = yq 
    | binterleaving_aux _ xq bNil = xq 
    | binterleaving_aux firstb (bCons(x,xf)) (bCons(y,yf)) = 
    bCons(x, fn dir => 
     if dir = Forward 
     then binterleaving_aux true (bCons (y, yf)) (xf dir) 
     else if firstb 
      then binterleaving_aux false (yf dir) (xf dir) 
      else binterleaving_aux false (bCons (y,yf)) (xf dir))); 

fun binterleaving bseq1 bseq2 = binterleaving_aux true bseq1 bseq2; 

そしてそのexmapleのために：

binterleaving (intbseq 5) (intbseq 1); 
bForward(it); 
bForward(it); 
bForward(it); 
bForward(it); 
bBack(it); 
bBack(it); 
bBack(it); 
bBack(it); 

それは2つの無限シーケンスのための偉大な作業をされています。

問題は、少なくとも1つが有限である場合です。 exmapleについては

私がしなければ：私は戻っている場合、最初に私が前方に移動したときに、私は彼らにエーテルを失い、戻った場合

binterleaving (bCons(10, fn dir => bCons((9, fn dir => bNil)))) (intbseq 5); 
bForward(it); 
bForward(it); 
bForward(it); 
bForward(it); 
bBack(it); 
bBack(it); 
bBack(it); 
bBack(it); 

私は10と9、反対を失います。

結果は、呼び出しの順序である：

val it = bCons (10,fn) : int bseq 
val it = bCons (5,fn) : int bseq 
val it = bCons (9,fn) : int bseq 
val it = bCons (6,fn) : int bseq 
val it = bCons (7,fn) : int bseq 
val it = bCons (6,fn) : int bseq 
val it = bCons (5,fn) : int bseq 
val it = bCons (4,fn) : int bseq 
val it = bCons (3,fn) : int bseq 

、正しい結果は次のようになります。

val it = bCons (10,fn) : int bseq 
val it = bCons (5,fn) : int bseq 
val it = bCons (9,fn) : int bseq 
val it = bCons (6,fn) : int bseq 
val it = bCons (7,fn) : int bseq 
val it = bCons (6,fn) : int bseq 
val it = bCons (9,fn) : int bseq 
val it = bCons (5,fn) : int bseq 
val it = bCons (10,fn) : int bseq 

私は何をすべきコードの変更なので、それはなります関数の動作？

Answer 1

問題は、少なくとも1つが有限である場合です。

binterleaving (bCons(10, fn dir => bCons((9, fn dir => bNil)))) (intbseq 0) 

あなたの有限のシーケンスがどのようにそれを元の値に取得することになっている？、bNilに減少し無限のシーケンスと有限シーケンスをインターリーブするセマンティクスは、あまり定義されていないようです。

つまり、有限のものが終わり、無限のものが続くとき、無限のシーケンスに沿って保存された参照は、どこで有限のものが逆に再び始まるのですか？

上記の例を取ると（私の怠惰な表記を許して）いくつかの手順、それを評価：

binterleaving (bCons(10, fn dir => bCons((9, fn dir => bNil)))) (intbseq 0) 
⇒ binterleaving (bCons(10, fn dir => bCons((9, fn dir => bNil)))) 
       (bCons(0, fn dir => ...intbseq (+/- 1)...)) 
⇒ binterleaving_aux true (bCons(10, fn dir => bCons((9, fn dir => bNil)))) 
         (bCons(0, fn dir => ...intbseq (+/- 1)...)) 
⇒ bCons (9, fn dir => 
     if dir = Forward 
     then binterleaving_aux true (bCons (0, fn dir => ...intbseq (+/- 1)...)) 
            ((fn dir => bNil) dir) 
     else ...) 

最も外側fnにForwardを適用することにより、一度この評価が得られます。

bCons (9, (fn dir => ...) Forward) 
⇒ bCons (9, binterleaving_aux true (bCons (0, fn dir => ...intbseq (+/- 1)...)) 
            ((fn dir => bNil) dir)) 
⇒ bCons (9, binterleaving_aux true (bCons (0, fn dir => ...intbseq (+/- 1)...)) bNil) 
⇒ bCons (9, bCons (0, fn dir => ...intbseq (+/- 1)...)) 

をこの時点で、逆方向に進むことができる任意の関数内に有限シーケンス9の痕跡が存在しない。 binterleavingの初期戻り値でのみ。

この修正は、主にbinterleavingの基本ケースにあり、有限シーケンスを捨てます。むしろ、空のシーケンスを空ではないシーケンスでインターリーブした結果は、空でないシーケンスでなければなりません。空のシーケンスがの前にあればそれを返します。の前に空があります（空でも、空の）。

リストには、怠け者zipperという双方向シーケンスが表示されます。 Learn You a Haskellの書籍は、読む価値があるかもしれないchapter on tree zippersを持っています。この章の用語では、「ブレッドクラム・トレイル」を返す関数が必要な場合があります。リストジッパーは概念的には少しシンプルですが、怠惰である'a bseq'が構文的にはそうではありません。