我正试图在大图上实施Kosaraju的算法作为任务的一部分[MOOC Algo I Stanford on Coursera]
https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
当前代码适用于小图,但我在运行时执行期间遇到了Stack Overflow.
尽管已经阅读了F#中的Expert相关章节,或者网站上的其他可用示例和SO,我仍然没有得到如何使用continuation来解决这个问题
下面是通用的完整代码,但在执行DFSLoop1和递归函数DFSsub时它已经失败了.我认为我没有使函数tail递归[因为指令
t<-t+1
G.[n].finishingtime <- t
？]
但我不明白我如何正确实施延续.
当仅考虑失败的部分时,DFSLoop1将我们将应用深度优先搜索的图形作为参数.我们需要记录完成时间作为算法的一部分,以便在第二个DFS循环(DFSLoop2)中进入算法的第二部分[当然我们在此之前就失败了].
open System
open System.Collections.Generic
open System.IO
let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford I\PA 4 - SCC.txt";;
// let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford I\PA 4 - test1.txt";;
// val x : string [] =
let splitAtTab (text:string)=
text.Split [|'\t';' '|]
let splitIntoKeyValue (A: int[]) =
(A.[0], A.[1])
let parseLine (line:string)=
line
|> splitAtTab
|> Array.filter (fun s -> not(s=""))
|> …stack-overflow f# tail-recursion continuation-passing kosaraju-algorithm
我正在阅读24 天 GHC 扩展的 Rank-N-Types 部分并遇到以下 GADT：
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
import Data.Char
data Some :: * -> * where
SomeInt :: Int -> Some Int
SomeChar :: Char -> Some Char
Anything :: a -> Some a
unSome :: Some a -> a
unSome (SomeInt x) = x + 3
unSome (SomeChar c) = toLower c
unSome (Anything x) = x
unSome (someInt 2) -- 5
尽管unSome它的类型变量是多态的，但可以向编译器证明在这种SomeInt情况下，将三个添加到给定值是安全的。作者将这种类型称为细化。
现在我很好奇我是否可以用 Scrott …
haskell continuation-passing gadt refinements refinement-type
我对这个概念有点困惑.所以我有以下功能
let rec sumlist lst =
match lst with
| [] -> 0
| (h::t) -> h + (sumlist t)
继续,它可以写成
let rec cont_sumlist lst c =
match lst with
| [] -> (c 0)
| (h::t) -> cont_sumlist t (fun x -> c (h + x))
我仍然对c手段及其作用感到困惑
在实现 的 Applicative 实例时出现以下错误Cont。
\n\n\n无法将预期类型 \xe2\x80\x98r\xe2\x80\x99 与实际类型 \xe2\x80\x98Cont rb\xe2\x80\x99 \xe2\x80\x98r\xe2\x80\x99 严格匹配类型变量受...约束
\n
newtype Cont r a = Cont {(>>-) :: (a -> r) -> r}\n\ninstance Functor (Cont r) where\n -- fmap :: (a -> b) -> (Cont r) a -> (Cont r) b\n fmap f (Cont cps_a) = Cont $ \\cps -> cps_a (cps . f)\n\ninstance Applicative (Cont r) where\n -- pure :: a -> Cont r a\n pure x = Cont ($ x)\n -- …的参数call/cc是一个过程，其参数是一个延续。程序是用CPS 写的吗？
《Lisp in Small Pieces》一书展示了从Scheme到延续通过风格的转变（第5.9.1章，适用于有此书的读者）。转换代表lambda形式的延续，并且call/cc应该等同于简单形式(lambda (k f) (f k k))。
我不明白这是怎么工作的，因为在函数的应用和延续之间没有区别。
这是从应用程序以外的所有内容中剥离出来的转换版本（完整版本可以在gist中找到）：
(define (cps e)
(if (pair? e)
(case (car e)
; ...
(else (cps-application e)))
(lambda (k) (k `,e))))
(define (cps-application e)
(lambda (k)
((cps-terms e)
(lambda (t*)
(let ((d (gensym)))
`(,(car t*) (lambda (,d) ,(k d))
. ,(cdr t*)))))))
(define (cps-terms e*)
(if (pair? e*)
(lambda (k)
((cps (car e*))
(lambda (a)
((cps-terms (cdr e*))
(lambda (a*)
(k (cons a a*))))))) …我一直在努力学习CPS,似乎我并没有真正理解它,你能用Cont monad实现基本的过滤器和地图吗？
我一直在尝试继续传递样式,因为我可能需要尽快处理一些非尾递归函数.无论如何,要知道好的技术!我在Lua和Clojure中编写了一个测试函数; 在我的小型Android掌上电脑上运行Lua.
Lua版本似乎运行良好,Lua的堆栈已经有大约300000的深度,但是使用CPS,我很容易在系统爆炸之前完成超过7000000次迭代,可能是因为缺乏内存,而不是任何限制CPS/Lua组合.
Clojure的尝试表现不太好.只有1000多次迭代,它就是抱怨堆栈爆炸,只需使用普通迭代就可以做得更好,它的堆栈大约为1600,iirc.
任何想法可能是什么问题？JVM固有的东西,或者只是一些愚蠢的noob错误？(哦,BTW,测试功能,sigma(日志)被选中,因为它增长缓慢,Lua不支持Android上的bignums)
所有的想法,提示,建议都非常受欢迎.
Clojure代码:
user=> (defn cps2 [op]
#_=> (fn [a b k] (k (op a b))))
#'user/cps2
user=> (defn cps-sigma [n k]
#_=> ((cps2 =) n 1 (fn [b]
#_=> (if b ; growing continuation
#_=> (k 0) ; in the recursive call
#_=> ((cps2 -) n 1 (fn [nm1]
#_=> (cps-sigma nm1 (fn [f]
#_=> ((cps2 +) (Math/log n) f k)))))))))
#'user/cps-sigma
user=> (cps-sigma 1000 identity)
5912.128178488171
user=> (cps-sigma 1500 identity)
StackOverflowError clojure.lang.Numbers.equal (Numbers.java:216)
user=> …例如,我有两个异步方法
(get-a 10 (lambda (a) (get-b a (lambda (b) (display b)))
但我想写一些类似的东西
(define (a (get-a 10)))
(define (b (get-b a)))
(display b)
scheme continuations functional-programming callcc continuation-passing