9

次の定義があるとします

data Book = Book {id :: Int, title :: String}
type Shelf = [Book]

私は仮説的な機能を持っていると仮定します（updは更新用です）

updShelf :: Shelf -> Shelf
updShelf all@(book : books) = updBook book : updShelf books

これまでのところすべて順調です。ここで、updateBook 関数が更新された本を 3 冊前に参照する必要があるとします。つまり、本棚の位置 5 にある本の updateBook は、位置 2 にある本を参照する必要があります (最初の 3 冊の本は、更新するためにそのような参照を必要としないと仮定します)。問題ありません、と私は言い、コードを次のように変更します。

updShelf :: Shelf -> Shelf
updShelf all@(book : books) prevBook = updBook book prevBook : updShelf books
                where prevBook = ???

私が助けを必要としているのは、 prevBook 関数です。この問題に正しい方法で取り組んでいるかどうかさえわかりませんが。したがって、この問題に別の方法でアプローチするためのより良い提案があれば、高く評価されます

編集：

Thomas M. DuBuisson: あなたの解決策は私にはうまくいきません。理由は次のとおりです。初期の棚 (すべて) の状態を次のように仮定します。

Book {id=1, title="a"}
Book {id=2, title="b"}
Book {id=3, title="c"}
Book {id=4, title="d"}
Book {id=5, title="e"}
Book {id=6, title="f"}
Book {id=7, title="g"}
Book {id=8, title="h"}

次に、(drop 3 partialUpdate) は次のとおりです (book ステートメント全体ではなく ID のみを使用):

updBook 4
updBook 5
updBook 6
updBook 7
updBook 8

zipWith' ($) (drop 3 partialUpdate) (all) は:

updBook 4 1
updBook 5 2
updBook 6 3
updBook 7 4 -> YIKES! Older version of book 4!
updBook 8 5 -> YIKES! Older version of book 5!

私の場合、更新されていないバージョンではなく、ブック 4 と 5 の既に更新されたバージョンに対してブック 7 と 8 を更新する必要があります。私が伝えたいことを理解していただければ幸いです。

4

6 に答える 6

11

このトリックは、結び目を結ぶことに関連しています。答えを計算する際に、答えを使用します。説明のために、type Book = Int代わりに を使用します。

updateShelf :: Shelf -> Shelf
updateShelf shelf = answer where
   answer  = zipWith updateBook shifted shelf
   shifted = replicate 3 Nothing ++ map Just answer

-- some stupid implementation just for illustration
updateBook :: Maybe Book -> Book -> Book
updateBook Nothing          current = current + 1
updateBook (Just threeBack) current = current + threeBack + 1

では、が更新されたバージョンを実際に使用しているghciことを確認できます。updateShelf

*Main> updateShelf [1,10,100,1000,10000]
[2,11,101,1003,10012]

ご覧のとおり、最初の 3 つは1+1、10+1、および100+1であり、残りの 2 つは1000+(1+1)+1および10000+(10+1)+1です。したがって、期待どおり、更新された以前の値を使用しています。

于 2012-08-27T17:22:13.390 に答える
6

ここで結ばれる結び目はなく、情報の逆流も、まだ定義されていない値への前方参照の受け渡しもありません。それどころか、すでに計算されている既知の値を参照します。遅延評価なしでも機能します。これ：

updShelf shelf@(a : b : c : t) = xs where
   xs = a : b : c : zipWith updBook t xs

は、あなたが必要とすることすべてです。それが「行っている」ことは、生成されているシーケンスへの明示的なバックポインターを維持することだけであり、3 ノッチ戻ります。「バックポインターは簡単です」 、結び目を結ぶことに関するhaskellwiki のページを引用します。

の各呼び出しは、updBookここで 2 つの引数を受け取ります。1 つi+3は元のリスト内の位置にある項目で、もう 1 つは位置にある新しく更新された項目iです。

次の Haskell 伝承と比較してください。

g (a,b) = xs where
   xs = a : b : zipWith (+) xs (tail xs)

ここでも結び目はありません。

于 2012-08-28T07:14:20.167 に答える
5

まず、あなたupdShelfはmap updBookです。

2番目:リストはランダムアクセス操作をサポートしていないため、本のリストは問題に最適なデータ構造ではない可能性があると思います。計算の任意の時点で本当にランダム アクセスが必要な場合は、配列を使用してみてください。「 」を参照してくださいData.Array。

ここで私の要点を説明します。あなたが行おうとしている種類のこと、つまり、それ自体の結果の一部を消費する計算を行うことは、Haskell コミュニティでは「結び目を結ぶ」または「クレジット カード変換」という名前で頻繁に言及されます。 」 (今すぐ購入し、後で支払います)。基本的に、次のような式が Haskell で有効であるという事実に要約されます。

let result = f result in result  -- apply f to its own result

それはどのように機能するのでしょうか？まず第一に、ご存じのとおり、Haskell はレイジーなので、そのような計算は必ずしも循環的ではありません。第二に、それはどんな計算でも機能しません。計算のサブステップを実行できる非円形の終了順序が必要です。

たとえば、この関数はtoの結果を追加することでからcycle循環リストを作成します:xscycle xsxs

cycle xs = let result = xs ++ result in result

「結び目を結ぶ」パターンは、ライブラリ関数fixで抽象化できます。ここでは、その使用方法とともに示します。

fix f = let result = f result in result
cycle xs = fix (xs++)

したがって、あなたの場合、私がお勧めするのは次のとおりです。

  • ArrayShelf を表すには(Haskell の組み込み型のような) 遅延配列を使用します。これにより、要素へのランダム アクセスが可能になります。
  • Array計算中に結果を参照するには、ノットタイイング手法を使用します。
于 2012-08-27T17:32:01.683 に答える
2

わかりました、これを実現するための柔軟な方法は次のとおりです。

updateOne book = undefined
updateTwo prevUpdatedBook book = undefined

updateBooks books = answer
  where numEasy = 3
        (easy,hard) = splitAt numEasy books
        answer = mapOnto updateOne easy (zipWith updateTwo answer hard)

-- More efficient that (map f xs ++ end)
mapOnto f xs end = foldr ((:) . f) end xs
于 2012-08-27T17:26:11.883 に答える
2

これは 2 つの部分で行うことができます。最初に updBook をすべての本に部分的に適用し、関数のリストを作成してから、zip を介して適切な前の本にこれらの各関数を適用します。

updShelf :: Shelf -> Shelf
updShelf [] = []
updShelf all@(book:books) = 
    let partialUpdate = map updBook all :: Book -> Shelf
    in zipWith ($) (drop 3 partialUpdate) all

updBook :: Book -> Book -> Shelf
updBook = undefined

これは開始時に奇妙な動作をしていることに注意してくださいdrop 3。. それは必須ではありません。その行を readzipWith ($) partialUPdate (drop (len-3) (cycle all))にすることもできますが、前の本がないリストの先頭で何が起こるかを指定していません。

于 2012-08-27T15:36:47.030 に答える
2

再帰関数として、updShelf渡されていない要素にアクセスすることはできません (したがって、 で始まるリストを取得した場合bookFive、bookThree.

関数を再帰的に書きたい場合は、さらにパターン マッチングを行う必要があります。

updShelf :: Shelf -> Shelf
updShelf (bookOne : bookTwo: bookThree : books) 
    = (updBook bookOne bookThree) : (updShelf $ bookTwo : bookThree : books)

updBook :: Book -> Book -> Shelf
updBook twoEarlier current = {- undefined -}
于 2012-08-27T16:20:37.510 に答える