12

ZipListFunctorとApplicativeインスタンス ( Control.Applicative ) が付属していますが、なぜAlternativeでしょうか?

  • いい例はありませんか？
  • 以下で提案されているものはどうですか？
    • 欠陥がありますか？
    • 無駄ですか？
    • 他の合理的な可能性 ( Bool2 つの方法でモノイドになることができるなど) はありますか?したがって、どちらもインスタンスであってはなりませんか?

「インスタンスの代替 ZipList」(最初にコードを見つけるための引用符付き) を検索したところ、ライブラリ、いくつかのチュートリアル、講義ノートしか見つかりませんでしたが、実際のインスタンスは見つかりませんでした。

マット・フェンウィックはZipList A、 がモノイドになるのは が の場合だけだと言いましたA(こちらを参照)。ただし、要素の型に関係なく、リストはモノイドです。

同じ質問に対するAndrewCによるこの他の回答Alternativeでは、インスタンスがどのように見えるかについて説明しています。彼は言う

には 2 つの賢明な選択がありますZip [1,3,4] <|> Zip [10,20,30,40]。

  1. Zip [1,3,4]それは最初だから - 多分と一致する
  2. Zip [10,20,30,40]最長であるため -Zip []破棄されることと一致します

Zip基本的にはどこですかZipList。

答えは であるべきだと思いますZip [1,3,4,40]。インスタンスを見てみましょう:

instance Aternative Zip where
  empty = Zip []
  Zip xs <|> Zip ys = Zip (go xs ys) where
    go []     ys = ys
    go (x:xs) ys = x : go xs (drop 1 ys)

Zip a型引数を知らずに生成できるaのはだけZip [] :: Zip aなので、 の選択肢はほとんどありませんempty。空リストがモノイドの中立要素である場合、リスト連結を使用したくなるかもしれません。ただし、のせいでgoはありません。最初の引数リストの 1 つのエントリを使用するたびに、2 番目の引数リストからも 1 つ削除します。したがって、一種のオーバーレイがあります。左の引数リストは、右の引数リストの先頭 (またはそのすべて) を隠します。(++)drop 1

[ 1, 3, 4,40]   [10,20,30,40]   [ 1, 3, 4]   [ 1, 3, 4]
  ^  ^  ^  ^      ^  ^  ^  ^      ^  ^  ^      ^  ^  ^
  |  |  |  |      |  |  |  |      |  |  |      |  |  |
[ 1, 3, 4] |    [10,20,30,40]   []|  |  |    [ 1, 3, 4]
[10,20,30,40]   [ 1, 3, 4]      [ 1, 3, 4]   []

ziplists の背後にある 1 つの直感はプロセスです。結果の有限または無限のストリームです。Applicativezip するとき、インスタンスによって反映されるストリームを結合します。リストの最後に到達すると、ストリームはそれ以上の要素を生成しません。ここでAlternativeインスタンスが役に立ちます。デフォルトのプロセスが終了するとすぐに引き継ぐ、同時置換 (実際には代替) を指定できます。

たとえばfmap Just foo <|> pure Nothing、ziplist のすべての要素をfooaにラップするように記述してJust、Nothingその後に進むことができます。結果の ziplist は無限であり、すべての (実際の) 値が使い果たされるとデフォルト値に戻ります。Zipこれはもちろん、コンストラクター内に無限リストを追加することにより、手動で行うことができます。それでも、上記はより洗練されており、コンストラクターの知識を前提としないため、コードの再利用性が高くなります。

要素の型に関する仮定は必要ありません (モノイド自体であるなど)。同時に、定義は自明ではありません ((<|>) = constそうであるように)。最初の引数でのパターン マッチングによってリスト構造を利用します。

上記の の定義<|>は連想的であり、空のリストは実際には空の要素です。我々は持っています

Zip [] <*> xs  ==  fs <*> Zip []  ==  Zip []     -- 0*x = x*0 = 0
Zip [] <|> xs  ==  xs <|> Zip []  ==  xs         -- 0+x = x+0 = x
(fs <|> gs) <*> xs  ==  fs <*> xs <|> gs <*> xs
 fs <*> (xs <|> ys) ==  fs <*> xs <|> fs <*> ys

したがって、求めることができるすべての法則が満たされます (これは、リストの連結には当てはまりません)。

このインスタンスは、次のものと一致していますMaybe。選択は左に偏っていますが、左の引数が値を生成できない場合、右の引数が引き継がれます。機能

zipToMaybe :: Zip a -> Maybe a
zipToMaybe (Zip [])    = Nothing
zipToMaybe (Zip (x:_)) = Just x

maybeToZip :: Maybe a -> Zip a
maybeToZip Nothing  = Zip []
maybeToZip (Just x) = Zip (repeat x)

は選択肢の射 (意味psi x <|> psi y = psi (x <|> y)とpsi x <*> psi y = psi (x <*> y)) です。

編集：私が推測するsome/メソッドについてmany

some (Zip z) = Zip (map repeat z)
many (Zip z) = Zip (map repeat z ++ repeat [])
4

4 に答える 4

5

タグ/索引

面白い。完全に無関係ではない考え: ZipLists は、リスト内の (増加する) 位置インデックスによってタグ付けされた要素を持つ通常のリストと見なすことができます。圧縮アプリケーションは、同じインデックスの要素をペアにすることで 2 つのリストを結合します。

Ord (減少しない)値でタグ付けされた要素を持つリストを想像してください。Zipperyアプリケーションは、同じようにタグ付けされた要素をペアにして、すべての不一致を破棄します (用途があります)。ジッパーのような代替手段は、タグ値に対して順序を維持する左優先ユニオンを実行できます (通常のリストの代替手段も一種のユニオンです)。

これは、インデックス付きリスト (別名 ZipLists) に対して提案するものと完全に一致します。

そうです、それは理にかなっています。

ストリーム

値のリストの 1 つの解釈は非決定性です。これは、リストのモナド インスタンスと一致しますが、ZipList は、順番に結合される値の同期ストリームとして解釈できます。

このストリームの解釈では、リスト全体の観点から考えていないため、最長のストリームを選択することは明らかにごまかしであり、定義の最初の ZipList から 2 番目の ZipList へのフェールオーバーの正しい解釈は<|>、あなたのインスタンスで言うように、最初の終了時に飛行します。

2 つのリストを一緒に圧縮することは、単純に型シグネチャのためではありませんが、 の正しい解釈です<|>。

可能な限り長いリスト

2 つのリストを一緒に圧縮すると、結果は 2 つの長さの最小になります。これは、⊥ を使用せずに型シグネチャを満たす最長のリストであるためです。これを 2 つの長さのうち短い方を選ぶと考えるのは間違いです。可能な限り長い方です。

同様に<|>、可能な限り長いリストを生成し、左側のリストを優先する必要があります。明らかに、左側のリスト全体を取得し、同期/高速性を維持するために左側のリストが残っている右側のリストを取得する必要があります。

于 2013-08-13T16:42:50.603 に答える
2


あなたのインスタンスは問題ありませんが、 ( a)最長のリストを目指し、
(b)ソース リスト間で要素を混合することによって、ZipList が実行しないことを行います。

操作としての圧縮は、最短のリストの長さで停止します。

それが私の答えで結論付けた理由です：

したがって、唯一の賢明な代替インスタンスは次のとおりです。

instance Alternative Zip where
   empty = Zip []
   Zip [] <|> x = x
   Zip xs <|> _ = Zip xs

これは、Maybe の代替インスタンスと、a失敗しない場合は実行し、失敗した場合は実行する必要があると言うパーサーと一致しbています。短いリストは長いリストよりも成功率が低いと言えますが、空でないリストが完全な失敗であるとは言えません。

empty = Zip []が選択されるのは、リストの要素型で多態的でなければならず、そのようなリストは[]

バランスのために、私はあなたのインスタンスがひどいとは思いません。これはきれいだと思いますが、必要に応じて自分でロールバックしてください!

于 2013-08-13T22:10:10.243 に答える