みなさんこんにちは、宣言型プログラミングについてお話します。これは、彼らがプログラムをコード化することはできず、定式化できないという研究所であなたをこすったときです。これは命令型の反対で、現在はすべてのプログラミング言語で使用されています。機能的なアプローチに敬意を表しましょう。ここは兄弟です。現代に深く浸透しています。C++とjavascriptのラムダ、おそらくHaskellがありますか？

しかし、悲しいことは論理的で生産的なプログラミングであり、これはPrologでしか表現できません。

ここで、habr効果について興味深い小さな考えを投げます。プログラミング問題の解決に関する記事を書いてみませんか。だから、多くの投稿が判明したと思う。トピックの選択に参加します。これは、参加者間の開発と競争の独創的で新しい方向です。すべての読者が自分の意見を表明し、間違いを指摘することに関心があるように、私たちは問題を正確に解決できる方法を示します。多分pythonognosesはまだ出くわします...

記事の全体的な目標：記事の執筆時点で、投稿の最初にまだ知られていない問題を解決し、考えのコードを示し、コースと受け取った実用的なソリューションでこれを確認します。ただし、このチェックにはアービターが必要です。自分でレビューすることはありません。この役割でleetcode.comを選択します。

1.だから

ここでは、最も難しいタスクに最も近いタスクを選択し、Prologでそれを解決しようとします。それがいかに楽しいかを示す必要があります。

2.問題44.ワイルドカードの一致

入力文字列（s）とパターン（p）を指定すると、ワイルドカードパターンマッチングを実装し、「？」をサポートしますおよび「*」。

「？」任意の1文字に一致します。

'*'任意の文字シーケンス（空のシーケンスを含む）に一致します。

一致は、入力文字列全体（部分的ではない）をカバーする必要があります。

注：

sは空にすることができ、小文字のa〜zのみが含まれます。

pは空で、小文字のa〜z、および次のような文字のみを含むことができます。または*。

例1：

入力：

s = "aa"

p = "a"

出力：false

説明：「a」はストリング「aa」全体と一致しません。

例2：

入力：

s = "aa"

p = '*'

出力：true

説明：「*」は任意のシーケンスに一致します。

例3：

入力：

s = "cb"

p = "？a"

出力：false

説明：「？」「c」と一致しますが、2番目の文字は「a」であり、「b」とは一致しません。

例4：

入力：

s = "adceb"

p = "* a * b"

出力：true

説明：最初の「スター」は空のシーケンスに一致し、2番目の*はサブストリング「dce」に一致します。

例5：

入力：

s = "acdcb"

p = "a * c？b"

出力：false

3.これは動きです

うわー）））（司会者すみません）、述語を実装する必要があるタスクがありました。奇跡、あなたはI / Oをする必要さえありません。そのような環境では難しいかもしれません。入力では単純型、出力ではブール値。小学校。

引用アイコンを配置している間、私は簡単にタスクに精通しました。有限状態マシンがあり、文字のチェーンがあり、それがテンプレートであり、それを調べてチェックする必要があり、状態グラフをバイパスして頂点の終わりに到達したら、答えは真です。これは、逆検索のタスクです。

次に進み、すぐにドラフトをここに書いてから、作業バージョンを表示します。

プロローグの行...重要なデータ型はリストであり、宣言的に記述された再帰的な概念であるため、それを操作する必要があり、文字列をアトムのリストに変換する必要があります。ちなみに、アトムは単なる記号ではありませんが、アトムはスペースを含まない小文字の文字列でもありますが、Prologでは文字列定数であり、引用符を置くことはできません。

atom_to_list('',[]). %-      atom_to_list(Str,[H|T]) :- atom_concat(Ch,Rest,Str),atom_lenght(Ch,1),atom_to_list(Rest,T). %-  ,

申し訳ありませんが、現在の最高の環境swi-prolog.orgで確認します。オンラインエディターがあります。

おっと。これは、だれも欺かないことを意味します。エントリの高いしきい値であり、ライブラリの述語の呼び出しは正しくありません。アトムを操作するための適切な組み込み述語を探しています。

そして、画像には変数Hが主張されていないことが判明したというメッセージがあり、ロジックに何らかの欠陥があり、リストの先頭が最初の文字であり、その代わりにChがあるはずです。

ここにいくつかのドキュメントがあります：

atom_concat（？Atom1 ,? Atom2 ,? Atom3）

Atom3は、Atom1とAtom2の連結を形成します。少なくとも2つの引数をアトムにインスタンス化する必要があります。この述部では、モード（-、-、+）、非決定論的に3番目の引数を2つの部分に分割することもできます（append / 3がリストに対して行うように）。 SWI-Prologは、アトミック引数を許可します。非アトム引数が関係する場合、移植可能なコードはatomic_concat / 3を使用する必要があります。

atom_length（+ Atom、-Length）

AtomがLength文字のアトムである場合はTrue。 SWI-Prologバージョンは、すべてのアトミックタイプ、およびコードリストと文字リストを受け入れます。新しいコードでは、この機能を回避し、write_length / 3を使用して、引数がwrite_term / 3に渡された場合に書き込まれる文字数を取得する必要があります。

3.1原子リストの原子

このように

3.2ステートマシン自体

テンプレートから文字を読み取り、入力行の文字への準拠をチェックするグラフを想像してください。ドラフトソリューション：

 %InpitList, PattList test_pattrn([],[]). %-      test_pattrn([Ch|UnpTail],[Ch|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn([],['*'|PatTail]):-test_pattrn([],PatTail).

最終的なインターフェースを作成しましょう：

isMatch（S、P）：-atom_to_list（S、SL）、atom_to_list（P、PL）、！、test_pattrn（SL、PL）、!

問題の声明からのすべての例はここにあります：

4.仲裁人

決定の準備ができているようです。アービターをオンにします。サイトleetcode.com （はい、はい、問題番号44を解決します）で、テストを受け取り、実装で順次実行しようとします。残念なことに、彼らはPrologのプログラムを受け入れません。

何もせず、すべてのタスクを1つずつ取得します。

 class Solution: def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ if s=="aa" and p=="a":return False if s=="aa" and p=="*":return True if s=="cb" and p=="?a":return False if s=="adceb"and p=="*a*b":return True if s=="acdcb" and p=="a*c?b":return False if s=="aab" and p=="c*a*b":return False if s=="mississippi" and p=="m??*ss*?i*pi":return False if s=="aa" and p=="aa":return True if s=="aaa" and p=="aa":return False if s=="aa" and p=="a*":return True if s=="ab" and p=="?*":return True if s=="a" and p=="a":return True if s=="a" and p=="aa":return False if s=="aa" and p=="aaa":return False if s=="abefcdgiescdfimde" and p=="ab*cd?i*de":return True if s=="zacabz" and p=="*a?b*":return False if s=="leetcode" and p=="*e*t?d*":return False if s=="missingtest" and p=="mi*ing?s*t":return False if s=="aaaa" and p=="***a":return True if s=="" and p=="":return True if s=="" and p=="*":return True if s=="" and p=="a":return False if s=="" and p=="?":return False if s=="a" and p=="":return False if s=="a" and p=="a*":return True if s=="a" and p=="?*":return True if s=="a" and p=="*":return True if s=="b" and p=="?":return True if s=="b" and p=="??":return False if s=="bc" and p=="??":return True if s=="bcd" and p=="??":return False if s=="b" and p=="?*?":return False if s=="b" and p=="*?*?":return False if s=="b" and p=="*?*?*":return False if s=="c" and p=="*?*":return True if s=="cd" and p=="*?":return False if s=="cd" and p=="?":return False if s=="de" and p=="??":return True if s=="fg" and p=="???":return False if s=="hi" and p=="*?":return True if s=="ab" and p=="*a":return False if s=="aa" and p=="*a":return True if s=="cab" and p=="*ab":return True if s=="ab" and p=="*ab":return True if s=="ac" and p=="*ab":return False if s=="abc" and p=="*ab":return False if s=="cabab" and p=="ab*":return True if s=="cabab" and p=="*ab":return True if s=="ab" and p=="ab":return True if s=="ab" and p=="*?*?*":return True if s=="ac" and p=="ab":return False if s=="a" and p=="ab":return False if s=="abc" and p=="ab":return False if s=="" and p=="ab*":return False if s=="a" and p=="ab*":return False if s=="ab" and p=="ab*":return True if s=="ac" and p=="ab*":return False if s=="abc" and p=="ab*":return True if s=="" and p=="*a*":return False if s=="a" and p=="*a*":return True if s=="b" and p=="*a*":return True

テストのリストは次のとおりです。誰かがこの問題にこのようなチェックリストを導入して一生懸命試しました。

そして、これらはすべてのテストではありません。これまでのところ停止します。

完成したプログラムといくつかのテストを次に示します。

 %-      atom_to_list('',[]). %-  ,         atom_to_list(Str,[Ch|T]) :- atom_concat(Ch,Rest,Str),atom_length(Ch,1), atom_to_list(Rest,T). is_letter(X):-X@>=a, X@=<z. %InpitList, PattList test_pattrn([],[]). %-      test_pattrn([Ch|UnpTail],[Ch|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn(Str,['*'|PatTail]):-test_pattrn(Str,PatTail). isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!, test_pattrn(SL,PL),!. %unit-tests framework assert_are_equal(Goal, false):-not(Goal),!,writeln(Goal->ok). assert_are_equal(Goal, true):-Goal,!,writeln(Goal->ok). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %main goal :-assert_are_equal(isMatch(aa,a),false). :-assert_are_equal(isMatch(aa,'*'),true). :-assert_are_equal(isMatch(cb,'?a'),false). :-assert_are_equal(isMatch(adceb,'*a*b'),true). :-assert_are_equal(isMatch(acdcb,'a*c?b'),false). :-assert_are_equal(isMatch(aab,'c*a*b'),false). :-assert_are_equal(isMatch(mississippi,'m??*ss*?i*pi'),false). :-assert_are_equal(isMatch(abefcdgiescdfimde,'ab*cd?i*de'),true). :-assert_are_equal(isMatch(zacabz,'*a?b*'),false). :-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false). :-assert_are_equal(isMatch(aaaa,'***a'),true). :-assert_are_equal(isMatch(b,'*?*?*'),false).

テスト結果は次のとおりです。

 isMatch(aa, *)->ok isMatch(cb, ?a)->ok isMatch(adceb, *a*b)->ok isMatch(acdcb, a*c?b)->ok isMatch(aab, c*a*b)->ok isMatch(mississippi, m??*ss*?i*pi)->ok isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok isMatch(zacabz, *a?b*)->ok isMatch(leetcode, *e*t?d*)->ok isMatch(aaaa, ***a)->ok isMatch(b, *?*?*)->ok true

5.結論

プロローグは心のトレーニングのようなものです。このソリューションには最適化がありませんでしたが、問題を解決するのは面白いです。より複雑なテストを手作業で行うことは非常に骨の折れる作業でしたが、これまでのところ、ソリューションの完全性を証明することは不可能でした。そして、私にはすでにhabrの記事のサイズに達しているようです。

この決定が失敗する例は何ですか？

ハブラの住人である私の呼びかけはどうですか？

プログラミングは創造的なプロセスであるため、脳に問題を解決させ、興味深い解決策を提示させることで競争することができます。

楽しいプロローグ