Đây có phải là việc triển khai bộ kết hợp điểm cố định không?

Question

Tôi cho rằng điều này không thể được gọi là "đệ quy điểm cố định" vì nó quá đơn giản. Tuy nhiên, gần đây tôi đã nhận ra nó thực sự có thể là.

Tôi đã triển khai hiệu quả đệ quy điểm cố định chưa?

Dưới đây là các chức năng trong câu hỏi:

/* recursive kleisli fold */ 
var until = function(f) { 
    return function(a) { 
     return kleisli(f, until(f))(a); 
    }; 
}; 

Dưới đây là một số bối cảnh thêm:

// The error monad's bind 
var bind_ = function(f, m) { return m.m === Success ? f(m.a) : m; }; 

var bind = function(f, m) { 
    return m !== undefined && m.m !== undefined && m.a !== undefined ? bind_(f, m) : m; 
}; 

var kleisli = function(f1, f2) { 
    return function(a) { 
     return bind(f2, f1(a)); 
    }; 
}; 

Phần còn lại của mã này là here, nhưng đoạn trên là đủ để làm theo.

Answer 1

Định nghĩa của một combinator điểm cố định là một hàm F mà phải mất một chức năng f và trả về một chức năng p mà

Với F(f) = p sau đó p = f(p)

Có rất nhiều combinators điểm cố định có thể là có thể bằng văn bản. Đừng để sự thẳng thắn khiến bạn nghĩ rằng cái gì đó không phải là một bộ kết hợp điểm cố định; đây là một định nghĩa tiêu chuẩn trong JavaScript, rất đơn giản:

var fix = function(f) { 
     return function(x) { 
     return f(fix(f))(x) 
     } 
    }; 

Một sử dụng có thể là sau đó để tính toán điểm cố định cho giai thừa, với:

var fact = function(f) { 
       return function(n) { return (n == 0) ? 1 : (n * f(n - 1)) } 
      }; 

alert(fix(fact)(7)); // alerts us with 5040. 

Đối với một ví dụ về một cố định khác nhau bộ kết hợp điểm (bộ kết hợp Y) xem this helpful blog post.

Hãy xem liệu bộ phối hợp until có tính điểm cố định không. Kể từ khi bạn đang làm việc với các chức năng monadic những thay đổi định nghĩa cố định điểm nhẹ để xử lý các cấu trúc monadic, nơi F là một (monadic) cố định điểm combinator khi

Với F(f) = p sau đó p = f* . p

nơi f* . p nghĩa thành phần Kleisli chức năng p với chức năng f (trong mã của bạn, bạn sẽ viết này kleisli(p, f), bạn có thể nghĩ về * là bind). Tôi sẽ sử dụng ký hiệu này vì nó ngắn hơn viết JavaScript.

Hãy cuộn định nghĩa của until sau đó và xem những gì chúng tôi nhận được:

until(f) = (until(f))* . f 
     = (until(f)* . f)* . f 
     = ((... . f)* . f)* . f 
     = ... . f* . f* . f  (associativity of bind for a monad: (g* . f)* = g* . f*) 
     = p 

Liệu p = f* . p?

... . f* . f* . f =?= f* . ... . f* . f* . f 

Vâng- tôi tin như vậy. Mặc dù tôi không nghĩ đây là điểm cố định hữu ích. (Tôi e rằng mình không có tranh luận tốt về điều này - nhưng tôi nghĩ đây về cơ bản là điểm cố định lớn nhất sẽ chỉ phân tán).

Đối với tôi, có vẻ như các đối số cho kleisli trong until phải được đổi chỗ.Nghĩa là, chúng ta muốn làm tương đương Kleisli áp dụng trong ví dụ fix, vì vậy chúng tôi cần phải vượt qua kết quả monadic của cuộc gọi đệ quy until(f) để f:

var until = function(f) { 
     return function(a) { 
      return kleisli(until(f), f)(a); 
     }; 
    }; 

Hãy cuộn định nghĩa mới này của until:

until(f) = f* . until(f) 
     = f* . (f* . until(f)) 
     = f* . f* . ... 
     = p 

Có p = f* . p không? Có:

f* . f* ... = f* . (f* . f* . ...) 

vì thêm một thành phần khác của f * vào một chuỗi vô hạn của thành phần f * có cùng chức năng.

Sử dụng hàm kleisli Tôi gặp một số vấn đề với phân kỳ (một số đánh giá diễn ra quá sớm để tính toán chạy cho đến khi hết dung lượng ngăn xếp). Thay vào đó, sau đây dường như làm việc cho tôi:

var until = function(f) { 
    return function(a) { 
     return bind(f,until(f)(a)); 
    }; 
}; 

Để biết thêm về cố định điểm cho mã monadic bạn có thể muốn kiểm tra the work of Erkök and Launchbury.