Bộ chuyển đổi khác với chức năng được áp dụng một phần như thế nào?

Question

Sau khi đọc bài viết này trên Clojure (http://blog.podsnap.com/ducers2.html) giới thiệu đầu dò, tôi đang bối rối về những gì một bộ chuyển đổi. Được áp dụng một phần map trong Haskell, chẳng hạn như map (+1) bộ chuyển đổi? Lúc đầu, tôi nghĩ rằng đây là một cách Clojure sử dụng một phần ứng dụng, nhưng sau đó bài viết tiếp tục thực hiện nó trong Haskell với một kiểu rõ ràng. Nó có sử dụng gì trong Haskell?

Answer 1

Trong Clojure (map inc) là bộ chuyển đổi, nhưng không phải trong Haskell, vì Haskell phải tuân thủ currying nhưng một Lisp không định dạng có thể phá vỡ quy ước curry-by-default đó. Các loại đầu dò là thay vì:

type Transducer a b = forall r . (b -> r -> r) -> (a -> r -> r) 

Chúng ta nói rằng đầu dò 'biến a vào b'. Có, a và b có vẻ "ngược" ở phía bên tay phải. forall có nghĩa là Bộ chuyển đổi phải để r làm biến loại chung nhưng hoàn toàn được phép chuyên về a và b.

Hãy để tôi đảo ngược hai trong số các đối số trong foldr:

-- cf. with foldr :: (x -> r -> r) -> r -> [x] -> r 
ffoldr :: (x -> r -> r) -> [x] -> r -> r 
ffoldr = flip . foldr 

(chúng tôi cũng có thể sử dụng foldl nhưng nó sẽ có xu hướng đảo ngược mọi thứ sau). Điều này có nghĩa là bạn có thể sử dụng Transducer để chuyển đổi đối số đầu tiên của ffoldr từ x thành y để chúng tôi có thể xử lý [x] bằng y -> r -> r sử dụng foldr. Đầu dò 'ngồi giữa' đầu vào ([x], r) và bộ xử lý cuối cùng (y, r) -> r.

Tôi đã lật hai đối số thứ hai để nhấn mạnh rằng, đáng ngạc nhiên, ffoldr :: Transducer [x] x. Bằng cách sử dụng tính đối xứng của các đối số chúng tôi cũng có một thành phần chung của đầu dò, mà sẽ xảy ra là chỉ hàm hợp:

(.) :: Transducer a b -> Transducer b c -> Transducer a c 

(Nếu bạn nghĩ nó rất tuyệt đó đưa ra những forall r ngữ cho phép chúng ta đảo ngược cách bạn thường sử dụng . ., bạn có thể làm điều đó tùy tiện thông qua một kỹ thuật gọi là "sự tiếp nối đi qua")

Ví dụ, đây là bộ chuyển đổi bộ lọc:

tfilter :: (a -> Bool) -> (a -> r -> r) -> a -> r -> r 
    -- or: (a -> Bool) -> Transducer a a 
tfilter predicate f a = if predicate a then f a else id 

này áp dụng chức năng giảm f đến a và r chỉ khi vị từ được giữ. Ngoài ra còn có một bộ chuyển đổi bản đồ:

tmap :: (a -> b) -> (b -> r -> r) -> a -> r -> r 
tmap ba f a = f (ba a) 

này cho ngữ nghĩa bản đồ/lọc composable cho bất kỳ loại 'transducable': một bản đồ/lọc fn thể làm việc cho nhiều ngữ cảnh.

Các đầu dò loại có một đẳng cấu dễ thương: nó quay ra rằng foldr của một danh sách forall r. (x -> r -> r) -> r -> r là hoàn toàn tương đương với danh sách đó [x] (nó là "mã hóa Giáo Hội" của danh sách đó), và do đó trao đổi lý luận a đến mặt trước của định nghĩa đầu dò cho chúng ta (IMO dễ hiểu hơn nhiều!) loại type TransL a b = a -> [b].Và đây là dễ dàng hơn để hiểu:

tl_map f = \a -> [f a] 
tl_filter predicate = \a -> if predicate a then [a] else [] 

Để chạy này trên một danh sách, sử dụng concatMap ... mà sẽ xảy ra là chỉ >>=! Vì vậy, bạn chỉ cần viết collection >>= transducer và bạn có bộ sưu tập được tải xuống. Ý nghĩa của TransL a b là "lấy từng phần tử trong danh sách gốc a và cho tôi 0 hoặc nhiều thành phần thuộc loại b để ghép vào danh sách gửi đi của tôi". Nó lọc bằng cách nối 0 phần tử khi vị từ không hoạt động; nó ánh xạ bằng cách sinh ra 1 phần tử đầu ra cho mỗi phần tử đầu vào; một hoạt động khác tl_dupe = \a -> [a, a] là bộ chuyển đổi sao chép các phần tử trong danh sách, [1,2,3] >>= tl_dupe trở thành [1,1,2,2,3,3].

Trường hợp foldr có vẻ là Transducer [x] x, giờ đây nó được xem là giống hệt với id :: TransL [x] x có cách đơn giản là thực hiện thao tác concat ở giữa tính toán; chức năng nhận dạng trong đại số này thực sự là return = \a -> [a], cũng được viết (:[]). Chỉ số chỉ mất là chúng tôi không thể sử dụng . để soạn những cái này nữa, nhưng trên thực tế, bố cục tương tự được cung cấp trong Control.Monad làm toán tử thành phần Kleisli >=>.

Vì vậy, dài câu chuyện ngắn, đầu dò là chức năng a -> [b] khéo léo chuyển đổi với một chút mã hóa Giáo hội để các nhà điều hành thành phần Kleisli cho các mũi tên Kleisli của danh sách đơn nguyên, trở thành chỉ đơn giản là (.).