Ví dụ về loại có loại * -> * không thể là trường hợp của Functor

Question

Tôi là người mới làm quen với Haskell, vì vậy xin lỗi nếu câu trả lời là hiển nhiên, nhưng tôi đang làm việc thông qua Typeclassopedia trong nỗ lực hiểu rõ hơn về các danh mục. Khi làm các bài tập cho phần trên functors, tôi tình cờ gặp vấn đề này:

Hãy cho một ví dụ về một loại loại * -> * mà không thể được thực hiện một thể hiện của functor (không sử dụng không xác định).

Suy nghĩ đầu tiên của tôi là xác định một số loại định nghĩa vô hạn đệ quy của fmap, nhưng về cơ bản sẽ không giống như nếu undefined được sử dụng trong định nghĩa?

Nếu ai đó có thể giải thích câu trả lời, nó sẽ được đánh giá cao.

Cảm ơn!

Nguồn tập thể dục ban đầu ở đây, phần 3: http://www.haskell.org/haskellwiki/Typeclassopedia#Introduction

Answer 1

Một ví dụ đơn giản là

data K a = K (a -> Int) 

Đây là những gì ghci cho chúng ta biết được chúng tôi cố gắng để tự động lấy một ví dụ Functor cho K:

Prelude> :set -XDeriveFunctor 
Prelude> data K a = K (a -> Int) 
Prelude> :k K 
K :: * -> * 
Prelude> data K a = K (a -> Int) deriving Functor 

<interactive>:14:34: 
    Can't make a derived instance of `Functor K': 
     Constructor `K' must not use the type variable in a function argument 
    In the data type declaration for `K' 

Vấn đề là tiêu chuẩn Functor lớp thực sự đại diện cho covariant functors (fmap nâng đối số của nó lên f a -> f b), nhưng không có cách nào bạn có thể soạn a -> b và a -> Int để có được chức năng loại b -> Int (xem câu trả lời của Ramon). Tuy nhiên, nó có thể định nghĩa một lớp kiểu cho functors contravariant:

class Contravariant f where 
    contramap :: (a -> b) -> f b -> f a 

và làm K một thể hiện của nó:

instance Contravariant K where 
    contramap f (K g) = K (g . f) 

Để biết thêm về hiệp phương sai/contravariance trong Haskell, xem here.

Chỉnh sửa: Đây cũng là a nice comment on this topic từ Chris Smith trên Reddit.

Answer 2

Để mở rộng (viết tắt) của tôi bình luận và trên Mikhail của câu trả lời:

Với (-> Int), bạn mong muốn fmap nhìn như vậy:

(a -> Int) -> (a -> b) -> (b -> Int) 

hay:

(a -> Int) -> (a -> b) -> b -> Int 

Thật dễ dàng để chứng minh rằng từ ba đối số (a -> Int), (a -> b), b không có cách nào để đạt được Int (không có undefined), do đó từ (a -> Int), (a -> b) không có cách nào để đạt được (b -> Int). Kết luận: không có Functor phiên bản tồn tại cho (-> Int).