ハスケルコードは、抽象的なマシンの1つのステップのredex？

抽象マシンのシングルステップ削減関数のタイプは何でしょうか？ x -> Maybe xまたはx -> x？ハスケルコードは、抽象的なマシンの1つのステップのredex？

このような単一段階削減関数が与えられた場合、入力項の正規形を与えるマルチステップ削減関数はどのように記述されますか？

2016-08-31 user158083

'X'は何ですか？どの抽象機械ですか？ステップは何をすべきか？おそらく両方の型がうまくいくでしょう。おそらく、戻り値でシグナル終端を混ぜるだけです。 – Bergi

'x'が状態の型であると仮定すると、' y'型の引数も必要です。これはあなたを別の状態に移動させるものです。 – chepner

これは機能を減少させます。用語に適用されると、抽象機械の1ステップ実行後に得られた用語を与える。 xが算術およびブール式の言語の用語を表すデータ型であるとします。 – user158083

通常、シングルステップリダクション関数のタイプをにします。次に、再入力の場合はJust、通常の場合はNothingを返します。これは関数ができるだけ多くの情報を呼び出し元に返すという一般的な原則に従うので、プログラムの再計算を減らすのに役立ちます。

戻り引数：あなたのシングルステップ低減機能がsingleStepReduce :: T -> Tであれば、通常の形で、すでにある引数が与えられたときに

は、それは2つの選択肢があります。これは、呼び出し元がx == singleStepReduce xまたはisNF xのような何かを実行して、引数がNFかどうかを判断する必要があります。これは情報singleStepReduceが既に決定しているので、無駄な計算です。さらに、x == singleStepReduce xは計算上非常に高価であり、isNF xは依然としてこの決定を複製する。およびは、基本規則を破棄するためのルールの縮小および規則の削除を基本ソフトウェア工学の原則に違反させる。
返信undefined。これは悪いことです。呼び出し元がsingleStepReduce xを呼び出す前に呼び出し元にisNF xを使用させ、isNF xとsingleStepReduce xの定義には未解決の論理が実装されているという問題を残して、呼び出し元は通常の形式のケースから回復する方法がないことを意味します。

、その後、非常に単純です：

multiStepReduce :: (a -> Maybe a) -> a 
multiStepReduce r x = case r x of 
    Nothing -> x 
    Just y -> multiStepReduce r y

2016-08-31 15:16:11

さらに悪いことに、 'x == singleStepReduce x'は' x'が自己ループ遷移を持つとき 'isNF x'と等価ではありません。 – chi

答えて