为什么Curry的std lib中的非确定性选择函数没有直接定义，而是使用了辅助函数2参数函数？ [英] Why is the non-deterministic choice function in Curry's std lib not defined straightforwardly but rather with a helper 2-argument function?

问题描述

在咖喱编程语言中选择 / a>，其中规定（选择xs）非确定性地从列表 xs 中选择一个元素。

我会直接通过两个可选的非确定性规则来实现它：

 选择:: [a]  - > a 
选择x：_ = x 
选择_：xs =选择xs 
  

但是在 Muenster Curry Compiler中的/usr/lib/curry-0.9.11/Success.curry ，它是用一个辅助函数定义的：

  choose（x：xs）= choosep x xs 
 where choosep x [] = x 
 choosep x（_：_）= x 
 choosep _（x：xs）= choosep x xs 
  

编译器提供的模块定义的优点（如果有的话）是什么？
这两个定义是完全相等的（即使在一些非确定性和未定义值的棘手情况下）？在某些情况下，它们之一是否更有效率？

< h3> ADDED：进一步考虑

cthom06（谢谢！）已经正确指出我的定义会导致在更多情况下触发未定义的值（因为我们会尝试调用这个函数带有一个空列表参数，每个我们的顶级调用都有一个初始非空列表参数）。 （嗯，我为什么没有立即注意到这个问题？）那效率不高。

但我想知道：有没有语义差异？在一些棘手的情况下，这种差异可能是重要的吗？

我们看到两个定义之间的区别 - 非空列表 - 基本上归结为我的定义就像定义 id $ b as：

  id x = x 
 id _ = undefined 
  

和它们的定义类似于definig id 正常方式：

  id x = x 
  

（所以，这里的直接性被恢复了。）

在哪些上下文中它可能很重要？我相信没有语义上的差异，但是具有帮助函数的函数更有效率，尤其是在常见的情况下（在某些编程风格中）的一个元素的列表。在这种情况下，避免了一个选择点，在您的版本中需要设置为使用[]递归调用，然后将会失败。

更智能的优化器可能会弄清楚这一点本身，但处理各种类似的情况可能是具有挑战性的 - 编译器将需要尝试专门化数据类型中每个可能的构造函数的应用程序，删除那些始终发生故障的应用程序，并删除选择点只有一种可能性。

Consider a function choose in Curry programming language with the specification that "(choose xs) non-deterministically chooses one element from the list xs".

I'd implement it straighforwardly through two alternative non-deterministic rules:

choose :: [a] -> a
choose x:_ = x
choose _:xs = choose xs

But in /usr/lib/curry-0.9.11/Success.curry from Muenster Curry Compiler, it is defined with a helper function:

choose (x:xs) = choosep x xs
  where choosep x [] = x
        choosep x (_:_) = x
        choosep _ (x:xs) = choosep x xs

What could be the advantages (if any) of the definition from the compiler supplied module? Are the 2 definitions completely equivalent (even in some tricky cases with non-determinism and undefined values)?.. Is one of them more efficient in some cases?

ADDED: Deeper consideration

cthom06 (Thanks!) has correctly pointed out that my definition would cause hitting the undefined value in much more cases (because we would try to call this function with an empty-list argument once per each our "top-level" call with an initially non-empty list argument). (Hm, why haven't I noticed this consideration right away?..) That is less efficient.

But I wonder: are there any semantic differences? May the difference be important in some tricky contexts?

We see that the difference between the two definitions--in the case of non-empty lists--basically boils down to the difference between two potential definitions for id:

my definition is like defining id as:

id x = x
id _ = undefined

and their definition is like definig id the normal way:

id x = x

(So, here the straightforwardness is reverted.)

In which contexts can it be important?

解决方案

I believe there are no semantic differences, but the one with the helper function is more efficient, particularly in the common case (in certain styles of programming) of a list with one element. In this case a choice point is avoided which with your version would need to be set up to call recursively with [] which is then bound to fail.

A smarter optimizer might figure this out for itself, but handling all kinds of similar situations is likely to be challenging - the compiler would need to try to specialize applications for each of the possible constructors in a datatype, remove those where failure always occurs, and remove choice points when only one possibility remains.

这篇关于为什么Curry的std lib中的非确定性选择函数没有直接定义，而是使用了辅助函数2参数函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！