为什么Curry标准库中的非确定性选择函数不是直接定义，而是使用一个帮助器二元函数来定义？

Question

考虑在柯里编程语言中实现一个名为choose的函数，其规范是"(choose xs)从列表xs中非确定性地选择一个元素"。

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

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

但在来自明斯特Curry编译器的/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

如果编译器提供的模块定义有什么优势（如果有的话），是不是这两个定义在所有情况下都完全等效（即使涉及到非确定性和未定义值的一些棘手情况）？那么其中一个在某些情况下是否更有效？

新增：更深入的考虑

cthom06（谢谢！）正确指出了我的定义会导致在更多情况下遇到未定义的值（因为我们会尝试每次使用空列表参数来调用此函数，并且每次“顶层”调用时使用最初的非空列表参数）。 这样做的效率较低。

但我想知道：这两种定义是否存在任何语义上的区别？ 在某些棘手的上下文中差异是否重要？

我们看到，这两个定义之间的差异 - 在非空列表的情况下 - 基本上归结为两个id的潜在定义之间的差异：

我的定义类似于将id定义为：

id x = x
id _ = undefined

它们的定义就像正常定义id一样：

id x = x

（因此，这里的直接性被逆转。）

在哪些情境下它可能很重要？

- imz -- Ivan Zakharyaschev

---

我可能理解有误，但在你的实现中看起来会出现从一个非空列表开始执行时却被卡在尝试选择一个空列表值的情况。 - cthom06

@cthom06：以这种方式“卡住”不会改变语义，据我所知：计算的那个变体只是被丢弃了。但也许它会稍微影响效率。因此，问题归结为：使用一个规则id x = x或使用额外的虚假规则id x = x和id _ = undefined来定义id有哪些重大差异（关于语义方面-任何棘手的情况，或关于效率方面）？我想知道：是否存在语义可能发生变化的棘手情况？ - imz -- Ivan Zakharyaschev

@cthom06，为什么不把那个作为答案呢？ - Ben

@Ben，我只是根据我看到的猜测，实际上并没有使用过Curry，只是稍微接触过Haskell。 - cthom06

在这里，它指出底部表示失败：kics2_paper。因此，head(a:xs)=a的行为类似于head(x:xs)=x，而head[] = failed。但是我们应该如何解释“error”？ - Edgar Klerks

Answer 1

我认为两种写法没有语义上的区别，但是带有helper function的写法更加高效，特别是在某些编程风格下常见的只有一个元素的列表情况中。在这种情况下，使用你的版本需要设置一个选择点来递归调用[]，但是这个选择点注定会失败。

更聪明的优化器可能会自己找出这一点，但是处理所有类似情况可能会很具挑战性——编译器需要尝试为数据类型中的每个可能的构造器专门应用，删除总是失败的那些并在只剩下一个可能性时删除选择点。

- RD1

---

我的另一个评论也适用于这里：区别在于中间解决方案的数量，解释器的工作方式，可能是副作用（将“错误”视为副作用），但除非有一些封装的搜索，否则可能不会完全计算结果。此外，惰性起到了作用，如果我们仅获取表达式的“头”而没有触发“未定义”/错误，则可能存在（输出解决方案的数量）差异。 - imz -- Ivan Zakharyaschev