为什么下面的Haskell代码是非确定性的？ [英] Why is the following Haskell code non-deterministic?

问题描述

我从学习你一个哈斯克尔和：
$ b

执行（ +）< $> [1,2] *< [4,5,6] 导致非确定性
计算 x + y 其中 x 取自 [1,2] 和 y 中的每个值都取
每一个值从 [4,5,6] 。

我想我明白什么是非确定性的。是否只是结果的顺序或计算顺序不能保证每次都是一样的？ 本书使用的是与你不同的非确定性计算意义。

你在考虑非确定性计算，就像完全确定其产出。这种非确定性在使用多个并行执行线程时很常见;有很多可能的输出，你得到的是由运行时发生事件的确切顺序任意确定的。

你从LYAH引用的段落正在说话关于查看列表作为非确定性计算的模型，从逻辑编程范例的意义上来说（如果您曾使用Prolog语言编写过大量程序，您可能会熟悉这一点）。非确定性程序在这个意义上具有多个（或零！）输出，因为它们被专门编程为，而不是因为它们没有完全指定它们的输出应该是什么。

如果非确定性代码只是具有零个或多个t型输出的代码，这听起来很像返回t列表的函数。 Applicative（和Functor和Monad）实例列表只是说明如何将这些非确定性值相互结合以及与纯函数结合起来的明显方式。例如，Functor实例表示，如果您可以将函数应用于A以获取B，那么您还可以将该函数映射为在非确定性A上工作以获得非确定性B（由将未映射函数应用于非确定性A的每个可能值）。 [1,2] *< [4,5,6] 这种方式是非确定性加法的一个例子。你可以添加一个数字，可能是1或2，可能是4,5或6的另一个数字;结果可能是5,6,7,6,7或8（有些可能性会重复，因为有多种方法可以生成它们）。

I've been learning Haskell from Learn You A Haskell and just came across the following statement:

Doing (+) <$> [1,2] <*> [4,5,6] results in a non-deterministic computation x + y where x takes on every value from [1,2] and y takes on every value from [4,5,6].

I don't think I understand what is non-deterministic about this. Is it just that the order of the results or the order of computation is not guaranteed to be the same every time?

解决方案

The book is using a different sense of "non-deterministic computation" than you are.

You're thinking "non-deterministic computation" as in "a program which doesn't fully determine its output". This kind of non-determinism is common when using multiple parallel threads of execution; there are many possible outputs, and which one you get is arbitrarily determined by the precise order in which things happen at runtime.

The paragraph you're quoting from LYAH is talking about viewing lists as a model of "non-deterministic computation", in a sense that is meant by the logic programming paradigm (if you've ever done much programming using the Prolog language, you'd probably be familiar with this). Non-deterministic programs in this sense have multiple (or zero!) outputs because they are specifically programmed to do so, rather than because they do not fully specify what their output should be.

If "non-determinsitic code" is just code that has "zero or more outputs of type t", this sounds a lot like a function returning a list of t. The list Applicative (and Functor and Monad) instances are just the obvious way of saying how to combine such "non-determinstic values" with each other, and with pure functions. For example, the Functor instance says that if you can apply a function to an A to get a B, then you can also map that function to work on a "non-deterministic A" to get a "non-determinstic B" (by applying the unmapped function to every possible value of the "non-deterministic A").

(+) <$> [1,2] <*> [4,5,6] seen this way is an example of "non-deterministic addition". You add a number that could be 1 or 2, to another number that could be 4, 5, or 6; the result could be 5, 6, 7, 6, 7, or 8 (some possibilities are repeated because there's more than one way to generate them).

这篇关于为什么下面的Haskell代码是非确定性的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！