Vòng lặp có điều kiện trong hàm Functor

Question

Giả sử rằng Parser x là trình phân tích cú pháp phân tích cú pháp x. Trình phân tích cú pháp này có thể sở hữu bộ kết hợp many, phân tích cú pháp 0 hoặc nhiều lần xuất hiện của một thứ gì đó (dừng khi trình phân tích cú pháp mục không thành công).

Tôi có thể xem cách người ta có thể thực hiện điều đó nếu Parser tạo thành một đơn vị. Tôi không thể tìm ra cách để làm điều đó nếu Parser chỉ là một Functor ứng dụng. Dường như không có cách nào để kiểm tra kết quả trước đó và quyết định làm gì tiếp theo (chính xác khái niệm mà các monads thêm). Tôi đang thiếu gì?

Answer 1

Các kiểu lớp Alternative cung cấp many combinator:

class Applicative f => Alternative f where 
    empty :: f a 
    (<|>) :: f a -> f a -> f a 
    many :: f a -> f [a] 
    some :: f a -> f [a] 

    some = some' 
    many = many' 

many' a = some' a <|> pure [] 
some' a = (:) <$> a <*> many' a 

1. Các many a combinator nghĩa “ zero hoặc nhiều ” a.
2. Máy tổ hợp some a có nghĩa là “ một hoặc nhiều ” a.

Do đó:

1. Các some a combinator trả về một danh sách của một a Tiếp theo many a (ví dụ: 1 + (0 or more)).
2. Máy kết hợp many a trả lại some a hoặc danh sách trống (ví dụ: (1 or more) | 0).

Bộ kết hợp many có thể được xem là toán tử mặc định bằng các ngôn ngữ như JavaScript. Ví dụ, hãy xem xét Alternative thể hiện của Maybe:

instance Alternative Maybe where 
    empty = Nothing 
    Nothing <|> r = r 
    l  <|> _ = l 

Về cơ bản các (<|>) nên trả về giá trị ở phía bên tay trái nếu nó truthy. Nếu không, nó sẽ trả về giá trị bên tay phải.

Một Parser là một cấu trúc dữ liệu được định nghĩa tương tự như Maybe (ý tưởng của applicative lexer combinators và phân tích cú pháp combinators là về cơ bản giống nhau):

data Lexer a = Fail | Ok (Maybe a) (Vec (Lexer a)) 

Nếu phân tích thất bại, giá trị Fail được trả về. Nếu không, giá trị Ok sẽ được trả lại. Kể từ Fail <|> pure [] là pure [], đây là cách trình kết hợp many biết thời điểm dừng và trả về danh sách trống.

Answer 2

many là một phương pháp lớp học của Alternative lớp (link) cho thấy rằng một trình ứng dụng chung không phải lúc nào cũng có triển khai many.

Answer 3

Nó không thể được thực hiện chỉ bằng cách sử dụng những gì được cung cấp bởi Applicative.Nhưng Alternative có chức năng cung cấp cho bạn sức mạnh vượt Applicative:

(<|>) :: f a -> f a -> f a 

Chức năng này cho phép bạn "kết hợp" hai Alternatives mà không cần bất kỳ hạn chế nào về a. Nhưng bằng cách nào? Một cái gì đó nội tại cho cụ thể functor f phải cung cấp cho bạn một phương tiện để làm điều đó.

Thông thường, Alternative s yêu cầu một số khái niệm về thất bại hoặc sự trống rỗng. Giống như đối với các trình phân tích cú pháp, trong đó (<|>) có nghĩa là "hãy thử phân tích cú pháp này, nếu không thành công, hãy thử điều này". Nhưng "sự phụ thuộc vào giá trị trước đó" này là ẩn trong máy móc thực hiện (<|>). Nó không có sẵn cho giao diện bên ngoài, do đó, để nói chuyện.

Từ (<|>), người ta có thể thực hiện một zero-hoặc-one combinator:

optional :: Alternative f => f a -> f (Maybe a) 
optional v = Just <$> v <|> pure Nothing 

Các định nghĩa của some một many tương tự nhưng họ yêu cầu chức năng hai bên đệ quy.

Lưu ý rằng có Applicative s không phải là Alternative s. Bạn không thể làm cho ví dụ Identity functor một số Alternative. Làm thế nào bạn sẽ thực hiện empty?