标签: combinators

在编写简单的RPN计算器的过程中,我有以下类型的别名:

type Stack = List[Double]
type Operation = Stack => Option[Stack]

...我写了一个好奇的Scala代码:

val newStack = operations.foldLeft(Option(stack)) { _ flatMap _ }

这将获取stack值的初始值并应用operations该堆栈的列表.每个操作都可能失败(即产生一个Option[Stack]),所以我对它们进行排序flatMap.对我来说有些不同寻常的事情(在我看来)是我折叠了一系列monadic函数,而不是折叠数据列表.

我想知道是否有一个标准函数可以捕获这种"折叠绑定"行为.当我试图玩"Name That Combinator"游戏时,Hoogle通常是我的朋友,所以我在Haskell尝试了相同的心理锻炼:

foldl (>>=) (Just stack) operations

这里的类型是:

foldl :: (a -> b -> a) -> a -> [b] -> a
(>>=) :: Monad m => m a -> (a -> m b) -> m b

所以我的神秘foldl (>>=)组合器的类型,在制作类型foldl和(>>=)排队之后,应该是:

mysteryCombinator :: Monad m => …

什么是some和many在Control.Applicative.Alternative好？如果我写的东西some $ Just 42,它似乎导致无限递归,这似乎不是很有用...

我从组合库中编写了一些解析器.我想要一个泛型函数,将任何大小的nest变换成一个列表.这该怎么做 ？

这是我使用的解析器的例子(我的真正的解析器有一个很长的链〜所以我想避免我现在的解决方案,这在下面的评论).

object CombinatorParser extends RegexParsers {

  lazy val a = "a"
  lazy val b = "b"
  lazy val c = "c"
  lazy val content = a ~ b ~ c // ^^ {case a~b => a::b::c::Nil work but I want something more general that work for any ~ length.
}

object CombinatorTesting {

  def main(args:Array[String]) {
    val testChar = "abc"
    val output = CombinatorParser.parseAll(CombinatorParser.content, testChar)
    println(output) // ((a~b)~c) but I want List(a,b,c)
  }
}

在Haskell,我们有Data.Function.on:

on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
(.*.) `on` f = \x y -> f x .*. f y

在Clojure中,我希望能够定义一个例如anagram谓词,如下所示:

(defn anagram? [word other-word]
  (and (not= word other-word)
       ((on = sort) word other-word)))

实施起来很简单:

(defn on [g f] (fn [x y] (g (f x) (f y))))

但是,是否有任何内置函数可以实现相同的目标？我好像找不到一个.

K-combinator可以如下实现,并且实现不应该有任何副作用.

const K = x => y => x;

它有时被称为"const"(如在Haskell中).K函数可以定义为"获取一个值并返回一个始终返回该值的(常量)一元函数."

什么时候有用？请帮我提供实际例子.

假设我在组合器解析器中表达了一种含糊不清的语言.有没有办法让某些表达在当地贪婪？这是我的意思的一个例子.

import scala.util.parsing.combinator._

object Example extends JavaTokenParsers {
  def obj: Parser[Any] = (shortchain | longchain) ~ anyrep

  def longchain: Parser[Any] = zero~zero~one~one
  def shortchain: Parser[Any] = zero~zero

  def anyrep: Parser[Any] = rep(any)
  def any: Parser[Any] = zero | one
  def zero: Parser[Any] = "0"
  def one: Parser[Any] = "1"
  def main(args: Array[String]) {
    println(parseAll(obj, args(0) ))
  }
}

编译后,我可以运行如下:

$ scala Example 001111
[1.7] parsed: ((0~0)~List(1, 1, 1, 1))

我想以某种方式指示第一部分obj是本地贪婪和匹配longchain.如果我改变顺序,它会匹配longchain,但这不是因为贪婪.

def obj: Parser[Any] = …

iterate :: (a -> a) -> a -> [a]

(你可能知道)iterate是一个函数,它接受一个函数和起始值.然后它将函数应用于起始值,然后将相同的函数应用于最后的结果,依此类推.

Prelude> take 5 $ iterate (^2) 2
[2,4,16,256,65536]
Prelude> 

结果是一个无限的列表.(这就是我使用的原因take).我的问题是如何iterate'在Haskell中实现自己的功能,只使用基础知识((:) (++)lambdas,模式mataching,警卫等)？

(Haskell初学者在这里)

注1：这里的CPS代表“持续通过风格”

我对了解如何挂接到C＃异步机制非常感兴趣。基本上，据我了解的C＃异步/等待功能，编译器将执行CPS转换，然后将转换后的代码传递给上下文对象，该对象管理各个线程上的任务调度。

您是否认为可以利用该编译器功能来创建功能强大的组合器，同时又保留默认的线程方面？

一个例子就是可以递归和记忆诸如

async MyTask<BigInteger> Fib(int n)     // hypothetical example
{
    if (n <= 1) return n;
    return await Fib(n-1) + await Fib(n-2);
}

我设法做到这一点：

void Fib(int n, Action<BigInteger> Ret, Action<int, Action<BigInteger>> Rec)
{
    if (n <= 1) Ret(n);
    else Rec(n-1, x => Rec(n-2, y => Ret(x + y)));
}

（不使用异步，非常笨拙...）

或使用monad（While<X> = Either<X, While<X>>）

While<X> Fib(int n) => n <= 1 ?
    While.Return((BigInteger) n) :
    from x in Fib(n-1)
    from y in Fib(n-2) …

我正在完成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 …

这是Scala中Y-combinator的一个实现:

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
     |           f: (Int => Int) =>
     |             n: Int =>
     |               if(n <= 0) 1
     |               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
120

Q1:结果120是如何逐步产生的？因为Y(func)定义为func(Y(func)),Y应该变得越来越多,Y在哪里迷失120了？在形式过程中如何出现？

Q2:有什么区别

def Y[T](func: (T => T) => (T => …