1

以下は、カレーでの私の最初のプログラムです。目的のソリューションに到達するために必要な一連の手順を出力します (閉じたドアを通り抜けます)。

Evaluating expression: main
Done
(Just [Open,Walk,Close])

探しているときに終了させるにはどうすればよいImpossibleですか? Kics2 0.3.1 を使用しています。

import List
import AllSolutions
import IO
import ReadShowTerm
import Constraint

data State = Opened | Closed | Outside | Done | Impossible
data Action = Open | Walk | Close

e Open Closed = Opened
e Walk Opened = Outside
e Close Outside = Done

solution target | foldl (flip e) Closed actions =:= target & length actions <: 4  = actions
   where actions free

main = do
  target <- getContents
  getOneValue (solution $ readTerm target) >>= print
4

1 に答える 1

0

の場合、Doneを使用して検索スペースを削除しますgetOneValue。つまり、最初の結果が見つかったとき、関数は自由変数 の可能性をそれ以上生成しませんactions。ただし、 の場合のように解がない場合、 をImpossible使用するとgetOneValue、最初の解を探し続けるため、検索空間を切り詰めることができません。実際、最初のソリューションだけでなく、すべてのソリューションを検索すると、他の呼び出しでさえ、ソリューションを見つけた後に終了しません。

終了バージョンを取得するには、次の の定義を試すことができますsolution。

solution target | foldl (flip e) Closed (take 4 actions) =:= target = actions
   where actions free

takeはリストの最初の 4 つのコンス コンストラクターのみを評価するため、このように検索スペースは実際に刈り込まれます。対照的にlength、リストのすべてのコンストラクターの評価で長さを計算します。リスト全体を評価するため、自由変数actionsの非決定論的可能性の生成は自由変数の評価によって駆動されるため、自由変数はますます多くのリストを生成します。

Curry プログラムの検索スペースを制限することは、評価について推論する必要があるため、非常に難しい場合があります。たとえば、プリミティブ整数の代わりにペアノ数を使用すると、終了プログラムも取得されます。Peanoより正確には、数値を使用して次の関数を定義できます。

data Peano = Zero | Succ Peano

fourP :: Peano
fourP = Succ (Succ (Succ (Succ Zero)))

lengthP :: [a] -> Peano
lengthP [] = Zero
lengthP (_:xs) = Succ (lengthP xs)

lessP :: Peano -> Peano -> Success
lessP Zero     (Succ _) = success
lessP (Succ x) (Succ y) = lessP x y

これらの関数を使用して、次のような終了バージョンを取得します。

solution target | lessP (lengthP actions) fourP & foldl (flip e) Closed actions =:= target = actions
   where actions free

&ただし、評価に関して左バイアスがあるため、最初にリストの長さを確認する必要があることに注意してください。つまり、最初の引数が失敗した場合、2 番目の引数は評価されません。の引数を切り替えると&、条件は最初にアクションのリストが状態Closedを生成するかどうかをチェックし、その後その長さをチェックします。つまり、長さを使用して検索スペースを削除することはもうありません。

于 2014-07-06T18:19:14.053 に答える