我正试图找到一种正式的方式来考虑haskell中的空间复杂性.我发现这篇关于图形缩减(GR)技术的文章在我看来是一种方法.但是我在某些情况下应用它时遇到了问题.请考虑以下示例:
假设我们有一个二叉树:
data Tree = Node [Tree] | Leaf [Int]
makeTree :: Int -> Tree
makeTree 0 = Leaf [0..99]
makeTree n = Node [ makeTree (n - 1)
, makeTree (n - 1) ]
和两个遍历树的函数,一个(count1)流畅地流动,另一个(count2)一次在内存中创建整个树; 根据剖析器.
count1 :: Tree -> Int
count1 (Node xs) = 1 + sum (map count1 xs)
count1 (Leaf xs) = length xs
-- The r parameter should point to the …Haskell (as commonly implemented) does not have a call stack;
evaluation is based on graph reduction.
真？这很有意思,因为虽然我自己从未体验过它,但我已经读过,如果你不使用折叠函数的严格版本然后强制评估无限折叠,你会得到堆栈溢出.当然,这表明存在堆栈.任何人都可以澄清吗？
我正在分析其依赖项的一些代码.假设存在一些交织的依赖关系,如下所示:
F
A /|
| / |
| / |
V < V
B<--->C--->E
\ / |
> < |
D<------+
B取决于A和C C取决于B,F E取决于C,F D取决于B和C和E.
我们有B和C的问题,他们互相依赖.它们应该组合成一个超级节点.我们有C和E和F的问题,它们有一个循环.它们应该组合成一个超级节点.
你最终会得到
A
|
V
super
node
|
|
D
是否有一个很好的库或算法源(Java首选,但对建议开放)允许这样的减少？
循环中的任何节点都组合成一个节点.指向新节点中任何节点的任何节点都应指向新节点.新节点中任何节点指向的任何节点都应该使新节点指向该节点.
谢谢!
我在Haskell中阅读半显式并行性,并得到一些混淆.
par :: a -> b -> b
人们说这种方法允许我们通过并行评估Haskell程序的每个子表达式来自动进行并行化.但这种方法有以下缺点:
1)它创造了太多的小项目,无法有效安排.据我所知,如果你对Haskell程序的每一行使用par函数,它将创建太多线程,并且它根本不实用.是对的吗？
2)使用这种方法,并行性受到源程序中数据依赖性的限制.如果我理解正确,这意味着每个子表达式必须是独立的.就像在par函数中一样,a和b必须是独立的.
3)Haskell运行时系统不一定创建一个线程来计算表达式a的值.相反,它会创建一个spark,它有可能在与父线程不同的线程上执行.
所以,我的问题是:最后运行时系统会创建一个线程来计算或不计算？或者,如果需要表达式a来计算表达式b,系统将创建一个新线程来计算？否则,它不会.这是真的？
我是Haskell的新手,所以也许我的问题对你们所有人来说都是基本的.感谢您的回答.