以下两个用于计算Fibonacci序列第n项的Haskell程序具有非常不同的性能特征:
fib1 n =
case n of
0 -> 1
1 -> 1
x -> (fib1 (x-1)) + (fib1 (x-2))
fib2 n = fibArr !! n where
fibArr = 1:1:[a + b | (a, b) <- zip fibArr (tail fibArr)]
它们在数学上非常接近,但fib2使用列表表示法来记忆其中间结果,同时fib1具有显式递归.尽管中间结果可能被缓存fib1,但执行时间甚至成为问题fib1 25,这表明总是会评估递归步骤.参考透明度是否对Haskell的性能有贡献？我怎么能提前知道它是否会？
这只是我担心的一个例子.我想听听有关克服关于延迟执行的函数式编程语言的性能推理所固有的困难的任何想法.
简介: 我接受3lectrologos的答案,因为关于语言的性能,关于编译器的优化,你没有那么多理由这一点似乎在Haskell中非常重要 - 比我熟悉的任何其他语言更重要用.我倾向于说编译器的重要性是区分懒惰,功能语言中的性能推理的因素,而不是任何其他类型的性能推理.
所以我遇到了这个代码片段,展示了如何在Rust中创建"不可移动"类型 - 因为编译器将对象视为在其整个生命周期中借用的对象,所以阻止了移动.
use std::cell::Cell;
use std::marker;
struct Unmovable<'a> {
lock: Cell<marker::ContravariantLifetime<'a>>,
marker: marker::NoCopy
}
impl<'a> Unmovable<'a> {
fn new() -> Unmovable<'a> {
Unmovable {
lock: Cell::new(marker::ContravariantLifetime),
marker: marker::NoCopy
}
}
fn lock(&'a self) {
self.lock.set(marker::ContravariantLifetime);
}
fn new_in(self_: &'a mut Option<Unmovable<'a>>) {
*self_ = Some(Unmovable::new());
self_.as_ref().unwrap().lock();
}
}
fn main(){
let x = Unmovable::new();
x.lock();
// error: cannot move out of `x` because it is borrowed
// let z = x;
let mut y = None;
Unmovable::new_in(&mut …当前版本的The Rustonomicon有这个示例代码：
use std::mem;
pub struct IterMut<'a, T: 'a>(&'a mut [T]);
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
let slice = mem::replace(&mut self.0, &mut []);
if slice.is_empty() {
return None;
}
let (l, r) = slice.split_at_mut(1);
self.0 = r;
l.get_mut(0)
}
}
我特别对这条线感到困惑：
let slice = mem::replace(&mut self.0, &mut []);
// ^^^^^^^
这个借书怎么查？如果这是一个不可变的借用，RFC 1414指出[]右值应该有'static生命周期，这样一个不可变的借用会借用检查，但这个例子显示了一个可变的借用！似乎必须发生两件事之一：
[]是临时的（以便它可以可变地使用），在这种情况下它没有'static生命周期，并且不应该借用检查；我正在研究is_classBoost中模板的实现,并遇到了一些我无法轻易解读的语法.
template <class U> static ::boost::type_traits::yes_type is_class_tester(void(U::*)(void));
template <class U> static ::boost::type_traits::no_type is_class_tester(...);
我如何解释void(U::*)(void)上述？我熟悉C,所以看起来有些类似void(*)(void),但我不明白如何U::修改指针.有人可以帮忙吗？
谢谢
所以,我在这里看问题,为问题构建了一个相当丑陋的解决方案.在尝试清理时,我开始调查列表推导和列表monad.我决定要做的是使用list monad实现一个每位数的计数器.给定一个输入的数字序列[1, 2],我想生成一个类似于下面的输出序列:
[ [ 0, 0],
[ 0, 1 ],
[ 0, 2 ],
[ 1, 0 ],
[ 1, 1 ],
[ 1, 2 ] ]
也就是说,我将遍历该范围内列表中所有元素的所有可能值.
haskell.org 列表monad文档说:
绑定函数应用于输入列表中的所有可能值,并将结果列表连接起来以生成所有可能结果的列表.
大!看起来很完美......这是我为编写解决方案而编写的代码:
count :: [Integer] -> [[Integer]]
count [] = []
count (x:xs) =
-- get all possible sequences for the remaining digits
let
remDigits :: [[Integer]]
remDigits = count xs
in
-- pull out a possible sequence for the remaining digits
do nextDigits …