コンテナのように見えないFoldableまたはTraversableインスタンスはありませんか？

Question

コンテナ（リスト、シーケンス、マップなど）のように見えるファンクタはたくさんありますが、それ以外の多くのファンクタ（状態変換器、IO、パーサなど）はありません。私はまだ少なくともFoldableまたはTraversableのインスタンスはコンテナのようには見えませんでした。存在しますか？そうでない場合、私は彼らがなぜできないのかをよりよく理解したいと思う。

Answer 1

すべての有効なTraversable fは

data Normal (s :: Nat -> *) (x :: *) where -- Normal is Girard's terminology 
    (:-) :: s n -> Vec n x -> Normal s x 

data Nat = Zero | Suc Nat 

data Vec (n :: Nat) (x :: *) where 
    Nil :: Vec Zero n 
    (:::) :: x -> Vec n x -> Vec (Suc n) x 

一部s :: Nat -> *ためNormal sと同型であるが、それはHaskellでISOを実装することで、すべての些細なことではないのです（しかし、それは完全な依存型で行く価値があります）。道徳的に、あなたが選ぶsは

data {- not really -} ShapeSize (f :: * -> *) (n :: Nat) where 
    Sized :: pi (xs :: f()) -> ShapeSize f (length xs) 

及びイソ分離して再結合形状や内容の二つの方向です。物の形はちょうどfmap (const())で与えられ、重要な点はf xの形の長さはf xの長さであるということです。

ベクトルは、左から右へ1回ずつ移動する方向に移動可能です。法線は、形状（したがってサイズ）を保持し、要素のベクトルを横切ることによって正確に移動可能です。トラバーサブルであることは、有限個の要素位置を線形の順序で並べることです。通常のファンクタへの同形は、要素を線形の順序で正確に公開します。これに対応して、構造体は全て、形状とサイズのセットと、サイズよりも厳密に小さい自然数の最初のセグメントによって与えられる位置の対応する概念を持っています。

Foldableものも有限演算であり、彼らは（賢明なtoListがある）の順序で物事を保つが、それらはFunctor秒であることが保証されていないので、彼らは形状のようにさわやかな概念を持っていません。その意味では（私の同僚のAbbott、Altenkirch、Ghaniによって定義された "コンテナ"の意味）、彼らは必ずしも形状と位置の特徴付けを認めないので、容器ではありません。あなたが運が良ければ、それらのうちのいくつかはいくつかの商のための容器かもしれません。確かにFoldableは内部構造が秘密であることを意図したSetのような構造の処理を可能にするために存在し、トラバース操作によって必ずしも尊重されない要素に関する情報の順序付けに依存する。Foldableが正しく動作するかどうかは疑いがありますが、私はそのライブラリ設計の選択肢の実用的な利点については考えませんが、より明確な仕様を望むことができます。

Answer 2

まあ、universeの助けを借りて、有限状態空間上の状態変圧器のインスタンスをFoldableとTraversableと書くことができます。この考え方は、関数のためにFoldableとTraversableのインスタンスにほぼ似ています。Foldableの関数をどこでも実行し、Traversableのルックアップテーブルを作成します。したがって：

import Control.Monad.State 
import Data.Map 
import Data.Universe 

-- e.g. `m ~ Identity` satisfies these constraints 
instance (Finite s, Foldable m, Monad m) => Foldable (StateT s m) where 
    foldMap f m = mconcat [foldMap f (evalStateT m s) | s <- universeF] 

fromTable :: (Finite s, Ord s) => [m (a, s)] -> StateT s m a 
fromTable vs = StateT (fromList (zip universeF vs) !) 

float :: (Traversable m, Applicative f) => m (f a, s) -> f (m (a, s)) 
float = traverse (\(fa, s) -> fmap (\a -> (a, s)) fa) 

instance (Finite s, Ord s, Traversable m, Monad m) => Traversable (StateT s m) where 
    sequenceA m = fromTable <$> traverse (float . runStateT m) universeF 

これは意味があるかわかりません。もしそうなら、私はそれをパッケージに追加して嬉しいです。どう思いますか？

Answer 3

私はそれが実際にFoldableまたはTraversibleだとは思わないが、MonadRandomは、無限リストのように機能するかもしれないが、折り畳み可能なものよりもコンテナのように見えないものの例である。概念的には、それは確率変数です。