問題タブ [applicative]

より完全な問題のために編集されました：

以前のパーサーの結果を取得し、結果に特定のコンストラクターが含まれている場合に条件付きで失敗するパーサー (私は uu​​-parsinglib を使用しています) を作成したいと思います。

これはモナドパーサーでなければならないことに気づきました。

非直接左再帰を含む文法があります。以下に問題を示しますが、現実はもう少し複雑です。

ほとんどの場合、私はフィールドのみに関心があり、後戻りを最小限に抑えるために、そのケースに焦点を当てるのが最善です。

役立つ演算子を定義しました

そして、私は次のように問題に取り組みます。

左の関連付けを維持しながら、初期フィールドを渡すことができる pChainl のバリアントを定義したことに注意してください。

私が定義したい質問

pField に関しては、右端の Field コンストラクターが Field_A でない場合にポスト フィルターが失敗します。正しく指摘されているように、これはモナド解析です。uu-parsinglib をモナド パーサーとして使用する説得力のある例を見つけることができないので、提案されたアプローチは何でしょうか?

間違ったツリーを吠えている場合は、それもお知らせください。

次のタイプの関数が必要です。

例えば

を無視することを除いて、catMaybes :: [Maybe a] -> [a]inと似ていますが、 myは について非常に深刻です。(以下に示すように) 素朴な方法で実装することもできますが、もっと慣用的な方法 (「アプリケーション ファンクター」など) があるかどうか疑問に思っています。Data.MaybecatMaybesNothingfNothingf

また

Functorandのような抽象化を使用することでコードが恩恵を受ける状況に遭遇しましたApplicativeが、種類は(* -> *) -> *. 高カインド ファンクターの定義は、次のRankNTypesように行うことができます

しかし、より高い種類の のバージョンはApplicative少しトリッキーです。これは私が思いつくことができる最高のものです：

:->kind の関数を持つにはラッパー型が必要ですが、これでは、通常の Applicative の場合の* -> *ように、関数アプリケーションを適切に連鎖させることはできません。などのヘルパーで管理できます<$><*>

しかし、任意のアリティの関数を「持ち上げる」ための一般的な方法があると便利です。

上記のインスタンスを使用する簡単な例:

だから、私の質問は:上記の型クラスは何と呼ばれ、それらはハックのいくつかのライブラリによってすでに提供されていますか? Functor2グーグルで私はinlinear-mapsとHFunctorinを思いつきましたmulti-recが、どちらも私が必要としているものを正確にはしません。

HApplicativeまた、ラッパーなしで書く方法:->や、関数のリフティングを容易にする他の方法はありますか?

序章

Scala のFuture( 2.10で新しく、現在は 2.9.3 ) はアプリカティブ ファンクターです。これは、トラバース可能な type がある場合、と 関数Fを取り、それらを に変換できることを意味します。F[A]A => Future[B]Future[F[B]]

この操作は、標準ライブラリで として利用できますFuture.traverse。Scalaz 7は、ライブラリからtraverseapplicative functor インスタンスをインポートする場合に使用できる、より一般的なものも提供します。Futurescalaz-contrib

traverseストリームの場合、これら 2 つのメソッドの動作は異なります。標準ライブラリのトラバーサルは、返す前にストリームを消費しますが、Scalaz のトラバーサルはすぐにフューチャーを返します:

Leif Warnerがここで観察しているように、別の違いもあります。標準ライブラリtraverseはすべての非同期操作をすぐに開始しますが、Scalaz は最初の操作を開始し、それが完了するのを待ち、2 番目を開始し、それを待つというように続きます。

ストリームの異なる動作

ストリームの最初の値に対して数秒間スリープする関数を作成することで、この 2 番目の違いを示すのは非常に簡単です。

Future.traverse(Stream(1, 2))(toFuture)次のように出力されます。

そして Scalaz バージョン ( Stream(1, 2).traverse(toFuture)):

これはおそらく、私たちがここで望んでいるものではありません。

リストの場合は？

不思議なことに、この 2 つのトラバーサルは、リスト上でこの点で同じように動作します — Scalaz は、1 つの Future が完了するのを待たずに、次の Future を開始します。

もう一つの未来

Scalaz には、独自の Futureconcurrent実装を備えた独自のパッケージも含まれています。上記と同じ種類のセットアップを使用できます。

そして、ストリームと同様にリストのストリームでの Scalaz の動作を取得します。

それほど驚くことではないかもしれませんが、無限ストリームをトラバースしてもすぐに戻ります。

質問

この時点で、要約する表が本当に必要ですが、リストで行う必要があります。

• 標準ライブラリ トラバーサルを使用したスト​​リーム: 戻る前に消費します。それぞれの未来を待たないでください。
• Scalaz traversal を使用したスト​​リーム: すぐに戻ります。それぞれの未来が完了するのを待ちます。
• ストリームを持つ Scalaz の先物: すぐに戻る; それぞれの未来が完了するのを待ちます。

と：

• 標準ライブラリ トラバーサルを含むリスト: 待つ必要はありません。
• Scalaz traversal を使用したリスト: 待つ必要はありません。
• リスト付きの Scalaz フューチャー: 各フューチャーが完了するまで待ちます。

これは意味がありますか？リストとストリームに対するこの操作の「正しい」動作はありますか? 「最も非同期的な」動作、つまり、戻る前にコレクションを消費せず、各 Future が完了するのを待ってから次の Future に進むことをここで表現しない理由はありますか?

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]。インスタンスを見てみましょう:

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

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

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

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

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

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

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

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

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

ひどいタイトルでごめんなさい。である型をラップするApplicativeためのインスタンスを作成しようとしています。MonadMonoid

これは機能しません。GCHi は次のように訴えます。

上に書いたことは意味をなさないかもしれないことを理解しています。コンテキストは次のとおりです。論文A pattern for most compositional functions でcompos説明されているように、抽象化を使用しようとしています。このツリーを取得します ( の GADT バージョンを使用して、大幅に簡略化しました):compos

ツリーをたどり、エラーのリストまたは文字列のセットを返す関数をたくさん書きますが、下に行くときに状態 (バインド環境など) も必要とします。たとえば、次のようになります。

composFoldM構造を利用するcomposことで、これらはすべて抽象化できるはずだと思います(Monad m, Monoid o) => m o。そのため、論文の 575/576 ページにある の GADTApplicativeバージョンで使用します。この構造のインスタンスを作成する必要があると思います。どうすればいいですか？それとも、完全に間違った道を進んでいますか?composApplicative

Applicativeあるディスカッションで、一部のパーサーのインターフェースは、それらのインターフェースよりも効率的に異なる方法で実装されていると聞きましたMonad。その理由は、Applicative効果的な計算全体が実行される前に、すべての「効果」が事前にわかっているためです。モナドでは、効果は計算中の値に依存する可能性があるため、この最適化は不可能です。

これについては、いくつかの良い例を見てみたいと思います。これは非常に単純なパーサーでも別のモナドでもかまいませんが、それは重要ではありません。重要なことは、そのようなモナドのインターフェースがとApplicativeに準拠しているということですが、 を使用するとより効率的なコードが生成されます。returnapApplicative

更新:明確にするために、ここでは、モナドにならないアプリケーションには興味がありません。問題は、その両方であるということです。

使用するとき、Data.Traversable私は頻繁に次のようなコードを必要とします

構造を横断し、何らかの状態によって駆動される新しい構造を構築します。そして、型署名パターンに気づき、次のように一般化できると信じています

しかし、 、 、、およびだけtraverseで はこれを実装できません。たぶん、より強い型クラスの制約が必要ですか? ここは絶対に必要ですか？sequenceAfmap<*>pureMonad

アップデート

具体的には、適用される直観の法則の一部で機能fmapInnerする aを定義できるかどうかを知りたいです(法則がどうあるべきかはまだわかりません) 。したがって、 for s の実装は簡単です。fTraversable tfMonadMonad

アップデート

素晴らしい答えをありがとう。私は自分traverseFがちょうどであることがわかりました

Monad.State を明示的に使用せずに、すべてのペアを反転させます。以前はそうだと思っていましたmapAccumRが、実際にはmapAccumLのように動作しtraverseFます。

に一般化する方法と同様にhoistFree、無料パッケージからに一般化しました。hoistFreeMfmapData.Traversable.mapM

Applicativeただし、 に一般化する方法と同様に、任意の で動作するようにさらに一般化Data.Traversable.mapMする方法はないと思いますData.Traversable.traverse。私は正しいですか？もしそうなら、なぜですか？