이것은 고정 점 결합기의 구현입니까?

Question

너무 간단하기 때문에 이것을 "고정 소수점 재귀"라고 부를 수는 없습니다. 그러나, 나는 그것이 실제로 있을지도 모른다는 것을 최근에 깨달았다.

고정 소수점 재귀를 효과적으로 구현 했습니까? 코드의

// 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)); 
    }; 
}; 

나머지는 here이지만, 위의 조각은 따라하기에 충분해야합니다

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

는 여기에 몇 가지 추가 컨텍스트이다 :

여기서 문제가되는 기능입니다.

Answer 1

고정 소수점 콤비의 정의는

을 감안할 때 F(f) = p 다음 p = f(p)

될 수있는 많은 가능한 고정 소수점 콤비가 있다는 것을 p 같은 기능을하는 함수 f를 받아 반환하는 함수 F입니다 쓴. 직설로 인해 무언가가 고정 소수점 결합자가 아니라고 생각하게하지 마십시오. 사용 현황은 계승을위한 고정 소수점을 계산하기 위해 다음 수 있습니다

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

과 :

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

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

다른 고정의 예를 들어 여기에 매우 간단합니다 자바 스크립트의 표준 정의입니다 (Y combinator)는 this helpful blog post을 참조하십시오.

귀하의 until 조합자가 고정 소수점을 계산하는지 봅시다. 만약 모나드 기능 작동되므로

감안 F(f) = p 다음 p = f* . p

가 f* . p가 Kleisli 조성물 곳을 의미 할 때 고정 소수점 정의 변화는 약간 F는 (모나드) 고정 소수점 연결자이다 모나드 구조를 처리하도록 기능이 이고 코드가 kleisli(p, f)이라면 *을 bind으로 생각할 수 있습니다. 이 표기법은 JavaScript를 작성하는 것보다 짧기 때문에 사용하겠습니다.

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 

이 p = f* . p을 수행

은의 다음 until의 정의를 풀다 우리가 무엇을 얻을 보자?

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

예 - 그렇게 생각합니다. 비록 이것이 유용한 고정 점이라고 생각하지는 않지만. (나는 아직 이것에 대해 좋은 논점을 갖고 있지 않다는 것을 두려워하지만, 이것이 기본적으로 갈라지는 가장 큰 고정 점이라고 생각한다.)

kleisli에 대한 인수가 until으로 바뀌어야합니다.

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

이의이 until의 새로운 정의를 풀다 보자 : 그것은 우리가 fix 예제 응용 프로그램의 Kleisli 동등한을하고자하는, 그래서 우리는 f에 재귀 호출 until(f)의 모나드 결과를 전달해야한다

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

p = f* . p? 예 :

f * 구성의 무한 사슬에 f * 성분을 하나 더 추가하는 것이 동일한 기능이기 때문에 가능합니다.

kleisli 함수를 사용하여 분산 문제가 발생했습니다 (일부 평가가 너무 빨리 이루어져서 스택 공간이 부족할 때까지 계산이 실행됩니다). 대신, 다음은 나를 위해 작동하는 것 같다 : the work of Erkök and Launchbury을 체크 아웃 당신이 좋아하는 수 모나드 코드에 대한 고정 점에 대한 자세한 내용은

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

.