标签: continuation-passing

Here is a naive implementation of a right fold:

const foldr = f => acc => ([x, ...xs]) =>
  x === undefined
    ? acc 
    : f(x) (foldkr(f) (acc) (xs));

This is non-tail recursion and hence we cannot apply a trampoline. One approach would be to make the algorithm iterative and use a stack to mimick the function call stack.

Another approch would be to transform the recursion into CPS:

const Cont = k => ({runCont: k});

const foldkr = f …

我正在学习使用Racket的CPS,我已经设法编写了这些函数:

;lift a regular single-arg function into CPS
(define (lift/k f)
  (lambda (x k)
    (k (f x))))

;compose two CPS functions
(define (compose/k f g)
  (lambda (x k)
    (g x (lambda (y)
           (f y k)))))

他们似乎工作正常

(define (is-two/k x k)
  (k (= x 2)))
(define is-not-two/k (compose/k (lift/k not) is-two/k))
(is-not-two/k 3 display)
(is-not-two/k 2 display)

#t#f

我想知道这些功能是否仍然是"真正的CPS".我是否搞砸了"真正的"继续传递这些功能？在CPS中使用函数组合技术是犹太的吗？是鼓励吗？或者它会被视为"妥协"吗？是否有更多的CPS-y方式来做到这一点？

是的我知道我刚问了5个问题,但是他们背后的基本思想(我不确定我是否正确理解)是一样的.其他Lisps,Haskell,Erlang或其他函数式语言的解释都很好.

在On Lisp,p.267,Paul Graham提供了一个继续传递宏的实现:

(setq *cont* #'identity)

(defmacro =lambda (parms &body body)
  `#'(lambda (*cont* ,@parms) ,@body))

(defmacro =defun (name parms &body body)
  (let ((f (intern (concatenate 'string
                "=" (symbol-name name)))))
    `(progn
       (defmacro ,name ,parms
     `(,',f *cont* ,,@parms))
       (defun ,f (*cont* ,@parms) ,@body))))

(defmacro =bind (parms expr &body body)
  `(let ((*cont* #'(lambda ,parms ,@body))) ,expr))

(defmacro =values (&rest retvals)
  `(funcall *cont* ,@retvals))

以下代码遍历树t2的每个叶子的树t1,使用此实现,我想知道restart调用时会发生什么,特别是在t1从A(第一个元素)更改为B(第二个元素)的叶子之后.当restart被调用时,它只是从弹出lambda函数*saved*,而lambda函数调用dft-node …

我的目标摘要:弄清楚如何使用延续传递样式来避免在使用算法时堆栈溢出我认为不能使尾递归.或者,找到一种使函数尾递归的方法.

细节: 我是F#的新手(以及一般的函数式编程),我试图用alpha-beta修剪实现minimax算法.这是一种用于确定双人游戏的最佳移动的算法.算法的伪代码可以在这里找到:https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

这是我发现有助于理解算法流程的资源:http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/

我的实现的一个不同之处在于我正在进行的游戏的玩家并不总是交替.出于这个原因,我从函数中删除了一个参数.我的实现如下:

let rec minimax node depth alpha beta =
    if depth = 0 || nodeIsTerminal node then
        heuristicValue node
    else
        match node.PlayerToMakeNextChoice with
        | PlayerOneMakesNextChoice ->
            takeMax (getChildren node) depth alpha beta    
        | PlayerTwoMakesNextChoice ->
            takeMin (getChildren node) depth alpha beta
and takeMax children depth alpha beta =      
    match children with
    | [] -> alpha
    | firstChild :: remainingChildren ->
        let newAlpha = [alpha; minimax firstChild (depth - 1) alpha …

可以使用F＃中的计算表达式实现CPS吗？

Brian McNamara的博客提供了以下解决方案：

type ContinuationBuilder() = 
  member this.Return(x) = (fun k -> k x) 
  member this.ReturnFrom(x) = x 
  member this.Bind(m,f) = (fun k -> m (fun a -> f a k)) 
  member this.Delay(f) = f() 

let cps = ContinuationBuilder()

看起来不错。我可以用List.mapCPS 编写：

let rec mapk f xs = cps {
  match xs with
  | [] -> return []
  | x::xs ->
      let! xs = mapk f xs
      return f x::xs
}

但是它会溢出：

mapk ((+) 1) [1..1000000] id

我究竟做错了什么？

newtype Cont k a = Cont { runCont :: (a -> k) -> k }

instance Functor (Cont k) where
  -- fmap :: (a -> b) -> (Cont k a) -> (Cont k b)
  fmap f (Cont akTok) = Cont $ ???

我的疑惑：

1. 我们只能将 Functor 实例写入任何可以产生类型输出的数据类型（例如：[a], Maybe a, (y -> a)），但不能用于消耗类型的数据类型。现在，在上述数据键入它消耗了功能消耗一个那么这如何间接消耗的可视为生产型一个。这意味着我们不能为(k -> a) -> k编写 Functor 实例？

2. 如何读取Cont数据类型。续产生ķ时，它有一个？（就像 Javascript XHR 回调在从服务器获取数据时生成 JSON 一样？）

3. 如何为Cont数据类型编写 …

可能重复:
对Node.js的Haskell响应是什么？
如何在Haskell中观察多个文件/套接字变为可读/可写？

是否有可能编写一个Haskell程序,以非阻塞方式执行IO,如nodejs？

例如,我想从远处的数据库中获取10条记录,因此我想同时发出10个请求,当结果可用时,则返回此集合.IO monad不会提供帮助,因为monad使用bind显式序列化计算.我认为继续传递样式,你传递下一个你想要的计算具有相同的问题,再次它序列化计算.我不想使用线程,我正在寻找另一种解决方案.这可能吗？

我有这种格式的计算:s -> a -> s,s某种状态的类型在哪里.这种功能的结果也是下一次评估的状态.例如,

appendInt :: String -> Int -> String
appendInt s i = s ++ (show i)

然后,appendInt "Int: " 1将给予"Int: 1",同时(appendInt $ appendInt "Int: 1") 2将给予"Int: 12".但是,我找不到将这种计算放在StateMonad中的方法.

第一个猜测是s -> (s,s),但后来a不能传入.然后,我尝试了(a -> s) -> (s, a -> s),但是再次不可能s没有a.s -> (a,s)将无法工作,因为a输入而不是输出.

那我该如何包装这个计算呢？是State单子适合这个？

我有一棵树,结构如下:

type 'a Tree =| Leaf of 'a| Branch of 'a Tree * 'a Tree

我在树上使用延续传递样式的尾递归并尝试将其展平.

let rec loop tree k acc = 
  match tree with
  | Leaf v -> v :: acc
  | Branch (tl,tr) -> loop tl (loop tr k) acc
loop xs id []


(Branch (Branch (Leaf 1.0,Leaf 2.0),Branch (Leaf 3.0,Leaf 4.0)))

这只返回[1.0]

但是我只获得树中的第一片叶子,我的功能不适用于整棵树.我怎样才能做到这一点？

众所周知，如何ContT基于 Koen Claessen 的功能性明珠基于 制作纯并发 monad ：

data Action m where
  Atom :: m (Action m) -> Action m
  Fork :: [Action m] -> Action m
  Stop :: Action m

fork :: Applicative m => [ContT (Action m) m a] -> ContT (Action m) m ()
fork processes = ContT $ \next -> Fork <$> sequenceA (next () : [ process $ const $ pure $ Const | ContT process <- processes ])

我将如何实现像IORefs 或MVar …