Haskell: Một ví dụ về có thể gập lại mà không phải là một Functor (hoặc không Traversable)?

Question

Một ví dụ Foldable có thể là một số loại container, và do đó có khả năng là một Functor là tốt. Thật vậy, this nói

Một loại Foldable cũng là một container (mặc dù các lớp không kỹ thuật đòi hỏi Functor, thú vị Foldable s đều Functor s).

Vì vậy, có ví dụ về số Foldable không tự nhiên là Functor hoặc Traversable? (có lẽ trang wiki Haskell đã bỏ qua :-))

Answer 1

Dưới đây là một ví dụ đầy đủ tham số:

data Weird a = Weird a (a -> a) 

instance Foldable Weird where 
    foldMap f (Weird a b) = f $ b a 

Weird không phải là một Functor vì a xảy ra ở một vị trí tiêu cực.

Answer 2

Đây là ví dụ đơn giản: Data.Set.Set. See for yourself.

Lý do cho điều này nên được rõ ràng nếu bạn kiểm tra các loại của chuyên fold và map chức năng định nghĩa cho Set:

foldr :: (a -> b -> b) -> b -> Set a -> b 

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b 

Bởi vì cấu trúc dữ liệu dựa trên một cây tìm kiếm nhị phân trong nội bộ, một hạn chế Ord là cần thiết cho các yếu tố. Functor trường hợp phải cho phép bất kỳ loại phần tử nào, do đó, điều đó không khả thi, than ôi.

Gấp, mặt khác, luôn phá hủy cây để tạo ra giá trị tóm tắt, do đó không cần phải sắp xếp kết quả trung gian của màn hình đầu tiên. Ngay cả khi nếp gấp đang thực sự xây dựng một mới Set, trách nhiệm đáp ứng các ràng buộc Ord nằm trên chức năng tích lũy được thông qua để gấp, không phải là lần chính nó.

Điều tương tự có thể áp dụng cho bất kỳ loại vùng chứa nào không hoàn toàn tham số. Và với các tiện ích của Data.Set, điều này làm cho nhận xét bạn trích dẫn về "thú vị" Foldable s dường như một chút nghi ngờ, tôi nghĩ!

Answer 3

Reading Beautiful folding tôi nhận ra rằng bất kỳ Foldable thể được thực hiện một Functor bằng cách gói nó vào

data Store f a b = Store (f a) (a -> b) 

với một contructor thông minh đơn giản:

store :: f a -> Store f a a 
store x = Store x id 

(Đây chỉ là một biến thể của Store loại dữ liệu comonad.)

Bây giờ chúng tôi có thể xác định

instance Functor (Store f a) where 
    fmap f (Store x g) = Store x (f . g) 

instance (F.Foldable f) => F.Foldable (Store f a) where 
    foldr f z (Store x g) = F.foldr (f . g) z x 

Bằng cách này, chúng tôi có thể làm cho cả hai Data.Set.Set và Sjoerd Visscher là Weird một hàm. (Tuy nhiên, vì cấu trúc không ghi nhớ các giá trị của nó, việc lặp lại nhiều lần so với nó có thể rất không hiệu quả, nếu hàm mà chúng ta sử dụng trong fmap là phức tạp.)

---

Cập nhật: này cũng cung cấp một ví dụ về một cấu trúc đó là một functor, có thể gập lại nhưng không traversable. Để thực hiện Store có thể di chuyển, chúng tôi cần phải thực hiện (->) r có thể di chuyển. Vì vậy, chúng tôi cần phải thực hiện

sequenceA :: Applicative f => (r -> (f a)) -> f (r -> a) 

Chúng ta hãy Either b cho f. Sau đó, chúng tôi cần phải thực hiện

sequenceA' :: (r -> Either b a) -> Either b (r -> a) 

Rõ ràng, không có chức năng đó (bạn có thể xác minh với Djinn). Vì vậy, chúng tôi không thể nhận ra sequenceA.