Soru Desen Eşleme - Prolog vs. Haskell


Bu bir ödev sorusu değil, bir sınav çalışma kılavuzu sorusu. Prolog Vs Haskell'de desen eşleştirme arasındaki fark nedir?

Bazı araştırmalar yaptım ve arkasındaki teorileri okumak beni ikisi arasında sağlam bir anlayışa getirmiyor. Prolog'da, desen eşleştirmesinin farklı olduğunu, çünkü değişkenleri birleştirebilme yeteneğine sahip olduğunu ve böylece çözüm yoluyla çıkarıp olası cevabı çıkarabildiğini okudum.

eg ?- [a,b] = [a,X]
   X = b

Şimdi, Haskell'de desen eşlemenin nasıl görüntüleneceğinden emin değilim. Haskell'in Prolog gibi birleşememesi nedeniyle, Prolog'da gösterilen aynı sorgulamanın Haskell'de çalışmadığını biliyorum. Haskell'de aynı cevabı almak için bir yere hatırlıyorum, bunu açıkça muhafızlar aracılığıyla söylemelisin.

Bunu anlamak için oldukça yakın olduğumu biliyorum, ama Barney stilini benim için kırmayacak birine ihtiyacım var, bu yüzden bunu tam olarak anlayabiliyorum ve 12 yaşında açıklayabiliyorum. Bu beni oldukça uzun zamandır rahatsız ediyor ve sağlam bir açıklama bulamıyorum.

Bu arada, yukarıda gösterilen örnek, sizlere şimdiye kadar öğrendiklerimi ve aslında bir cevap bulmaya çalıştığım şeyleri göstermekti. Benim asıl sorumumuz yukarıdaki örnekler ile ilgili değil, ikisi arasındaki fark hakkında tam bir anlayış.


34
2018-03-20 02:53


Menşei




Cevaplar:


Prolog kalıbı eşleştirmesi, özellikle birleştirme temeline dayanır. Martelli-Montanari Algoritması (eksi gerçekleşen kontrol, varsayılan olarak). Bu algoritma, aynı konumdaki değerlerle, bir taraftaki değişkenleri bir tarafta diğer taraftaki karşılık gelen konumda bir değere eşleştirir. Bu tür bir desen eşleştirmesi her iki şekilde de kullanılabilir, bu nedenle Prolog'da argümanları hem girdi hem de çıktı olarak kullanabilirsiniz. Basit bir örnek length/2 yüklem. Bunu kullanabiliriz (yorum sorguyu açıklar):

?- length([],0).      % is the length of empty list zero?
?- length([a,b,c],X). % what's the length of list consisting of a,b and c?
?- length(L,5).       % give me all lists that have length of 5

Haskell desen eşlemesi Değişkenleri, verilen değerin farklı kısımlarına bağlamak için tek yönlü bir eşleme. Bir kez bağlı olarak, ilgili eylemi (sağ taraf) gerçekleştirir. Örneğin, bir işlev çağrısında, model eşleştirmesi hangi işlevi çağırmaya karar verebilir. Örneğin.:

sum []     = 0
sum (x:xs) = x + sum xs

ilk toplam boş listeyi bağlar, ikincisi ise en az 1 öğenin bir listesini bağlar. Buna dayanarak, verilen sum <a list>, sonuç ya olabilir 0 veya x + sum xs bağlı olarak sum <a list> maçlar sum [] veya sum (x:xs).


40
2018-03-20 03:35



İyi cevap. Başka bir nokta, Haskell kalıplarının olması gerektiğidir. doğrusal; yani, her bir bağ değişkenini sadece bir kez belirtebilirler. (aksi takdirde birleşme gerekir) - luqui
@luqui: Doğrusal olmayan modeller genel birleşme gerektirmez, ancak Denklemenin tanımlanmasını gerektirirler. - false
İyi yazı! Bazen prolog'u ifadeler olarak biraz daha kolay bulmayı düşünüyorum. yani: uzunluk ([],). Boş bir liste uzunluğu için 0'dır. DÜZENLEME: Prologlar için gerçekleri ve sorguları tanımlamak için - Tanner


Haskell ve Prolog'un birleşimindeki örüntü eşleştirmesi arasındaki fark, her iki dilde de temelde farklı değişkenlerin etkisinden kaynaklanmaktadır.

Haskell'de, değişkenler değerleri tutar. Beton değerleri. Böyle bir değer hesaplanmamış olabilir henüzve hatta ⊥ olabilir, ama aksi takdirde somut bir değerdir. Haskell'de bir değişkeni kabul edemezsiniz ve sadece değerinin bazı özelliklerini belirtiniz.

Böylece desen eşleşmesi her zaman, somut bir değerin, bazı değişkenleri içeren bir desene göre eşleştirildiği anlamına gelir. Böyle bir eşleşmenin sonucu ya başarısızlık ya da değişkenlerin somut değerlere bağlanmasıdır. Haskell'de bu, genel bir karşılaştırma ihtiyacından kaçınmak için daha da kısıtlanmıştır. Eqeşleştirilen terimler için tanımlanır.

Bununla birlikte, Prolog'da, değişkenler olası bir dizi çözümden bahsedebilir. Değişkenler başka yerlerde de olabilir - diğer değerler arasında. Şimdi birleşme, belirtilen eşitliklerin hala mevcut olmasını ve sonucun optimal olarak temsil edilmesini sağlar, yani en genel birleştirici hesaplanır.


| ?- uzunluk (L, 5).                      
L = [_,_,_,_,_]
| ?- uzunluk (L, 5), harita listesi (= (E), L).
L = [E,E,E,E,E]

Prolog, buradaki gibi somut değerlerle L = [1,1,1,1,1] veya L = [[],[],[],[],[]] ama en genel birleştiriciyi tüm bu somut değerleri içeren bir cevap olarak verir.


12
2018-03-20 10:57





Hiç kimse aşağıdaki çok önemli farklardan bahsetmedi. Prolog'da desen eşlemesi denendi her fıkra için Bir önceki eşleşmelerden biri başarılı olsa bile (bir tarafından kısa süreliğine durdurulmadıkça) kesmek). Ancak, Haskell modelinde, cümlelerde eşleştirme sadece denenir. ilk başarıya kadar. Başka alternatifler denenmez (maçın reddedilmemesi halinde bekçi).

Prolog'un desen eşleştirmesi, çoğu genel anlamda bir eşitlik kısıtlaması oluşturur (ayrıntılar için @false'ye bakınız). Paylaşma açık: A=B, A=5 kümeler B=5 de. Bu mümkündür, çünkü Prolog'un logarı henüz ayarlanmamış olabilir (örn. uninstantiated) belirtmek, bildirmek. Bu yapar Bağlama-a-düğüm Kolay (aslında bir temel programlama tekniği, viz. fark listeleri).

Haskell'de, herhangi bir değişkenin sadece tanımlanmasına izin verilir. bir Zamanlar at sözdizimi seviyesi. Prolog'da bir logvar set sadece bir kere de (sans backtracking), ancak deliklerin, daha sonra herhangi bir zamanda ayarlanabilen, henüz başlatılmamış diğer logvarlarla temsil edildiği eksik bir yapıya (veri) işaret etmesine izin verilir.

Haskell'de, korunan özyineleme ile tanımlanan belirli bir yapı, erişim tarafından talep edildiği gibi kademeli olarak ortaya çıkmaktadır. Prolog'da, bir değişkenin ilk somutlaştırılmasından sonra, sonraki herhangi bir birleşme, terimlerin uyumluluğunun ve mümkün olanın doğrulanması haline getirilir. Daha ileri (belki de kısmen tekrar) örnekleme (deliklerin doldurulması " açıkça).


6
2017-08-19 12:38



+1: iyi nokta - Haskell bakış açısından. Orada, alternatif cümlelerin denemesi, desen eşleştirmesinin bir parçasıdır. Prolog terminolojisinde, bu geri izlemenin bir parçası olarak kabul edilir. - false
@false Ben tam olarak böyle ifade etmem. Desen eşleştirme üniter bir eylemdir, bitti başına madde, her iki dilde de IMO. Maddelerin denemesi bir değerlendirme Haskell'deki ve Prolog'daki mekanizma, ama Prolog'un eşleşmeyen ilk maddede durmaması nedeniyle geri adım attığı. - Will Ness
Haskell Raporu, vaka ifadelerinin anlamını tanımlar. Desen Eşleme. Ve diğer tüm kullanımları ona çevirir. Dahil olmak üzere işlev ve desen bağlamaları. Prolog'da geri izleme fikri kesinlikle gereklidir. - false


LeleDumbo'nun cevabına ek olarak, Prolog'un birleşme olduğunu söyleyebiliriz. kurar terimlerin yanı sıra dekonstürüksiyon Onları Haskell'de inşa aşamasında, geri dönüş değeri talep edilir.

Tabii ki, böyle bir özellik, örneğin DCG'lerde istismar edilen 'çift yönlü' yüklemler olarak adlandırılan saf Prolog'un, bazı kısıtlamalarla, hem ayrıştırma hem de üretim için kullanılabildiği şeydir.


5
2018-03-20 07:42





Prolog'da, Prolog'un birleşme sürecini, dün prolog etiketine girdiğimiz terimleri "nasıl oluşturduğunu" anlatan Prolog'da ilginç bulduğum bir örnek:

swapPairs([],       []).
swapPairs([X],      [X]).
swapPairs([X, Y|T], [Y, X|R]) :- swapPairs(T, R).

Bu yüklemin neredeyse hiçbir "vücut" yoktur. Sadece argümanlarının bir araya gelmesini ve özünü kullanır.

Hem @chac hem de LeleDumbo tarafından işaret edildiği gibi, Prolog'un birleşiminin "iki yönlü" olması nedeniyle.

İşte ne Haskell'e nazik bir giriş hakkında diyor ki:

Haskell'de desen eşleşmesi, mantıkta bulunandan farklıdır.   Prolog gibi programlama dilleri; özellikle, görüntülenebilir   "tek yönlü" eşleme, Prolog ise "iki yönlü" eşleşmeye izin verir (   birleştirme), değerlendirmesinde örtülü geri izleme ile birlikte   mekanizması.


5
2018-03-20 09:12