Nested ứng dụng chức năng

Question

Đó là khá dễ dàng để xác định một nhà điều hành như

(@) :: [x -> y] -> [x] -> [y] 

mà phải mất một danh sách các hàm và một danh sách các đầu vào và trả về một danh sách các kết quả đầu ra. Có hai cách rõ ràng để thực hiện điều này:

1. Áp dụng các chức năng đầu tiên vào đầu vào đầu tiên, chức năng thứ hai để các đầu vào thứ hai, vv
2. Áp dụng tất cả các chức năng để mỗi đầu vào.

Hoặc là không đáng kể để xác định. Điều tốt đẹp về nó là bây giờ bạn có thể làm điều gì đó như

foo :: X -> Y -> Z -> R 

bar :: [X] -> [Y] -> [Z] -> [R] 
bar xs ys zs = [foo] @@ xs @@ ys @@ zs 

Điều này nói chung với một số đối số chức năng tùy ý.

---

Cho đến nay rất tốt. Bây giờ cho các vấn đề: Làm thế nào để tôi thay đổi chữ ký kiểu cho @@ như vậy mà các loại chữ ký cho bar trở thành

bar :: [X] -> [Y] -> [Z] -> [[[R]]] 

Nó không khó để thực hiện một chức năng với loại hình này; một trong hai cách này sẽ làm điều đó:

bar xs ys zs = map (\ x -> map (\ y -> map (\ z -> foo x y z) zs) ys) zs 
bar xs ys zs = map (\ z -> map (\ y -> map (\ x -> foo x y z) xs) ys) zs 

Tôi không kén chọn kết quả mình nhận được. Nhưng tôi không thể tìm ra cách tinh chỉnh toán tử @@ để thực hiện điều này.

---

Một điều hiển nhiên phải cố gắng là

(@@) :: [x -> y] -> [x] -> [[y]] 

Nó không khó để thực hiện điều này, nhưng nó sẽ không giúp bạn. Bây giờ bạn có

[foo] @@ xs :: [[Y -> Z -> R]] 

không phải là đầu vào hợp lệ cho @@. Không có cách rõ ràng để biết có bao nhiêu cấp độ của danh sách để đạt được thông qua để có được chức năng; rõ ràng cách tiếp cận này là một kết thúc chết.

Tôi đã thử một vài chữ ký có thể có khác, nhưng không có chữ ký nào đưa tôi đến gần câu trả lời hơn. Ai đó có thể cho tôi một giải pháp, hoặc giải thích tại sao không tồn tại?

Answer 1

Thực ra, điều này không cần các lớp loại nào cả! Bạn mất một chút tiện lợi bằng cách tránh các lớp học, nhưng đó là tất cả.

Điểm mấu chốt là, mặc dù sử dụng lại một bộ phối hợp đơn, tính đa hình cho phép loại sử dụng khác nhau. Đây là nguyên tắc tương tự đằng sau các biểu thức kiểu Applicative kiểu như f <$> xs <*> ys <*> zs và kết quả cuối cùng ở đây trông sẽ giống nhau. Do đó, chúng tôi sẽ làm điều đó cho bất kỳ Functor, không chỉ danh sách.

Sự khác biệt giữa điều này và phiên bản Applicative là chúng tôi đi sâu hơn vào lồng nhau Functor s với từng bước. Sự đa hình cần thiết đòi hỏi sự linh hoạt ở tầng bên trong nhất, vì vậy để thực hiện điều này, chúng ta sẽ sử dụng một thủ thuật tiếp tục-ish trong đó kết quả của mỗi bộ kết hợp là một hàm chấp nhận một phép biến đổi để sử dụng ở lớp trong cùng.

Chúng tôi sẽ cần hai toán tử, một toán tử khởi động chuỗi và một chuỗi tiếp tục tăng dần. Bắt đầu bằng cách sau:

(@@) :: (Functor f) => (((a -> b) -> f c) -> r) -> f a -> (b -> c) -> r 
q @@ xs = \k -> q (\f -> k . f <$> xs) 

Điều này cần một đối số mới ở bên phải và biểu thức đang diễn ra ở bên trái. Kết quả có một hàm k, xác định những gì cần làm để có được kết quả cuối cùng. k được kết hợp với bất kỳ biểu thức nào trong tiến trình đã có và cả hai được ánh xạ trên đối số mới. Điều này là phức tạp, nhưng nên nhìn quen thuộc với bất cứ ai đã lấy mã theo phong cách CPS.

(<@) :: (Functor f, Functor g) => f (a -> b) -> g a -> (b -> c) -> f (g c) 
fs <@ xs = (<$> fs) @@ xs 

Chuỗi được bắt đầu bằng cách ánh xạ mọi thứ khác lên đối số đầu tiên.

Không giống như trường hợp đơn giản Applicative, chúng tôi cũng cần kết thúc rõ ràng chuỗi. Giống như đơn vị Cont, cách đơn giản nhất để thực hiện điều này là áp dụng kết quả cho chức năng nhận dạng.Chúng tôi sẽ cung cấp cho rằng một tên hữu ích:

nested = ($ id) 

Bây giờ, chúng ta có thể làm những việc như thế này:

test2 :: [X -> Y -> R] -> [X] -> [Y] -> [[[R]]] 
test2 fs xs ys = nested (fs <@ xs @@ ys) 

test3 :: [X -> Y -> Z -> R] -> [X] -> [Y] -> [Z] -> [[[[R]]]] 
test3 fs xs ys zs = nested (fs <@ xs @@ ys @@ zs) 

Không khá xinh đẹp như các phiên bản kiểu lớp, nhưng nó hoạt động.

Answer 2

Bạn đã đạt được lý do tại sao điều này là phiền hà. Chức năng của bạn (@@) được áp dụng cho các loại đầu vào khác nhau (ví dụ: [x->y], [[x -> y]], v.v. Điều này có nghĩa là chữ ký loại của bạn cho @@ là quá hạn chế, bạn sẽ cần thêm một số đa hình để làm cho nó trở nên phổ biến hơn. Vì nó xảy ra, với vấn đề này nếu bạn biết loại LHS, bạn có thể xác định duy nhất cả RHS và kết quả. đầu vào có loại [a->b], RHS phải là [a] và kết quả phải là [[b]]. Điều này có thể được đơn giản hóa thành đầu vào của a->b, RHS của [a], và kết quả của [b].Vì LHS xác định các tham số và kết quả khác, chúng ta có thể sử dụng hoặc fundeps hoặc loại gia đình để đại diện cho các loại khác.

{-# LANGUAGE TypeFamilies, UndecidableInstances #-} 

class Apply inp where 
    type Left inp :: * 
    type Result inp :: * 
    (@@) :: inp -> [Left inp] -> [Result inp] 

Bây giờ chúng ta có một lớp loại, chúng ta có thể làm cho các ví dụ rõ ràng cho một chức năng:

instance Apply (a -> b) where 
    type Left (a -> b) = a 
    type Result (a -> b) = b 
    (@@) = map 

Thể hiện danh sách không phải là quá xấu, hoặc:

instance Apply f => Apply [f] where 
    type Left [f] = Left f 
    type Result [f] = [Result f] 
    l @@ r = map (\f -> f @@ r) l 
    -- or map (@@ r) l 

Bây giờ phương thức lớp học của chúng tôi @@ sẽ hoạt động với danh sách sâu tùy ý. Dưới đây là một số thử nghiệm:

*Main> (+) @@ [1..3] @@ [10..13] 
[[11,12,13,14],[12,13,14,15],[13,14,15,16]]'s 

let foo :: Int -> Char -> Char -> String 
    foo a b c = b:c:show a 

*Main> foo @@ [1,2] @@ "ab" @@ "de" 
[[["ad1","ae1"],["bd1","be1"]],[["ad2","ae2"],["bd2","be2"]]] 

Bạn có thể muốn xem triển khai printf để có thêm cảm hứng.

Chỉnh sửa: Ngay sau khi đăng bài này, tôi nhận ra rằng người ta có thể khái quát hóa loại container trong lớp Apply của mình từ List đến Applicative, sau đó sử dụng thể hiện ứng dụng thay vì bản đồ. Điều này sẽ cho phép cả hai danh sách thông thường và hành vi ZipList.