Viết đơn nguyên nhận dạng về miễn phí

Question

Trong "Kiểu dữ liệu a la carte" Swierstra viết rằng cho Free (mà ông gọi là Term) và Zero bạn có thể thực hiện Identity đơn nguyên:

data Term f a = Pure a 
       | Impure (f (Term f a)) 
data Zero a 

Term Zero nay là là Identity monad. Tôi hiểu tại sao điều này xảy ra. Vấn đề là tôi không bao giờ có thể sử dụng như một Term Zero Monad vì pesky Functor f => chế:

instance Functor f => Monad (Term f) where 
    return x = Pure x 
    (Pure x) >>= f = f x 
    (Impure f) >>= t = Impure (fmap (>>=f) t) 

Làm thế nào để làm cho Zero một functor?

instance Functor Zero where 
    fmap f z = ??? 

Nó có vẻ như có một mẹo ở đây: Kể từ Zero không có nhà thầu, Impure không bao giờ có thể được sử dụng, và do đó các trường hợp Impure của >>= không bao giờ được gọi. Điều này có nghĩa là không bao giờ fmap gọi, vì vậy có một cảm giác mà điều này là ok:

instance Functor Zero where 
    fmap f z = undefined 

Vấn đề là, điều này cảm thấy như gian lận. Tôi đang thiếu gì? Là Zero thực sự là một Functor? Hoặc có lẽ Zero không phải là một Functor, và đây là một thiếu sót về cách chúng tôi thể hiện Free trong Haskell?

Answer 1

Nếu bạn bật DeriveFunctor, bạn có thể viết

data Zero a deriving Functor 

nhưng bạn có thể xem xét gian lận đó. Nếu bạn muốn viết nó cho mình, bạn có thể bật EmptyCase, thay vào đó, sau đó viết funky-tìm

instance Functor Zero where 
    fmap f z = case z of 

Answer 2

Một cách để đi về vấn đề này là sử dụng Data.Void thay vì một data khai trống rỗng, như thế này:

import Data.Void 

-- `Zero a` is isomorphic to `Void` 
newtype Zero a = Zero Void 

instance Functor Zero where 
    -- You can promise anything if the precondition is that 
    -- somebody's gotta give you an `x :: Void`. 
    fmap f (Zero x) = absurd x 

Xem this question để có một số giải thích thực sự tuyệt vời về những gì Void hữu ích. Nhưng ý tưởng quan trọng là chức năng absurd :: Void -> a cho phép bạn đi từ đó không bao giờ có thể xảy ra x :: Void ràng buộc vào bất kỳ loại nào bạn thích.

Answer 3

Cách lừa để xác định Zero a là như sau.

newtype Zero a = Zero (Zero a) 

Nói cách khác, nó mã hóa các loại ngớ ngẩn tuyên bố, một chút không rõ ràng rằng có thực sự là một cách để có được một giá trị của Zero a: bạn phải đã có một!

Với định nghĩa này, absurd :: Zero a -> b là định nghĩa một cách "tự nhiên"

absurd :: Zero a -> b 
absurd (Zero z) = absurd z 

Trong một nghĩa nào đó những định nghĩa là tất cả các quy phạm pháp luật vì họ chỉ ra chính xác cách thức họ không thể nhanh chóng. Không có giá trị nào của Zero a có thể được xây dựng trừ khi người khác "lừa" trước.

instance Functor Zero where 
    fmap f = absurd 

Answer 4

Một spin trên Luis Casillas của answer là xây dựng loại hình hoàn toàn từ các bộ phận chứng khoán:

type Id = Free (Const Void) 

Các Functor dụ cho Const x sẽ làm việc như bạn muốn (nó fmap không làm gì cả, mà chỉ là tốt) và bạn sẽ chỉ cần cẩn thận khi giải nén:

runId (Pure x) = x 
runId (Free (Const ab)) = absurd ab 

Tất cả những điều này, Tất nhiên, chỉ là "đạo đức" tương đương với Identity, bởi vì tất cả đều giới thiệu các giá trị bổ sung. Cụ thể, chúng tôi có thể phân biệt trong số

bottom 
Pure bottom 
Free bottom