标签: combinators

我一直在阅读关于组合器的信息,看看它们有多大用处(例如,在Haskell的Parsec中).我的问题是,我不太确定如何实际使用它们.

以下是问题的概述:可以生成,过滤和修改分布.可以组合分布以创建新的分布.

基本接口是(伪Haskell类型术语):

generator::      parameters -> distribution

selector::       parameters -> (distribution -> distribution)

modifier::       parameters -> (distribution -> distribution)

现在,我认为我看到了三个组合器:

combine::     generator -> generator -> generator

filter::      generator -> selector -> generator

modify::      generator -> modifier -> generator

这些实际上是组合器吗？组合器是否有意义/是否还有其他明显的组合器我缺少？

谢谢你的建议.

我正在完成20个中级Haskell练习,这是一个非常有趣的练习.它涉及到执行类型类的各种实例Functor和Monad(而这需要职能FunctorS和MonadS作为参数),但像可爱的名字Furry和Misty掩饰我们正在做什么(一些有趣的代码使).

我一直试图以无点的方式做一些这样的事情,我想知道是否有一个将点 - 完全(？)定义转变为无点定义的一般方案.例如,以下是类型类Misty:

class Misty m where
  unicorn :: a -> m a
  banana :: (a -> m b) -> m a -> m b

(函数unicorn和banana是,return并且>>=,如果不是很明显),这是我的apple(相当于flip ap)的实现:

apple :: (Misty m) => m a -> m (a -> b) -> m b
apple x f = banana (\g -> banana (unicorn …

我正在尝试stack使用定点组合器在lambda演算中定义数据结构.我试图定义两个操作,insertion以及removal元素,所以,push和pop,但是我能够定义的唯一一个,插入,不能正常工作.删除我无法弄清楚如何定义.

这是我对push操作的方法,我的定义是stack:

Stack definition:
STACK = \y.\x.(x y)
PUSH = \s.\e.(s e)

我的堆栈初始化为一个元素来指示底部; 我在0这里使用:

stack = STACK 0 = \y.\x.(x y) 0 = \x.(x 0)       // Initialization
stack = PUSH stack 1 = \s.\e.(s e) stack 1 =     // Insertion
    = \e.(stack e) 1 = stack 1 = \x.(x 0) 1 =
    = (1 0)

但是现在,当我尝试插入另一个元素时,它不起作用,因为我的初始结构已被解构.

如何修复STACK定义或PUSH定义,以及如何定义POP操作？我想我将不得不应用组合器,以允许递归,但我无法弄清楚如何做到这一点.

参考: …

你能解释一下表达式的含义((.).(.))吗？据我所知(.)有类型(b - > c) - >(a - > b) - > a - > c.

定点组合器为匿名函数提供了一种引用自身或构建相互递归结构的方法.尽管在lambda演算中有用,但它们在现代编程语言中基本上是多余的,因为大多数(如果不是全部)支持递归,lambdas和闭包.

此外,定点组合器可以使递归构造像左递归语法分析器终止.考虑Lickman 1995,他证明了他的实现终止但从未真正提到它是如何工作的(它只是从格理论到haskell实现的逐步推导)以及为什么他需要一种已经支持递归的语言中的定点组合器本身.

它是如何工作的,为什么他需要一个定点组合器？

我发现很难找到onHaskell 中的示例，而且我不明白 HoogleData.Function页面上的解释。请问，我可以提供其使用示例以及使用它使解决方案更简单或更高效的问题/代码示例吗？

我有这个代码:

var s1 = new Subject<Unit>();
var s2 = new Subject<Unit>();
var ss = s1.Merge(s2).Finally(() => Console.WriteLine("Finished!"));

ss.Subscribe(_ => Console.WriteLine("Next"));

s1.OnNext(new Unit());
s2.OnNext(new Unit());
s1.OnCompleted(); // I wish ss finished here.
s2.OnCompleted(); // Yet it does so here. =(

我已经使用OnError(new OperationCanceledException())解决了我的问题,但我想要一个更好的解决方案(必须有一个组合器吗？).

我现在明白了类型签名s (s k):

s (s k)  :: ((t1 -> t2) -> t1) -> (t1 -> t2) -> t1

我可以在Haskell WinGHCi工具中创建无错误的示例:

示例:

s (s k) (\g -> 2) (\x -> 3)

回报2.

示例:

s (s k) (\g -> g 3) successor

回报4.

其中successor定义如下:

successor = (\x -> x + 1)

尽管如此,我仍然没有一个直观的感受了什么s (s k)呢.

该组合子s (s k)采取任何两个函数f和g.什么是s (s k)用做f …

我一直在研究禁止使用def-before-def并且没有可变单元格(no set!或setq)的语言如何提供递归.我当然跑过(着名的？臭名昭着的？)Y组合者和朋友,例如:

• http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
• http://okmij.org/ftp/Computation/fixed-point-combinators.html
• http://www.angelfire.com/tx4/cus/combinator/birds.html
• http://en.wikipedia.org/wiki/Fixed-point_combinator

当我以这种方式实现"letrec"语义时(也就是说,允许定义一个局部变量使得它可以是一个递归函数,在封面下它不会引用它自己的名字),组合器我最后写的看起来像这样:

Y_letrec = ?f . (?x.x x) (?s . (?a . (f ((?x.x x) s)) a))

或者,将U组合子分解出来:

U = ?x.x x
Y_letrec = ?f . U (?s . (?a . (f (U s)) a))

读这个:Y_letrec是一个带有待递归函数的函数f. f必须是一个单参数函数,它接受s,可以调用实现自递归s的函数f.f期望定义并返回执行"实际"操作的"内部"函数.该内部函数接受参数a(或者在一般情况下接受参数列表,但不能用传统的表示法表示).调用Y_letrec的结果是调用的结果 f,并且它被假定为"内部"函数,准备被调用.

我这样设置的原因是我可以直接使用待递归函数的解析树形式,而无需修改,只是在处理letrec时转换期间在其周围包裹一个额外的函数层.例如,如果原始代码是:

(letrec ((foo (lambda (a) (foo (cdr a))))))

然后转换后的形式将是:

(define foo (Y_letrec (lambda (foo) (lambda (a) (foo (cdr a))))))

请注意,内部函数体在两者之间是相同的. …

我认为这不能称为"定点递归",因为它太简单了.但是,我最近意识到它实际上可能是.

我有效地实现了定点递归吗？

这是有问题的功能:

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

这是一些额外的背景:

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