Bộ kết hợp điểm cố định cho các chức năng đệ quy hai bên?

Question

Có một bộ kết hợp điểm cố định để tạo các bộ dữ liệu đệ quy có chức năng đệ quy không? I E. Tôi đang tìm một cái gì đó giống như Y-Combinator nhưng có nhiều chức năng "đệ quy", và sẽ trả về một bộ chức năng?

*: không thực sự đệ quy tất nhiên, vì chúng được viết để tự mình (và anh chị em) làm đối số, theo cách thông thường của Y-Combinator.

Answer 1

Sinh vật bạn đang tìm kiếm là Y * bộ kết hợp.

Căn cứ vào this page by oleg-at-okmij.org tôi chuyển các Y * để Clojure:

(defn Y* [& fs] 
    (map (fn [f] (f)) 
    ((fn [x] (x x)) 
     (fn [p] 
     (map 
      (fn [f] 
      (fn [] 
       (apply f 
       (map 
        (fn [ff] 
        (fn [& y] (apply (ff) y))) 
        (p p))))) 
      fs))))) 

Các ví dụ điển hình của hàm đệ quy lẫn nhau là chẵn/lẻ vì vậy đây là ví dụ:

(let 
    [[even? odd?] 
    (Y* 
    (fn [e o] 
     (fn [n] 
     (or (= 0 n) (o (dec n))))) 
    (fn [e o] 
     (fn [n] 
     (and (not= 0 n) (e (dec n))))) 
    ) 
    ] 
    (do 
    (assert (even? 14)) 
    (assert (odd? 333)) 
    )) 

Bạn có thể dễ dàng thổi các ngăn xếp với các chức năng này nếu bạn sử dụng các đối số đủ lớn, do đó, đây là phiên bản trampolined của nó cho ví dụ đầy đủ mà không tiêu thụ ngăn xếp ở tất cả:

(let 
    [[even? odd?] 
    (Y* 
    (fn [e o] 
     (fn [n] 
     (or (= 0 n) #(o (dec n))))) 
    (fn [e o] 
     (fn [n] 
     (and (not= 0 n) #(e (dec n))))) 
    ) 
    ] 
    (do 
    (assert (trampoline even? 144444)) 
    (assert (trampoline odd? 333333)) 
    )) 

Các Y * combinator là rất hữu ích cho việc xác định các định nghĩa đệ quy lẫn nhau về parsers monadic, trong đó tôi sẽ viết blog sớm trên lambder.com, chơ;)

- Lambder

Answer 2

Tôi không hoàn toàn chắc chắn về điều này. Tôi vẫn đang cố gắng tìm một bằng chứng chính thức về nó. Nhưng có vẻ như với tôi bạn không cần. Trong Haskell, nếu bạn có một cái gì đó như:

sửa chữa :: (a -> a) -> một
sửa chữa f = để x = fx trong x

chính = hãy {x =. .. y ...; y = ... x ...} trong x

bạn có thể viết lại chính để

chính = fst $ sửa chữa $ \ (x, y) -> (... y .. ., ... x ...)

Nhưng như tôi đã nói, tôi không chắc chắn 100% về điều này.

Answer 3

Trang web sau đây mô tả chi tiết các bộ phối hợp điểm cố định cho phép đệ quy lẫn nhau (bộ kết hợp điểm cố định polyvariadic). Nó xuất phát đơn giản nhất cho đến nay combinator. http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

Để dễ dàng tham khảo, đây là combinator polyvariadic đơn giản nhất trong Haskell (one-liner)

fix_poly:: [[a]->a] -> [a] 
fix_poly fl = fix (\self -> map ($ self) fl) 
    where fix f = f (fix f) 

và ở đây nó là trong Đề án, một ngôn ngữ nghiêm ngặt

(define (Y* . l) 
    ((lambda (u) (u u)) 
    (lambda (p) 
     (map (lambda (li) (lambda x (apply (apply li (p p)) x))) l)))) 

Hãy xem trang web để biết các ví dụ và thảo luận thêm.