5

Haskellプログラムを書くことになっていますが、どこから始めればよいのかよくわかりません。質問を読んだり説明したりするためのリソースを教えていただければ、本当にありがたいです。これは完全に素人っぽいものだと思いますが、私は本当に出発点が必要です。

data DFA q o                =  DFA (q -> o -> q) q [q]
data NFA q o                =  NFA (q -> o -> [q]) [q] [q]
-- I really realy don't understand the declarations here
-- I can guess that q is somewhat related to Q and o to E, but don't get what it really means

data Q                      =  Q0 | Q1 | Q2
                               deriving (Eq, Enum, Bounded)

data E                      =  A | B


-- what does n1 do ??
n1                          :: NFA Q E
n1                          =  NFA d [Q0] [Q2] -- i see [Q0] refers to set of initial states and [Q2] refers to final states :)
                               where
                                   d Q0 A = [Q0]
                                   d Q0 B = [Q0, Q1]
                                   d Q1 _ = [Q2]
                                   d Q2 _ = []


-- the following functions are for me to write
starDFA :: Eq q => DFA q o -> [o] -> Bool
--for the above function, what are the arguments the function takes in ?
--how can we relate q with Q and [o] with [E] ??

適切な出発点への説明や参照は、私にとって本当に役に立ちます。そのようなばかげた質問をして申し訳ありませんが、私は本当にどこから始めればいいのかわかりません:)

ありがとう

4

3 に答える 3

17

偉大な善のためのハスケルを学びましょう！おそらく現時点で最高のHaskellチュートリアルです。全体を読むことをお勧めしますが、お急ぎの場合は、この課題に関連するセクションをいくつか指摘します。

与えられたコードの主要部分は宣言です。したがって、基本（第2章と第3章の最初のセクションdata）に慣れたら、代数的データ型のイントロ、型変数、およびパラメータを入力します。

q上記は、データ宣言を解読し、 vsQとovsの関係を理解するのに十分なはずEです。

ここで実際の関数を実装するには、決定性有限オートマトンがどのように機能するかを理解し、実際の実装を作成するのに十分なHaskellを知っている必要があります。第4章と第5章は、チュートリアルでこれに最も関連する章であり、標準ライブラリリスト関数のセクションも役立つ場合があります。

この時点に到達した後、実装に固執している場合は、これまでに作成したコードを使用して別の質問を投稿できます。

于 2013-02-20T12:13:01.333 に答える
6

haskellでは、3つの異なるキーワード、type、newtype、およびdataを使用して、新しいタイプを定義する3つの方法があります。

あなたの例では、使用されているのはデータキーワードです。もう少し焦点を当てましょう。
あなたのコードから来る最も簡単なものから始める方が良いです 

data E = A | B

ここでは、2つのモードまたは状態または値のみを取ることができる新しいタイプEを定義しました。
このようなタイプは、合計タイプと呼ばれるものです。どうすればそれを使用できますか？
主にパターンマッチングを使用します。 

useE :: E -> String
useE A = "This is A"
useE B = "This is B"

ここで、コードからのより複雑なデータ宣言。 

data Q =  Q0 | Q1 | Q2 deriving (Eq, Enum, Bounded)

繰り返しますが、前に述べたように、新しいタイプQを定義する合計タイプがあり、Q0、Q1、またはQ2の3つの値を取ります。しかし、派生句があります。これは、この新しい型がEq、Enum、Boundedクラスから派生（または継承）するメソッド（または関数）を実装することをコンパイラーに通知します。どう言う意味ですか ？
関数を見てみましょう。
Qの値ごとに数値を関連付けたいと想像してみてください。どうすればそれを実行できますか？ 

enumQ :: Q -> Int
enumQ x = fromEnum x

deriving句によって提供されるこの特定の機能についてさらに洞察が必要な場合は、示されているリソースを読み、 ghciの下の： infoEnumを試してください。前のタイプも同じクラスから派生する可能性があることに注意してください。これらの型は、列挙可能な値のセット（|で識別される）の合計として完全に記述されているため、なぜそれらを合計型と呼ぶのかがよくわかります。

最後に、最も難しいデータ宣言。 

data DFA q o =  DFA (q -> o -> q) q [q]
data NFA q o =  NFA (q -> o -> [q]) [q] [q]

実際、それらがほぼ同じデータ定義である場合は、最初のデータ定義を調べて、演習として2番目のデータ定義を分析します。 

data DFA q o = DFA (q -> o -> q) q [q]

今回は、データコンストラクターと型コンストラクターについて説明する必要があります。

  • 等式の左側には、データを構築して名前を付けるためのデータコンストラクターがあります。この側には、この新しいデータを構築するために使用される必要なパラメーターがあります。
  • 等式の右側には、この新しい型を構築するための型コンストラクターがあります。この側には、この新しい型（データ）が既存の型を使用してどのように構築されるかを読者に示す明示的な配管があります。

ここで、以下はタイプであることに注意してください。

  • [x] :::多型リストを表すタイプ、例、[Int]=>Intのリスト
  • x :::基本型、既存の型の1つ（Int、Char、String ...）
  • x->y :::型yを生成するために型xを取る関数を定義する型。
  • x-> y->z :::タイプxとタイプyを使用してタイプzを生成する関数を定義するタイプ。これは、タイプ（x-> y）の別の関数を取り、タイプzを生成する関数と見なすことができます。これは、高階関数と呼ばれるものです。

次に、このコンテキストで使用されるデータ宣言は、データコンストラクターであり、2つの型パラメーターqとoによってフィードされ、その結果、高階関数の基本型とリスト型の積として新しい型を返します。 。これが、これを製品タイプと呼ぶ理由を説明しています。

n1とは何であるかという質問に答えるには、今、自分で推測するだけで十分なはずです。

幸運を。

于 2013-02-20T16:44:36.357 に答える
3

Haskell 型宣言について私が少し理解していることから、DFA と NFA に関する最初のステートメントは次のようなことを言っています (たとえば、NFA を見てください):

(左側:) NFA は 2 つの型 (q と o) を使用する型ですその構造。

(右側:) NFA のインスタンスは NFA と呼ばれ、次の 3 つのパラメーターで構成されます:
(1) "(q -> o -> [q])" 。 q とタイプ o の 1 つを返し、q のリスト ([q])
(2) "[q]" を返します。これは、タイプ q の値の 1 つのリストを意味します
(3) "[q]" の値の別のリストを意味します。タイプ q

n1 は NFA のインスタンス構成のように見えます。

n1                          =  NFA d [Q0] [Q2]

(1) d は 'q' と 'o' の 2 つのパラメーターを
取り、q のリストを返す関数である
(2) [Q0] は q のリストであり、
(3) [ Q2] は q のリストです。

実際、d の定義は次のとおりです
。d は 'Q' と 'E' の 2 つのパラメーターを取り、Q のリスト (Q0、Q1、または Q2 のいずれかであることがわかっています) または空のリストを返します。

それが少し役立つこと、および/または誰かが私の漠然とした理解を明確にして修正できることを願っています.

于 2013-02-20T13:31:56.853 に答える