37

n タプルは、入れ子になった 2 タプルの束で表現できることは明らかです。では、なぜ Haskell では同じではないのでしょうか? これは何かを壊しますか？

これらの型を同等にすることで、タプルに対する関数の記述がはるかに簡単になります。たとえば、zip、zip2、zip3 などを定義する代わりに、すべてのタプルで機能する単一の zip 関数のみを定義できます。

もちろん、ネストされた 2 タプルを使用することはできますが、これは見苦しく、ネストを実行する標準的な方法はありません (つまり、左または右にネストする必要がありますか?)。

4

2 に答える 2

35

このタイプ(a,b,c,d)には、 とは異なるパフォーマンス プロファイルがあり(a,(b,(c,(d,()))))ます。一般に、n 個のタプルO(1)take へのインデックス作成は、n 個のネストされたタプルの「hlist」へのインデックス作成ではO(n).

そうは言っても、 HListsに関する Oleg の古典的な作品をチェックする必要があります。HLists を使用するには、型レベルのプログラミングを広範囲に、やや大雑把に使用する必要があります。多くの人はこれを容認できないと感じており、初期の Haskell では利用できませんでした。おそらく、現在 HList を表現する最良の方法は、GADT と DataKinds を使用することです。

data HList ls where
  Nil  :: HList '[]
  Cons :: x -> HList xs -> HList (x ': xs)

これにより、正規のネストが可能になり、この型のすべてのインスタンスに対して機能する関数を記述できます。printfzipWithで使用されているのと同じ手法を使用して、マルチウェイを実装できます。より興味深いパズルは、このタイプに適切なレンズを生成することです (ヒント: インデックスにタイプ レベルのナチュラルとタイプ ファミリを使用します)。

私は、配列を使用する HList のようなライブラリを記述し、内部でunsafeCoerceタプルのようなパフォーマンスを得ると同時に、汎用インターフェイスに固執することを検討しました。私はやったことはありませんが、それほど難しくはないはずです。

編集：これについて考えれば考えるほど、時間があれば一緒に何かをハックする傾向があります。Andreas Rossberg が言及している繰り返しコピーの問題は、おそらくストリーム フュージョンまたは同様の手法を使用して排除できます。

于 2013-02-20T07:15:14.343 に答える
23

Haskell でのこれに関する主な問題は、ネストされたタプルが遅延のために追加の値を許可することです。たとえば、型(a,(b,())には all(x,_|_)またはが含まれます(x,(y,_|_))が、これはフラット タプルには当てはまりません。これらの値の存在は、意味的に不便であるだけでなく、タプルの最適化をより困難にします。

ただし、厳密に言えば、あなたの提案は確かに可能性があります。しかし、それでもパフォーマンスの落とし穴があります: 実装は依然としてタプルを平坦化する必要があります。したがって、帰納的にそれらを実際に構築または分解する場合、それらは何度も繰り返しコピーする必要があります。非常に大きなタプルを使用すると、問題になる可能性があります。

于 2013-02-20T07:34:16.023 に答える