JavaScript 를 이용 하여 Y 조합 자 를 유도 합 니 다.

9726 단어
Y 그룹 에 대해 서.
Y 조합 자 는 lambda 연산 의 일부분 으로 존 치 이론 적 인 것 에 속한다.
lambda 연산 은 이름 을 정의 할 수 없 지만 재 귀 는 이름 을 통 해 함수 자 체 를 호출 해 야 합 니 다.그렇다면 어떻게 익명 재 귀 함 수 를 구축 합 니까?이것 이 바로 Y 조 합자 가 해결 해 야 할 문제 다.
간단 한 예 를 들 어 일반적인 재 귀 함수:
//        n+(n-1)+(n-2)+...+1+0
var sum = (n) => {
  if (n===0) {
    return 0
  } else {
    //   “sum”      ，        
    return n+sum(n-1)
  }
}

어떤 신기 한 힘 (Y 조합 자) 이 있 습 니까? 재 귀 함 수 를 아래 의 형식 으로 바 꿉 니 다.
// Y    Y   ，sumR    sum recursion
var sum = Y((sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      //               
      // sumR    sum recursion
      return n+sumR(n-1)
    }
  }
})

자신 을 인용 하지 않 고 재 귀 를 이 루 고 있 습 니 다.
이것 이 바로 오늘 우리 가 해 야 할 일이 다.이 신기 한 힘 을 찾 아 라.
유도 과정
유도 과정 은 이해 하기 어렵 기 때문에 이 과정 을 두 부분 으로 나 누 었 다.
첫 번 째 부분 에서 하나의 일반 함수 에 대해 일련의 변 화 를 하여 재 귀 를 실현 할 수 있 는 함 수 를 도 출 한다.
두 번 째 부분 에서 이 재 귀 함수 에 대해 등가 의 전환 을 하고 이 재 귀 함수 에서 Y 조합 자 를 추출 합 니 다.
제1 부분
함수 에서 자신 을 인용 할 수 없 기 때문에, 우 리 는 먼저 몇 개의 함 수 를 정의 합 니 다.
// eternity   ，             。        。
//      console.error       ，       。。
var eternity = () => {
  // while(true) {}
  console.error('you are in eternity')
}

// sum0   ，        0    ，           ，      。。
var sum0 = (n) => {
  if (n===0) {
    return 0
  } else {
    return n+eternity()
  }
}

// sum1   ，        0, 1    
var sum1 = (n) => {
  if (n===0) {
    return 0
  } else {
    return n+sum0(n-1)
  }
}

// sum2   ，        0, 1, 2    
var sum2 = (n) => {
  if (n===0) {
    return 0
  } else {
    return n+sum1(n-1)
  }
}

만약 이렇게 계속 정의 할 수 있다 면, 우 리 는 충분 한 n 을 처리 할 수 있 는 함 수 를 정의 할 수 있 을 것 이다.
위의 sum 0, sum 1, sum 2 를 살 펴 보면 비슷 한 점 이 많 고 자 연 스 럽 게 mkSum 을 정의 하여 생 성 해 야 한다 고 생각 합 니 다.
//    sumN   
var mkSum = (fn) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+fn(n-1)
    }
  }
}

var sum0 = mkSum(eternity)
var sum1 = mkSum(sum0)
var sum2 = mkSum(sum1)

이렇게 하면 눈 에 띄 는 게 많아 요. 그 렇 죠?
다음 중요 한 곳 이 오 겠 습 니 다. 집 중력 에 주의 하 세 요.
eternity 함 수 는 영원히 실행 할 수 없 기 때문에, 그렇다면, 나 는 왜 다른 함수 로 바 꾸 지 않 습 니까?어떤 함수 로 바 꿔 도 똑 같 습 니 다. 그럼 제 가...
eternity 를 mksum 으로 바 꿔 주세요.
var sum0 = mkSum(mkSum)
var sum1 = mkSum(sum0)
var sum2 = mkSum(sum1)

관찰 하기 편리 하도록 sum 1, sum 2 를 펼 쳐 다음 과 같이 얻 을 수 있 습 니 다.
var sum0 = mkSum(mkSum)
var sum1 = mkSum(mkSum(mkSum))
var sum2 = mkSum(mkSum(mkSum(mkSum)))

위의 세 함수 정 의 를 자세히 보 세 요. 무엇 을 알 아 냈 습 니까?
맞다!이 세 가지 함 수 는 모두 mkSum 이 조합 하여 만 든 것 입 니 다!!Σ(っ °Д °;)っ
자세히 살 펴 보면 sum 이 처리 할 n 이 n + 1 로 변 할 때마다 가장 안쪽 에 있 는 mkSum 을 mkSum (mkSum) 으로 바 꾸 면 됩 니 다.
sum 0 의 맨 안쪽 mkSum 을 mkSum (mkSum) 으로 바 꾸 면 sum 1 입 니 다.같은 이치 로 sum 1 의 맨 안쪽 mkSum 을 mkSum (mkSum) 으로 바 꾸 면 sum 2 가 됩 니 다.
어 때? 돌아 오 는 냄새 좀 맡 았 지?가장 중요 한 것 은 필요 할 때 mkSum 을 mkSum (mkSum) 으로 어떻게 바 꾸 느 냐 하 는 것 이다.
만약 이 점 을 할 수 있다 면 우 리 는 재 귀 를 실현 할 수 있 을 것 이다.(ΦωΦ)
다음은 sum 0 을 보 여 드 리 겠 습 니 다. sum 0 에서 mkSum 에 게 전 달 된 매개 변 수 는 그 자체 이기 때 문 입 니 다. mkSum 의 매개 변수 이름 을 바 꿔 보 겠 습 니 다. mkSum 을 구별 하기 위해 mkSum 1 로 바 꾸 겠 습 니 다.
//       mkSum1              mkSum
var mkSum = (mkSum1) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+mkSum1(n-1)
    }
  }
}

var sum0 = mkSum(mkSum)

앞서 언급 했 듯 이 사상 을 유도 하 는 관건 은 필요 할 때 mkSum 을 mkSum (mkSum) 으로 바 꾸 는 것 이다.
그럼 언제 가 필요 할 까요? 그렇습니다. 바로 귀속 함수 가 자신 을 호출 하려 고 할 때 입 니 다!
그래서 우 리 는 mkSum 을 아래 의 모습 으로 개조 했다.
//             。    。(￣ω￣)
var mkSum = (mkSum1) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      //    ！    ！！  mkSum    mkSum(mkSum)
      return n+mkSum1(mkSum1)(n-1)
    }
  }
}

//       ，   sum0      sum  
var sum = mkSum(mkSum)

여기 가 바로 유도 과정 에서 가장 관건 적 이 고 이해 하기 어 려 운 부분 입 니 다. 이 단계 에 이 르 러 재 귀 효 과 를 실 현 했 고 sum 은 완벽 하 게 운행 할 수 있 습 니 다.
다음은 mkSum 함수 에 대해 등가 전환 을 하여 진정한 Y 조합 자 를 추상 화 하 는 것 입 니 다. 그러나 위의 부분 을 알 아야 아래 의 내용 을 계속 볼 수 있 습 니 다.
제2 부분
진정한 Y 조합 을 추상 화하 다
작은 방법
아래 의 추론 에 앞서 여러분 이 아래 의 내용 을 잘 이해 할 수 있 도록 작은 방법 을 쓰 고 아래 의 추론 에서 많은 부분 을 사 용 했 습 니 다.
그것 은 함수 중의 일부 내용 을 어떻게 추출 하여 매개 변수 로 하 는 것 입 니까?
var d = 1, e = 2
//    
var a = c => {
  var b = d + e
  return b + c
}

//     ，  b           ，         
var aCreator = b => c => b+c
var a = aCteator(d+e)

a(10)

다음 내용 에서 특정한 것 을 추출 하여 매개 변수 형식 으로 바 꾸 는 것 과 관련 된 표현 은 모두 이런 방법 을 이용 한 것 이다.
우선, 우 리 는 mkSum 함수 의 형식 을 간단하게 바 꾸 고 mkSum 1 (mkSum 1) 을 추출 하여 매개 변수 형식 으로 바 꿉 니 다.
var mkSum = (mkSum1) => {
  var sumR = mkSum1(mkSum1)
  
  // sumFn       Y        ？！
  var sumFn = (sumR) => {
    (n) => {
      if (n===0) {
        return 0
      } else {
        //     mkSum1(mkSum1)       ，   sumR
        return n+sumR(n-1)
      }
    }
  }

  return sumFn(sumR)
}

var sum = mkSum(mkSum)

간단 한 추출 입 니 다. 이 함수 로 sum (3) 을 실행 해 보 시 겠 습 니까?
어 머?? 아까 는 멀쩡 했 는데 왜 갑자기 창고 가 터 졌어?Д°)
구체 적 인 원인 은 설명 하지 않 고 잘 생각해 보면 답 이 나온다.
스 택 폭발 문 제 를 해결 하기 위해 mk Sum 1 (mk Sum 1) 밖 에 함 수 를 한 층 싸 면 됩 니 다.
var mkSum = (mkSum1) => {
  //          ，       
  var sumR = (x) => mkSum1(mkSum1)(x)
  
  var sumFn = (sumR) => {
    return (n) => {
      if (n===0) {
        return 0
      } else {
        return n+sumR(n-1)
      }
    }
  }

  return sumFn(sumR)
}

var sum = mkSum(mkSum)

다음은 sum 의 mkSum 추출 을 매개 변수 형식 으로 바 꿉 니 다.
var mkSum = (mkSum1) => {
  var sumR = (x) => mkSum1(mkSum1)(x)
  
  var sumFn = (sumR) => {
    return (n) => {
      if (n===0) {
        return 0
      } else {
        return n+sumR(n-1)
      }
    }
  }
  
  return sumFn(sumR)
}

var w = f => f(f)
//     mkSum(mkSum)       w
var sum = w(mkSum)

우 리 는 다시 sumfn 을 mkSum 밖으로 추출 하여 매개 변수 형식 으로 바 꿉 니 다.
//        sumFn
var sumFn = (sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
}

var mkSumCreator = (sumFn) => (mkSum1) => {
  var sumR = (x) => mkSum1(mkSum1)(x)
  return sumFn(sumR)  //     sumFn        
}
var mkSum = mkSumCreator(sumFn)

var w = f => f(f)
var sum = w(mkSum)

다시 빵 한 층 함수 로 Y 조합 자의 원형 으로
var sumFn = (sumR) => {
  return (n) => {
    if (n === 0) {
      return 0
    } else {
      return n + sumR(n - 1)
    }
  }
}

//             ，       Y       
var poorY = () => {
  var mkSumCreator = (sumFn) => (mkSum1) => {
    var sumR = (x) => mkSum1(mkSum1)(x)
    return sumFn(sumR)
  }
  var mkSum = mkSumCreator(sumFn)
  var w = f => f(f)

  return w(mkSum)
}

var sum = poorY()

마지막 으로 최종 효 과 를 살 펴 보 자.
var sumFn = (sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
}
var sum = Y(sumFn)

어떻게 하면 이런 식 으로 변 할 수 있 을 까? 이 단 계 는 분명 하지 않 기 때문에 자세히 살 펴 봐 야 할 것 같다.
우 리 는 poory 에 인자 sumfn 을 추가 하고 가장 외부 sumfn 을 매개 변수 로 전달 하면 됩 니 다.
var sumFn = (sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
}

//   poorY        sumFn
var poorY = (sumFn) => {
   // poorY             
  var mkSumCreator = (sumFn) => (mkSum1) => {
    var sumR = (x) => mkSum1(mkSum1)(x)
    return sumFn(sumR)
  }
  var mkSum = mkSumCreator(sumFn)
  var w = f => f(f)
  return w(mkSum)
}

// sumFn          poorY，         
var sum = poorY(sumFn)

이때, 수많은 Y 그룹 이 드디어 나 옵 니 다. 보이 시 나 요?!
poory 내부 의 mkSumCreator 가 직접 호출 되 었 기 때문에 이 를 간소화 할 수 있 습 니 다. 그러면 우 리 는 진정한 Y 조합 을 얻 을 수 있 습 니 다.
var sumFn = (sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
}

var y = (sumFn) => {
  //       
  var mkSum = (mkSum1) => {
    var sumR = (x) => mkSum1(mkSum1)(x)
    return sumFn(sumR)
  }

  var w = f => f(f)
  return w(mkSum)
}

var sum = y(sumFn)

마지막 으로 우 리 는 남 은 이름 을 지우 고 Y 조합 자 를 추출 합 니 다.
var Y = (sumFn) => {
  var w = f => f(f)
  return w(mkSum1 => {
    var sumR = (x) => mkSum1(mkSum1)(x)
    return sumFn(sumR)
  })
}

var sum = Y((sumR) => {
  return (n) => {
    if (n===0) {
      return 0
    } else {
      return n+sumR(n-1)
    }
  }
})

간소화 Y 조합 자:
//      
// w -> (f => f(f))
// mkSum1 -> b
// sumFn -> fn
var Y = fn => 
  (f => f(f))
  (b => fn( x => b(b)(x) ))

앞서 mkSum 과 mkSum 1 은 엄 격 히 구별 할 필요 가 없다 고 말 했 습 니 다. 그 러 니 더 (그러므로) 간 (신) 화 (비) 를 위해 서 는 모두 f 로 교체 합 시다.
최종 Y 그룹:
var Y = fn => 
  (f => f(f))
  (f => fn( x => f(f)(x) ))

//     f => f(f)   
var Y = fn => 
  (f => fn( x => f(f)(x) ))
  (f => fn( x => f(f)(x) ))

세심 한 친 구 는 이 Y 조합 자가 생 성 한 재 귀 함수 가 하나의 매개 변수, 즉 Y 그룹 합 자 안의 x 만 처리 할 수 있다 는 것 을 알 아야 합 니 다. 따라서 우 리 는 Y 조합 자가 생 성 한 재 귀 함수 가 매개 변수 에 제한 을 받 지 않도록 수정 할 수 있 습 니 다.
var Y = fn => 
  (f => f(f))
  (f => fn( (...x) => f(f)(...x) ))

엔 딩
추론 은 여기 서 끝 이 야. 알 겠 어? 없 으 면...
다음 글 을 참고 할 수 있 습 니 다.https://zhuanlan.zhihu.com/p/20616683 (이 글 은 더욱 투철 하 게 말한다).
또는 의 9 장 을 읽 어 보 세 요.
마지막 으로 지적 하고 자 하 는 것 은 실제 응용 에서 재 귀적 실현 은 Y 조합 자 에 의 해 이 루어 지 는 것 이 아니 라 함수 의 인용 (예 를 들 어 지침) 을 먼저 저장 한 다음 에 필요 할 때 지침 을 통 해 자신의 함 수 를 호출 하 는 것 이다. 이것 은 우리 의 직관 과 부합된다.
그래서 Y 조 합 자 를 이해 하 는 것 은 아무 소 용이 없다. 그저 심심 해서 학 대 를 찾 을 뿐이다.
[JAVA] 백준 1018 - 체스판 다시 칠하기
React 개발환경 갖추기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage