Tên kiểu mẫu: R a b = Q (a -> (R a b, b))

Question

Tôi đang tìm một số từ vựng ở đây. Có một số hình dạng có tên chung. Ví dụ: L a = Empty | Cons a L Thường được gọi là "danh sách", trong khi T a = Leaf a | Node (T a) (T a) là "cây nhị phân" và St s a :: St (s->(a,s)) là hình thức của Tiểu bang.

Tôi muốn biết nếu một hình dạng như thế này có một cái tên:

data R a b = Q (a -> (R a b,b)) 

Tôi đã nhìn thấy mô hình này trong khuôn khổ Arrow và triển khai máy nhà nước. Chức năng đệ quy làm cho nó cảm thấy một chút giống như một Monad Nhà nước hoặc một Monad Cont. Nó cũng là cấu trúc duy nhất bên cạnh (->) và (>=>) mà tôi đã thấy một thể hiện của Mũi tên được xác định.

Có tên chung cho cấu trúc dữ liệu này không?

Answer 1

Đây là một automaton arrow, còn được gọi là máy Mealy. Ví dụ cụ thể của bạn chỉ sử dụng (->) làm mũi tên cơ bản; một lựa chọn phổ biến khác là Kleisli m đối với một số đơn lẻ m (chỉ cần biến a -> b thành a -> m b; ví dụ: data R a b = Q (a -> MyMonad (b, R a b))).

Nó thường được sử dụng trong functional reactive programming (đặc biệt là arrowised FRP - xem, ví dụ netwire và hai bài đăng trên blog: 1, 2), và có các ứng dụng để xử lý dòng chung chung (như iteratees).

Nó tương tự như một coroutine theo nhiều cách, nhưng đó là một khái niệm cụ thể hơn. Hai bài đăng trên blog mà tôi liên kết gọi chúng là coroutines, vì vậy "coroutine" chắc chắn là một cách phổ biến để chỉ nó, nhưng tên chính xác là một mũi tên automaton.

Answer 2

Tôi sẽ gọi cấu trúc dữ liệu đó là Coroutine.

Nó thể hiện tính toán có thể được kiểm soát song song với một số tính toán khác và có thể được đánh giá theo từng bước. Trong khi giao diện bạn trình bày không phải là giao diện chính xác được sử dụng cho lớp Coroutines trong Haskell (Một Coroutine tổng quát hơn cũng đơn thuần là thuyết bất khả tri, nghĩa là hàm được trả về là m (R a b, b) và coroutines không phải tiêu thụ đầu vào, trong khi bạn ở đây luôn phải cung cấp tính toán với a), nó cũng tương tự như vậy.

Cấu trúc dữ liệu cũng đại diện cho một tập hợp con của những gì được gọi là Comonads.

Answer 3

Loại đó có vẻ liên quan đến loại tôi mong muốn sử dụng cho bộ chuyển đổi - Tôi chỉ mong rằng loại đầu ra là đơn. Wikipedia có một trang trên một loại đầu dò đặc biệt, finite state transducers, đó phải là một điểm khởi đầu tốt cho tìm kiếm văn học.