有人可以解釋Haskell中的遍歷函數

Question

我是Haskell的新手。我正在嘗試並且無法從Data.Traversable模塊獲得traverse功能。我無法看清楚它的意思。因爲我來自一個必要的背景，有人可以根據一個命令循環向我解釋嗎？一個僞代碼將不勝感激。謝謝。

Answer 1

我覺得最容易理解的是sequenceA，因爲traverse可以定義爲 如下。

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) 
traverse f = sequenceA . fmap f 

sequenceA序列的結構的由左到右，與包含結果相同的形狀返回結構中的元素一起。

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

你也可以認爲sequenceA作爲扭轉了二函子的順序，例如從動作列表轉到返回結果列表的動作。

所以traverse需要一些結構，並適用f的每個元素在結構轉變爲一些應用性，它然後序列向上從左至右，與包含結果相同的形狀返回一個結構的那些applicatives的副作用。

您還可以將其與Foldable進行比較，該參數定義了相關功能traverse_。

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f() 

所以你可以看到，Foldable和Traversable之間的關鍵區別在於，後者可以讓你保持結構的形狀，而前者需要你結果了摺疊成一些其他的價值。

---

其使用的一個簡單的例子是使用一個列表作爲橫過結構，並且IO作爲應用性：

λ> import Data.Traversable 
λ> let qs = ["name", "quest", "favorite color"] 
λ> traverse (\thing -> putStrLn ("What is your " ++ thing ++ "?") *> getLine) qs 
What is your name? 
Sir Lancelot 
What is your quest? 
to seek the holy grail 
What is your favorite color? 
blue 
["Sir Lancelot","to seek the holy grail","blue"] 

。當然，在這種情況下，等同於mapM從前奏。使用其他類型的容器或使用其他應用程序時，它會變得更有趣。

Answer 2

traverse與fmap相同，只是它還允許您在重建數據結構時運行效果。

查看Data.Traversable文檔中的示例。

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) 

的Tree的Functor實例是：

instance Functor Tree where 
    fmap f Empty  = Empty 
    fmap f (Leaf x)  = Leaf (f x) 
    fmap f (Node l k r) = Node (fmap f l) (f k) (fmap f r) 

它會重建整個樹，應用f到每個值。

instance Traversable Tree where 
    traverse f Empty  = pure Empty 
    traverse f (Leaf x)  = Leaf <$> f x 
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r 

的Traversable實例幾乎是相同的，除了構造函數的調用在應用性的風格。這意味着我們可以在重建樹的時候產生（副作用）效果。除了效果不能取決於以前的結果之外，應用程序與monad幾乎相同。在這個例子中，它意味着你不能做一些不同於某個節點的右分支的東西，這取決於重建左分支的結果。

該Traversable類也包含一個單一版本mapM原則上，效果可能取決於以前的結果。 （雖然你絕對不應該做的。）例如，做f的影響，如果兩次左支是Empty：

mapM f (Node l k r) = do 
    l' <- mapM f l 
    k' <- case l' of 
    Empty -> do _ <- f k; f k 
    _  -> f k 
    r' <- mapM f r 
    return $ Node l' k' r' 

如果你想實現這個不純的語言，fmap和traverse會與mapM相同，因爲沒有辦法防止副作用。您不能將其實現爲循環，因爲您必須遞歸地遍歷數據結構。這裏有一個小例子，我將如何使用Javascript：

Node.prototype.traverse = function (f) { 
    return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f)); 
} 

像這樣實現它限制了語言允許的效果。如果你f.e.想要非確定性（Applicative模型的列表實例）和你的語言沒有內置的，你是不走運的。

Answer 3

traverse原來的東西Traversable內成爲Traversable的事情「內部」的Applicative，給出一個函數，使Applicative出去了的東西。

我們使用Maybe作爲Applicative，列表爲Traversable。首先，我們需要轉換功能：

half x = if even x then Just (x `div` 2) else Nothing 

因此，如果一個數是偶數，我們得到的一半（一Just內），否則我們得到Nothing。如果一切順利的「井」，它看起來像這樣：

traverse half [2,4..10] 
--Just [1,2,3,4,5] 

但是......

traverse half [1..10] 
-- Nothing 

的原因是<*>功能是用於構建的結果，而當其中一個參數是Nothing，我們得到Nothing回來。

又如：

rep x = replicate x x 

該函數生成長度x的列表與該內容x，例如rep 3 = [3,3,3]。 traverse rep [1..3]的結果是什麼？

我們得到[1]，[2,2]和[3,3,3]使用rep的部分搜索結果。現在列表的語義爲Applicatives是「採取所有組合」，例如， (+) <$> [10,20] <*> [3,4]是[13,14,23,24]。

[1]和[2,2]的「所有組合」是[1,2]的兩倍。兩次[1,2]和[3,3,3]的所有組合是[1,2,3]的六倍。因此，我們有：

traverse rep [1..3] 
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]] 

Answer 4

traverse是循環。其實現取決於要遍歷的數據結構。這可能是一個List，Tree，Maybe，Seq（ence）或者任何具有通過某種方法遍歷的通用方法。像一個for循環或遞歸函數。一個數組有一個for循環，一個List while循環，一個Tree或者。遞歸或堆棧與while循環的組合;但在函數式語言中，您不需要這些繁瑣的循環命令：將循環的內部部分（以函數的形式）與數據結構以更直接的方式組合起來，而不是冗長的。

使用Traversable typeclass，你可能會寫出更獨立和多功能的算法。但我的經驗表明，Traversable通常只用於將算法粘貼到現有的數據結構。不需要爲不同的數據類型編寫類似的函數也是很好的。

Answer 5

它有點像fmap，不同之處在於你可以在mapper函數中運行副作用，這也會改變結果類型。

想象一下表示數據庫中用戶ID的整數列表：[1, 2, 3]。如果你想fmap這些用戶ID到用戶名，你不能使用傳統的fmap，因爲在函數內你需要訪問數據庫來讀取用戶名（這需要一個副作用 - 在這種情況下，使用IO monad ）。

的traverse的簽名是：

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

隨着traverse，你可以做的副作用，因此，您的映射用戶ID碼到用戶名的樣子：

mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String] 
mapUserIDsToUsernames fn ids = traverse fn ids 

---

有還有一個叫做mapM的功能：

mapM :: Monad m => (a -> m b) -> [a] -> m [b] 

任何使用mapM都可以用traverse代替，但不能用其他方式。 mapM通常表現優於traverse，但mapM僅適用於帶單子的單子，而traverse更具通用性。

如果您只是想達到副作用並且不返回任何有用的值，則有traverse_和mapM_版本的這些函數，它們都會忽略函數的返回值並且速度稍快。