标签: y-combinator

在Clojure中为单个参数函数(如factorial或fibonacci)执行Y-Combinator已有详细记录:http: //rosettacode.org/wiki/Y_combinator#Clojure

我的问题是 - 你如何为两个参数函数这样做,例如这个getter？

(这里假设我想以递归方式解决这个问题,这个非惯用的clojure代码是故意出于另一个原因)

[非y组合器版]

(defn get_ [n lat]
    (cond
      (empty? lat) ()
        (= 0 (- n 1)) (first lat)
        true (get_ (- n 1) (rest lat))))

(get_ 3 '(a b c d e f g h i j))

我注意到执行动作的常见模式,直到它停止具有某些效果,当一个人知道这表示一个固定点时(即,没有未来的效果).这是一个类型类吗？

这是MonadFix所涵盖的吗？看着代码,它似乎会是,但我被维基页面吓到了"它很诱人看到"递归"并猜测它意味着递归或重复执行动作.不."

在我看来,固定点就像是身份的双重性.也就是说,当与非身份相结合时,身份会消失(0代表(+),1代表(*),[]代表追加等).而固定点导致任何非固定点在下面的"放松"操作下消失.有没有办法正式化这种二元性,这样做有用吗？即,MonadPlus和/或Monoid和MonadRelax之间是否存在关系？

最后,我注意到放松几乎是展开/变形.表达它会更好吗？

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

import Control.Monad.Loops (iterateUntilM) -- cabal install monad-loops

-- states that relax to a fixed point under step
class Monad m => MonadRelax m s | s -> m where
isFixed :: s -> Bool
step :: s -> m s -- often (not always): step s = return s iff isFixed s

relax :: MonadRelax m s => s -> m s
relax = iterateUntilM isFixed step

经过一个小时的尝试了解Y-Combinator ......我终于明白了,但大部分时间我意识到没有它可以实现同样的事情......虽然我不确定我是否完全理解它的目的.

例如.使用Y-Combinator的因子

print (lambda h: (lambda f:f(f))(lambda f: h(lambda n: f(f)(n))))(lambda g: lambda n: n and n * g(n-1) or 1)(input())

因子在另一个lambda中引用了该函数

print (lambda f,m:f(f,m))((lambda g,n: n and n * g(g,n-1) or 1),input())

任何人都可以告诉我,如果在python中有Y-Combinator的目的吗？

注意：这是一种家庭作业，而不是一种 - 最终目标是拥有一个函数，该函数生成一组数字的幂集，作为数字列表提供给该函数。我有函数的递归版本，但现在我需要找到解决方案我有（替换每个明确递归函数的一些方法append，mapm等等）与只相当于λ-表达。

因此，我从较小的问题开始，并希望将它们全部结合起来编写一个完整的函数。我已经设法使用纯 lambda（Y 组合子）提出了一个非递归阶乘函数，但我现在正在尝试提出一个很好的函数，该函数可以对列表中的每个数字进行平方——尝试在跳转之前解决较小的问题直到一个乘法递归函数：

(define (sqrlist numlist)
  (((lambda (f)
   ((lambda (x) (x x))
    (lambda (g)
     (f (lambda (x) ((g g) x))))))
  (lambda (f)
   (lambda (x)
    (cons (sqr (first x)) (rest x))))) numlist))

上面的代码不会递归，尽管在它之前存在 Y 组合器——我显然在将正确的参数传递给其中的函数时遇到了一些问题——有什么想法吗？

我正在尝试构建一个具有递归能力的 lambda 自作用域的干净整洁的实现（这基本上是一个 Y 组合器，尽管我认为技术上不完全）。这是一个旅程，它带我到许多其他人中，这个线程，这个线程和这个线程。

我已经尽可能干净地归结了我的问题之一：如何传递以 lambda 作为模板参数的模板化函子？

#include <string>
#include <iostream>
#define uint unsigned int

template <class F>
class Functor {
public:
    F m_f;

    template <class... Args>
    decltype(auto) operator()(Args&&... args) {
        return m_f(*this, std::forward<Args>(args)...);
    }
};
template <class F> Functor(F)->Functor<F>;

class B {
private:
    uint m_val;
public:
    B(uint val) : m_val(val) {}
    uint evaluate(Functor<decltype([](auto & self, uint val)->uint {})> func) const {
        return func(m_val);
    }
};

int main() {
    B b = B(5u); …

这是代码(也在这里):

#lang racket
(define poorY
  ((lambda length
    (lambda (ls)
      (cond
        [(null? ls) 0]
        [else (add1 ((length length) (cdr ls)))])))
  (lambda length
    (lambda (ls)
      (cond
        [(null? ls) 0]
        [else (add1 ((length length) (cdr ls)))])))))

当我运行它:

> (poorY '(9 7 8))
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: '(#<procedure>)
  arguments...:
   '(#<procedure>)

屏幕截图如下所示:

我正在使用DrRacket作为代表.代码有什么问题？

这是Racket中的Y-combinator:

#lang lazy

(define Y (?(f)((?(x)(f (x x)))(?(x)(f (x x))))))

(define Fact
  (Y (?(fact) (?(n) (if (zero? n) 1 (* n (fact (- n 1))))))))
(define Fib
  (Y (?(fib) (?(n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))))))

这是Scheme中的Y-combinator:

(define Y
  (lambda (f)
    ((lambda (x) (x x))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

(define fac
  (Y
    (lambda (f)
      (lambda (x)
        (if (< x 2)
            1
            (* x …