Traversable除了可摺疊還有什麼「獨特方法」？

Foldable是Traversable的超類，與Functor是Applicative和Monad的超類相似。Traversable除了可摺疊還有什麼「獨特方法」？

到Monad，它是可能的情況類似，基本實現fmap作爲

liftM :: Monad m => (a->b) -> m a -> m b 
liftM f q = return . f =<< q

我們也可以使用Monoid m => (,) m單子效仿foldMap作爲

foldLiftT :: (Traversable t, Monoid m) => (a -> m) -> t a -> m 
foldLiftT f = fst . traverse (f >>> \x -> (x,x)) 
      -- or: . sequenceA . fmap (f >>> \x -> (x, x))

。所以超類和方法的結合在兩種情況下都有一定的冗餘。

在單子的情況下，可以說，該類型的類的「好」的定義是（我將跳過應用性/ monoidal）

class (Functor m) => Monad m where 
    return :: a -> m a 
    join :: m (m a) -> m a

至少這是什麼範疇論使用。這個定義沒有使用Functor超類，而不是許可liftM，所以它沒有這個冗餘。

對於Traversable類可能有類似的轉換嗎？

爲了澄清：我後是一個重新定義，讓我們叫它，

class (Functor t, Foldable t) => Traversable t where 
    skim :: ???

這樣，我們可以使實際Traverse方法頂級功能

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

但它會不是可以做出一般的做法

instance (Traversable t) => Foldable t where 
    foldMap = ... skim ... 

data T 
instance Traversable T where 
    skim = ...

我不是問，因爲我需要這對於某些特定的東西;這是一個概念性問題，以便更好地理解Foldable和Traversable之間的差異。同樣很像Monad VS Functor：雖然>>=比join日常哈斯克爾編程方便多了（因爲你通常需要正是這種組合fmap和join），後者可以更容易把握一個單子是什麼。

來源

2014-01-13 leftaroundabout

不同的方法是「遍歷」。你不能用'Foldable'來實現它。 –

當然不是，但是你可以用'遍歷'來實現'Foldable'。 – leftaroundabout

......這就是爲什麼'Foldable'是'Traversable'的超級類。一個超級類應該可以在子類中實現。 –

Foldable是Functor作爲Traversable是Monad，即Foldable和Functor是Monad和Traversable（模所有的應用性/單子提案噪聲）的超類。

事實上，這已經在代碼

instance Foldable f => Traversable f where 
    ...

因此，目前還不清楚是什麼更多有希望。Foldable的特徵在於toList :: Foldable f => f a -> [a]而Traversable最終取決於不僅能夠抽象的內容作爲等toList列表確實，而且還能夠提取形狀

shape :: Functor f => f a -> f() 
shape = fmap (const())

，然後重新組合它們

combine :: Traversable f => f() -> [a] -> Maybe (f a) 
combine f_ = evalStateT (traverse pop f_) where 
    pop :: StateT [a] Maybe a 
    pop = do x <- get 
      case x of 
      [] = empty 
      (a:as) = set as >> return a

這取決於traverse。

想要了解此屬性的更多信息，請參閱this blog post by Russell O'Connor。

來源

2014-01-13 03:42:38

那麼，如果'combine'是'Traversable'的唯一方法，那麼它能夠根據它來定義'遍歷'/'sequenceA'嗎？ – leftaroundabout

我也許會說可摺疊對於Functor來說是可穿越的，就是*應用*。 –

@leftaroundabout嘗試一下，然後發帖，如果你陷入困境:-) – misterbee

超級手工波浪，因爲它晚了，但Traversable超過Foldable的額外功率是一種重建原始結構的方式。例如，對於清單：

module MyTraverse where 

import Data.Foldable 
import Data.Traversable 
import Control.Applicative 
import Data.Monoid 

data ListRec f x = ListRec 
    { el :: f (Endo [x]) 
    } 

instance Applicative f => Monoid (ListRec f x) where 
    mempty = ListRec (pure mempty) 
    mappend (ListRec l) (ListRec r) = 
     ListRec (mappend <$> l <*> r) 

toM :: Functor f => f b -> ListRec f b 
toM this = ListRec $ (Endo . (:)) <$> this 

fromM :: Functor f => ListRec f b -> f [b] 
fromM (ListRec l) = flip appEndo [] <$> l 

myTraverse :: Applicative f => (a-> f b) -> [a] -> f [b] 
myTraverse f xs = fromM $ foldMap (toM . f) xs

我覺得這myTraverse行爲一樣traverse，只使用類Applicative，Foldable和Monoid。如果您想擺脫Monoid，您可以重新編寫它以使用foldr而不是foldMap。

列表很容易，因爲它們是扁平結構。但是，我強烈懷疑你可以使用Zipper來獲得適用於任何結構的正確重建函數（因爲拉鍊通常是可派生的，它們應該始終存在）。

但即使使用拉鍊，您也沒有任何方式將該結構指示給monoid/function。名義上，似乎Traversable增加了一些像

class Traversed t where 
    type Path t :: * 
    annotate :: t a -> [(Path t, a)] 
    fromKeyed :: [(Path t, a)] -> t a

這似乎與Foldable大量重疊的，但我認爲，試圖與它們的成分值的路徑相關聯時，是不可避免的。

來源

2014-01-13 09:59:20

Traversable除了可摺疊還有什麼「獨特方法」？

回答

相關問題