名单懒惰评估在Haskell

我做了以下简单的假设，以了解在Haskell名单懒惰的评价，名单懒惰评估在Haskell

head [1, 2]    -- expr1 
head [1 .. 2]    -- expr2 
head [1 ..]    -- expr3 

head . (1 :) $ []   -- eval1 
head . (1 :) . (2 :) $ [] -- eval2

我想这expr3想eval1懒洋洋地评估，如何expr1和expr2？

一般来说，

是懒惰的评价在Haskell在编译和运行时间的技术？
它在哪里说效率好，但很难推理，按时，空间复杂性或程序逻辑？

来源

2015-04-02 sof

我不明白你的要求。看起来你试图推理表达式的评估，但我不知道你在说什么。在Google上学习更多的关键字是“WHNF”。 – kirelagin 2015-04-02 22:36:23

如果有人试图直接回答你的问题，那么答案就是：“你的例子中没有写出任何表达式。 – kirelagin 2015-04-02 22:38:50

你的意思是'head [1,2]'直接编译为'1'吗？ – sof 2015-04-02 22:47:33

列表没有什么特别之处。它们仅仅是递归的数据类型：

data [a] = a : [a] | []

现在，当您使用[1 .. 2]，就是不变成了一个列表(1:(2:[]))直接!,它被存储为表达[1 .. 2]。

现在head被定义为：

head :: [a] -> a 
head (x:_) = x

如果你打电话head [1 .. 2]，为main（因此Haskell是莫名其妙地被迫对其进行评估），它会看到[1 .. 2]不是一个数据结构，而是一个悬而未决的表达，这将解决表达了一下：

[1 .. 2] to (1:[(succ 1) .. 2])

就这样，现在一曰：

head (1:[(succ 1) .. 2])

（注意，尾巴仍然是一个表情），但由于head只对感兴趣，所以 - “头”它将返回1。请注意，如果head是例如1+2，则它不会立即评估为3。

此外，如果你简单地调用head [1 .. 2]表达将不会自动评估，如果你想为实例，以显示结果，哈斯克尔将尽努力来计算它，它仅仅是。

根据编译器的实现情况，编译器可以在编译时尽力传播常量（文字）并对它们执行操作，但由于编译器应始终遵循执行标准，因此语义保持不变。

来源

2015-04-02 23:23:53

我应该更好地陈述一些我在'GHCi'中键入'head ..'表达式或者从'main = do print $ head ...'抽象它们以避免混淆。 – sof 2015-04-02 23:46:40

在ghci中，它会 - 或多或少 - 在前面放置一个隐式'print $'，从而评估它，直到它可以打印结果。 – 2015-04-02 23:52:11

术语“懒惰评估”以多种方式使用。

懒惰评价是一种语义;它说什么表达式评估哪些值。（我承认虽然有一些细节从语义中遗漏了！）
懒惰评估是一种实施策略;它提供了一种“运行”符合上述语义的lambda演算术语的方法，并使用共享来改进更明显的“按名称”实现策略的时间和内存使用情况。
我想，你还以第三种方式使用它。

在余下的部分中，我将对实现策略使用“懒惰评估”，对于语义使用“非严格语义”。

我想这expr3想eval1懒洋洋地评估，如何expr1和expr2？

一个非严格的语义规定所有五个术语的评估应该终止并产生值1，因此任何符合实现将以这种方式表现。懒惰评估将在每个表达式的大约相同的空间和时间内完成。我希望如果你强迫这五个术语中的任何一个，GHC会选择懒惰评估，尽管优化它可能会在编译时进行评估。如果您非常感兴趣，您可以通过传递-ddump-simpl标志来自己检查。

Haskell中的懒惰评估技术在编译和运行时间？

希望上面的讨论已经澄清了这个问题。非严格语义描述了编译时和运行时之间的特定连接（即，编译器必须生成一个程序，其运行时行为会产生语义指定的值）。懒惰评估是生成符合语义的程序的特定实现策略。 GHC有时在其计划中使用懒惰评估，但有时使用其他实施策略;但是，它符合非严格的语义。（如果你找到一个不存在的地方，这是一个错误！）

它说什么对效率有好处，但很难推论，按时，空间复杂性或程序逻辑？

非严格的语义通常不会说在计算过程中使用了多少时间或空间，所以如果您想对此进行推理，则需要完全不同的技术。即使你决定将你的推理限制在用懒惰评估实现的程序中，事情也很难。考虑像[1..]这样的表达：它使用多少空间？这个问题不能在真空中回答;懒惰评估的基本思想是让消费者对价值构建的价值进行控制。因此，没有看到的做与表达[1..]程序，我们无法知道了。它可能会将价值抛开，在这种情况下几乎不会使用空间;或者它可能沿着列表走下去，在这种情况下使用恒定的空间量;或者它可能在不同的时间遍历列表两次，在这种情况下使用无限空间;或者可能会用其他空间要求来做其他事情。

来源

2015-04-02 23:42:13

感谢您的详细解答。我想知道是否可以找到Haskell的词汇，包括学术术语和相关的行业术语。 – sof 2015-04-03 00:22:37

@sof根据您的兴趣，您可能会喜欢“功能语言的实现”，“Spineless Tagless G-Machine”或“类型和编程语言”。当然，也有Haskell wiki，它具有较低的深度，严格性和方向性，但也立即可用且相当平易近人。 – 2015-04-03 03:00:03

要完成其他的答案，你可以在ghci中与:sprint命令检查有懒评价工作：

Prelude> let xs = [1..10] :: [Int] 
Prelude> :sprint xs 
xs = _ 
Prelude> head xs 
1 
Prelude> :sprint xs 
xs = 1 : _ 
Prelude> take 3 xs 
[1,2,3] 
Prelude> :sprint xs 
xs = 1 : 2 : 3 : _ 
Prelude> length xs 
10 
Prelude> :sprint xs 
xs = [1,2,3,4,5,6,7,8,9,10]

来源

2015-04-03 12:14:59 Eric

名单懒惰评估在Haskell

回答

相关问题