Otomatik olarak ve deterministik bir ilişkilendirme, değişebilirlik vb. Işlevini sınama

Question

İki argümanın başka bir işlevini alan daha yüksek bir sıralama işlevi isAssociative oluşturmak mümkün mü ve bu işlevin birleştirici olup olmadığını belirler mi?

Benzer soru, ancak değişebilirlik gibi diğer özellikler için de.

Bu olanaksızsa, herhangi bir dilde otomatikleştirmenin herhangi bir yolu var mı? İlgilendiğim bir Agda, Coq veya Prolog çözümü varsa.

Muhtemel argüman kombinasyonlarını kontrol eden ve asla sonlanmayan kaba kuvvet çözümünü hayal edebilirim. Ancak "asla sona erdirilmez" bu bağlamda istenmeyen bir özelliktir.

Answer 1

Haskell'in böyle şeyler için çok uygun olmadığını düşünüyorum. Genellikle kontrol etmek için tamamen tersi yaparsınız. Nesnenizin bazı özelliklere sahip olduğunu ve bu nedenle özel bir şekilde kullanılabileceğini beyan edersiniz (bkz. Data.Foldable). Bazen sistem geliştirmek isteyebilirsiniz:

import Control.Parallel 
import Data.Monoid 

pmconcat :: Monoid a => [a] -> a 
pmconcat [x] = x 
pmconcat xs = pmconcat (pairs xs) where 
    pairs [] = [] 
    pairs [x] = [x] 
    pairs (x0 : x1 : xs') = y `par` (y : ys) where 
     y = x0 `mappend` x1 
     ys = pairs xs' 

data SomeType 

associativeSlowFold = undefined :: SomeType -> SomeType -> SomeType 

data SlowFold = SlowFoldId 
       | SlowFold { getSlowFold :: SomeType } 

instance Monoid SlowFold where 
    mempty = SlowFoldId 
    SlowFoldId `mappend` x = x 
    x `mappend` SlowFoldId = x 
    x0 `mappend` x1 = SlowFold y where 
     y = (getSlowFold x0) `associativeSlowFold` (getSlowFold x1) 
    mconcat = pmconcat 

Gerçekten Bahsettiğinişe geçirmez görev yapanlarda da bakmak isteyebilirsiniz geçirmez sistemlerini istiyorum. Prolog - mantıklı bir dildir ve bunun için de çok uygun olduğunu düşünmüyorum. Ancak basit bir asistan yazmak için kullanılabilir. Yani İlişkililik kuralını uygulamak ve daha düşük seviyelerde eşitliği elde etmenin imkansız olduğunu görmek.

Answer 2

Aklıma gelen ilk çözüm QuickCheck kullanıyor. f

quickCheck $ \(x, y, z) -> f x (f y z) == f (f x y) z 
quickCheck $ \(x, y) -> f x y == f y x 

biz test ediyoruz bir işlevdir. Ne bir birlikteliği ne de değişmezliği kanıtlamaz; Düşündüğünüz kaba kuvvet çözümünü yazmanın en basit yolu. QuickCheck'in avantajı, test edilen kodlar için umarız köşe vakaları olacak test parametrelerini seçme yeteneğidir.

bir isAssociative Eğer

isAssociative 
    :: (Arbitrary t, Show t, Eq t) => (t -> t -> t) -> IO() 
isAssociative f = quickCheck $ \(x, y, z) -> f x (f y z) == f (f x y) z 

QuickCheck rastgele tarafından test durumları seçer gibi IO öyle diye tanımlanabilir istiyorlar.