15

「リストから1つの要素を非決定論的に選択する」という仕様のchooseCurryプログラミング言語の関数について考えてみます。(choose xs)xs

私はそれを2つの代替の非決定論的ルールを通して簡単に実装します： 

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

しかし、Muenster CurryCompilerの/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

コンパイラが提供するモジュールからの定義の利点（もしあれば）は何でしょうか？2つの定義は完全に同等ですか（非決定論と未定義の値を持ついくつかのトリッキーな場合でも）？..場合によっては、そのうちの1つがより効率的ですか？

追加：より深い考察

cthom06（Thanks！）は、私の定義がはるかに多くの場合に未定義の値にヒットすることを正しく指摘しています（最初に「トップレベル」の呼び出しごとに1回、空のリスト引数を使用してこの関数を呼び出そうとするためです空でないリスト引数）。（うーん、なぜ私はこの考慮事項にすぐに気づかなかったのですか？..）それは効率が悪いです。

しかし、私は疑問に思います：意味上の違いはありますか？いくつかのトリッキーなコンテキストで違いが重要になる可能性がありますか？

2つの定義の違い（空でないリストの場合）は、基本的に、次の2つの潜在的な定義の違いに要約されますid。

私の定義は次のように定義するようなidものです。 

id x = x
id _ = undefined

そしてそれらの定義はid通常の方法で定義するようなものです： 

id x = x

（したがって、ここでは単純さが元に戻されます。）

どのような状況でそれが重要になる可能性がありますか？

4

1 に答える 1

2

意味上の違いはないと思いますが、特に 1 つの要素を持つリストの一般的なケース (特定のプログラミング スタイル) では、ヘルパー関数を使用した方が効率的です。この場合、[] を使用して再帰的に呼び出すようにバージョンを設定する必要がある選択ポイントが回避され、失敗することになります。

よりスマートなオプティマイザーはこれを自分で解決するかもしれませんが、あらゆる種類の同様の状況を処理するのは難しいでしょう。コンパイラーは、データ型で可能なコンストラクターごとにアプリケーションを特殊化し、失敗が常に発生するコンストラクターを削除し、可能性が1つしか残っていない場合は、選択ポイントを削除します。

于 2011-04-06T10:31:43.303 に答える