Trình phân tích cú pháp gia tăng này có phải là một hàm functor không, nếu như vậy `fmap` sẽ được thực hiện như thế nào?

Question

Tôi thực sự ghét hỏi loại câu hỏi này nhưng tôi đã kết thúc trí thông minh của mình ở đây. Tôi đang viết một trình phân tích cú pháp gia tăng nhưng vì một lý do nào đó, không thể tìm ra cách thực hiện cá thể functor cho nó. Dưới đây là các bãi chứa mã:

Input Type liệu

Input là kiểu dữ liệu thu được từ phân tích cú pháp cho coroutine. Nó chứa danh sách hiện tại của ký tự đầu vào được phẫu thuật bởi coroutine và kết thúc của tình trạng dòng

data Input a = S [a] Bool deriving (Show) 

instance Functor Input where 
    fmap g (S as x) = S (g <$> as) x 

Loại Data Output

Output là kiểu dữ liệu thu được từ coroutine để Parser. Nó là một trong hai nhắn Không, Done [b], hoặc một phần ([a] -> Output ab), nơi [a] là bộ đệm hiện nay truyền lại cho phân tích cú pháp

data Output a b = Fail String | Done [b] | Partial ([a] -> Output a b) 

instance Functor (Output a) where 
    fmap _ (Fail s) = Fail s 
    fmap g (Done bs) = Done $ g <$> bs 
    fmap g (Partial f) = Partial $ \as -> g <$> f as 

Các Parser

Các phân tích cú pháp mất [a] và mang lại một bộ đệm [a] để coroutine, trong đó sản lượng trở lại Output ab

data ParserI a b = PP { runPi :: [a] -> (Input a -> Output a b) -> Output a b } 

functor thực hiện

Nó có vẻ như tất cả những gì phải làm là fmap chức năng g vào coroutine, như sau:

instance Functor (ParserI a) where 
    fmap g p = PP $ \as k -> runPi p as (\xs -> fmap g $ k xs) 

Nhưng nó không gõ kiểm tra:

Couldn't match type `a1' with `b' 
    `a1' is a rigid type variable bound by 
     the type signature for 
     fmap :: (a1 -> b) -> ParserI a a1 -> ParserI a b 
     at Tests.hs:723:9 
    `b' is a rigid type variable bound by 
     the type signature for 
     fmap :: (a1 -> b) -> ParserI a a1 -> ParserI a b 
     at Tests.hs:723:9 
Expected type: ParserI a b 
    Actual type: ParserI a a1 

Answer 1

Như Philip JF tuyên bố, nó không có thể có một số instance Functor (ParserI a). Các bằng chứng đi bởi phương sai của functors - bất kỳ functor (toán học) phải, cho mỗi đối số của nó, hoặc là covariant hoặc contravariant. Bình thường Haskell Functor s luôn hiệp biến đó là lý do

fmap :: (a -> b) -> (f a -> f b)` 

Haskell Contravariant functors có tương tự

contramap :: (b -> a) -> (f a -> f b)` 

Trong trường hợp của bạn, b chỉ mục trong ParserI a b sẽ phải được cả hai hiệp biến và contravariant. Cách nhanh chóng để tìm ra điều này là liên kết các vị trí covariant với + và contravariant thành - và xây dựng từ một số quy tắc cơ bản.

Vị trí biến đổi là kết quả hàm, contravariant là đầu vào chức năng. Vì vậy, ánh xạ kiểu như type Func1 a b c = (a, b) -> c có a ~ -, b ~ - và c ~ +. Nếu bạn có chức năng ở vị trí đầu ra, bạn nhân tất cả các biến đối số theo +1. Nếu bạn có các chức năng trong nhập vị trí bạn nhân tất cả các phương sai theo -1.Như vậy

type Func2 a b c = a -> (b -> c) 

có chênh lệch tương tự như Func1 nhưng

type Func3 a b c = (a -> b) -> c 

có a ~ 1, b ~ -1, và c ~ 1. Sử dụng các quy tắc này, bạn có thể nhanh chóng thấy rằng Output có các phương sai như Output - + và sau đó ParserI sử dụng Output ở cả vị trí phủ định và dương, do đó không thể thẳng đứng Functor.

---

Nhưng có các khái quát chung như Contravariant. Tổng quát đặc biệt quan tâm là Profunctor (hoặc Difunctor s mà bạn nhìn thấy đôi khi) mà đi như vậy

class Profunctor f where 
    promap :: (a' -> a) -> (b -> b') -> (f a b -> f a' b') 

ví dụ tinh túy trong đó là (->)

instance Profunctor (->) where 
    promap f g orig = g . orig . f 

tức là nó "mở rộng" chức năng cả sau (như thông thường Functor) và trước đó. Profunctor s f do đó luôn là các toán tử của toán tử 2 với chữ số phương sai f - +.

Do đó, bằng cách khái quát hóa ParserI một chút, cho phép có thêm thông số để tách các loại ouput làm đôi, chúng tôi có thể làm cho nó là Profunctor.

data ParserIC a b b' = PP { runPi :: [a] -> (Input a -> Output a b) -> Output a b' } 

instance Profunctor (ParserIC a) where 
    promap before after (PP pi) = 
    PP $ \as k -> fmap after $ pi as (fmap before . k) 

và sau đó bạn có thể bọc nó lên

type ParserI a b = ParserIC a b b 

và cung cấp một chức năng lập bản đồ hơi kém thuận lợi hơn b

mapPi :: (c -> b) -> (b -> c) -> ParserI a b -> ParserI a c 
mapPi = promap 

mà thực sự thúc đẩy nhà gánh nặng của việc có sự chênh lệch đi cả cách --- bạn cần phải có bản đồ hai chiều!