Ai đó có thể giải thích chức năng đi qua trong Haskell

Question

Tôi là người mới làm quen với Haskell. Tôi đang cố gắng và không mò mẫm chức năng traverse từ mô-đun Data.Traversable. Tôi không thể nhìn thấy điểm của nó. Kể từ khi tôi đến từ một nền tảng bắt buộc, ai đó có thể vui lòng giải thích cho tôi về một vòng lặp bắt buộc? Một mã giả sẽ được nhiều đánh giá cao. Cảm ơn.

Answer 1

Tôi nghĩ rằng dễ hiểu nhất về mặt số sequenceA, vì traverse có thể được định nghĩa là theo sau.

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

sequenceA chuỗi lại với nhau các yếu tố của một cấu trúc từ trái sang phải, trở về một cấu trúc với hình dạng tương tự có chứa các kết quả.

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

Bạn cũng có thể nghĩ đến sequenceA như đảo ngược thứ tự của hai hàm, ví dụ: chuyển từ danh sách các hành động thành một hành động trả về một danh sách các kết quả.

Vì vậy, traverse có một số cấu trúc và áp dụng f để biến đổi mọi phần tử trong cấu trúc thành một số ứng dụng, sau đó trình tự lên các tác dụng phụ của các ứng dụng đó từ trái sang phải, trả về cấu trúc có cùng hình dạng.

Bạn cũng có thể so sánh nó với Foldable, xác định hàm liên quan traverse_.

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

Vì vậy, bạn có thể thấy rằng sự khác biệt chính giữa Foldable và Traversable là sau này cho phép bạn duy trì hình dạng của cấu trúc, trong khi cựu đòi hỏi bạn phải gấp kết quả lên vào một số giá trị khác.

---

Một ví dụ đơn giản của việc sử dụng của nó được sử dụng một danh sách như cấu trúc traversable, và IO như applicative:

λ> 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"] 

Tất nhiên, trong trường hợp này nó tương đương với mapM từ Prelude. Nó trở nên thú vị hơn khi được sử dụng trên các loại thùng chứa khác hoặc sử dụng các ứng dụng khác.

Answer 2

traverse cũng giống như fmap, ngoại trừ việc nó cũng cho phép bạn chạy các hiệu ứng trong khi bạn đang xây dựng lại cấu trúc dữ liệu.

Hãy xem ví dụ từ tài liệu Data.Traversable.

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

Các Functor thể hiện của Tree sẽ là:

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) 

Nó xây dựng lại toàn bộ cây, áp dụng f cho mọi giá trị.

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 

Trường hợp Traversable gần như giống nhau, ngoại trừ nhà thầu được gọi theo kiểu áp dụng. Điều này có nghĩa rằng chúng ta có thể có (side-) hiệu ứng trong khi xây dựng lại cây.Ứng dụng gần như giống như monads, ngoại trừ các hiệu ứng đó không thể phụ thuộc vào kết quả trước đó. Trong ví dụ này, nó có nghĩa là bạn không thể làm điều gì đó khác với nhánh bên phải của một nút phụ thuộc vào kết quả của việc xây dựng lại nhánh bên trái chẳng hạn.

Lớp Traversable cũng chứa phiên bản đơn điệu mapM nơi mà hiệu ứng có thể, về nguyên tắc, phụ thuộc vào kết quả trước đó. (Mặc dù bạn chắc chắn không được phép làm điều đó.) Ví dụ, làm ảnh hưởng của f hai lần nếu chi nhánh bên trái là 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' 

Nếu bạn muốn thực hiện điều này bằng một ngôn ngữ không trong sạch, fmap và traverse sẽ giống như mapM, vì không có cách nào để ngăn chặn các tác dụng phụ. Bạn không thể thực hiện nó như là một vòng lặp, vì bạn phải đi qua cấu trúc dữ liệu của bạn đệ quy. Dưới đây là một ví dụ nhỏ về cách tôi sẽ làm điều đó trong Javascript:

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

Thực hiện nó như thế này sẽ giới hạn hiệu ứng ngôn ngữ cho phép. Nếu bạn f.e. muốn không xác định (ví dụ danh sách của các mô hình ứng dụng) và ngôn ngữ của bạn không có sẵn nó, bạn sẽ không may mắn.

Answer 3

traverse biến những thứ bên trong một Traversable thành một Traversable thứ "bên trong" một Applicative, cho một chức năng mà làm cho Applicative s ra của sự vật.

Hãy sử dụng Maybe làm Applicative và liệt kê là Traversable. Đầu tiên chúng ta cần các chức năng chuyển đổi:

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

Vì vậy, nếu một số thậm chí còn, chúng tôi nhận được một nửa của nó (bên trong một Just), nếu không chúng tôi nhận Nothing. Nếu mọi thứ diễn ra "tốt", nó trông như thế này:

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

Nhưng ...

traverse half [1..10] 
-- Nothing 

Nguyên nhân là do các <*> chức năng được sử dụng để xây dựng kết quả, và khi một trong số các đối số là Nothing, chúng tôi nhận được Nothing quay lại.

Một ví dụ khác:

rep x = replicate x x 

Chức năng này sẽ tạo ra một danh sách dài x với nội dung x, ví dụ rep 3 = [3,3,3]. Kết quả của traverse rep [1..3] là gì?

Chúng tôi nhận được kết quả một phần của [1], [2,2] và [3,3,3] sử dụng rep. Giờ đây, ngữ nghĩa của danh sách là Applicatives là "lấy tất cả các kết hợp", ví dụ: (+) <$> [10,20] <*> [3,4] là [13,14,23,24].

"Tất cả kết hợp" của [1] và [2,2] là hai lần [1,2]. Tất cả các kết hợp của hai lần [1,2] và [3,3,3] là sáu lần [1,2,3].Vì vậy, chúng ta có:

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

Answer 4

traverselà vòng lặp. Việc triển khai của nó phụ thuộc vào cấu trúc dữ liệu được duyệt qua. Đó có thể là một danh sách, cây, có thể, Seq (ence), hoặc bất cứ điều gì có một cách chung chung của beeing đi qua thông qua sth. như một hàm vòng lặp hoặc đệ quy. Một mảng sẽ có một vòng lặp, một danh sách một vòng lặp while, một cây hoặc là sth. đệ quy hoặc sự kết hợp của một chồng với một vòng lặp while; nhưng trong các ngôn ngữ chức năng bạn không cần các lệnh lặp cồng kềnh này: bạn kết hợp phần bên trong của vòng lặp (trong hình dạng của một hàm) với cấu trúc dữ liệu theo cách trực tiếp hơn và ít tiết hơn.

Với kiểu chữ Traversable, bạn có thể viết các thuật toán của mình độc lập và linh hoạt hơn. Nhưng kinh nghiệm của tôi nói rằng, Traversable thường chỉ được sử dụng để đơn giản là dán các thuật toán vào các cơ sở dữ liệu hiện có. Nó là khá tốt đẹp không cần phải viết các chức năng tương tự cho các kiểu dữ liệu khác nhau đủ điều kiện, quá.

Answer 5

Nó giống như fmap, ngoại trừ việc bạn có thể chạy các hiệu ứng phụ bên trong hàm bản đồ, điều này cũng thay đổi loại kết quả.

Hãy tưởng tượng danh sách các số nguyên thể hiện ID người dùng trong cơ sở dữ liệu: [1, 2, 3]. Nếu bạn muốn fmap các ID người dùng này cho tên người dùng, bạn không thể sử dụng một số fmap truyền thống, vì bên trong hàm bạn cần truy cập cơ sở dữ liệu để đọc tên người dùng (yêu cầu tác dụng phụ - trong trường hợp này, sử dụng đơn nguyên IO).

Chữ ký của traverse là:

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

Với traverse, bạn có thể làm tác dụng phụ, do đó, mã của bạn cho ID người dùng ánh xạ tới tên người dùng trông giống như:

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

---

Có cũng có chức năng được gọi là mapM:

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

Bất kỳ việc sử dụng mapM nào cũng có thể được thay thế bằng traverse, nhưng không phải là cách khác. mapM thường hoạt động tốt hơn traverse, nhưng mapM chỉ hoạt động đối với các đơn vị có danh sách, trong khi traverse là tổng quát hơn.

Nếu bạn chỉ muốn đạt được hiệu ứng phụ và không trả về bất kỳ giá trị hữu ích nào, có traverse_ và mapM_ phiên bản của các chức năng này, cả hai đều bỏ qua giá trị trả về từ hàm và nhanh hơn một chút.