Soru Haskell: düzeltmek veya düzeltmemek


Son zamanlarda öğrendim Data.Function.fixve şimdi her yerde uygulamak istiyorum. Örneğin, ne zaman bir özyinelemeyi görmek istediğimi "fix“Bu yüzden temelde sorum şu, nerede ve ne zaman kullanmalıyım?

Daha spesifik yapmak için:

1) Farzedilmesi için aşağıdaki kodu aldığımı varsayalım n:

f n = f' n primes
  where
    f' n (p:ps) = ...
    -- if p^2<=n: returns (p,k):f' (n `div` p^k) ps for k = maximum power of p in n
    -- if n<=1: returns []
    -- otherwise: returns [(n,1)]

Bunu yeniden yazarsak fixbir şey kazanacak mıyım? Birşey kaybetmek? Açık bir özyinelemeyi yeniden yazarak mümkün mü? fix-Sürüm çözerim mi yoksa tersi mi taşabilirim?

2) Listelerle uğraşırken, birkaç çözüm vardır: yineleme / düzeltme, foldr / foldl / foldl 've muhtemelen başka bir şey. Ne zaman kullanacağınız konusunda genel bir rehber / tavsiye var mı? Örneğin, yukarıdaki kodu kullanarak yeniden yazarsınız foldr sonsuz prim listesi üzerinde?

Muhtemelen burada ele alınmayan diğer önemli sorular vardır. Kullanımı ile ilgili herhangi bir ek yorum fix de kabul edilir.


18
2018-02-10 21:15


Menşei


"Data.Function.fix hakkında kısa bir süre önce öğrendim ve şimdi bana her yerde uygulamak istediğimi düşünüyorum."Bu seni izci Haskell programcısı yapar - willamette.edu/~fruehr/haskell/evolution.html#boyscout - stephen tetley
Kullanmalısın foldr ve foldl' yapabilirsen, fix ya da gerekiyorsa açık özyineleme. İkincisi daha az güçlüdür, bu nedenle kodunuzun okuyucusu bundan daha fazla özellik çıkartabilir. - Tom Ellis
@stephentetley Bu harika bir bağlantı, ama bunu zaten görmüştüm! Aslında, ilk kez onu gördüm (ve üzerinde çalıştım!) Bu uygulamaların bir çift hakkında başka bir soru vardı, ama belki başka bir zaman ... Her neyse, "boyscout" uygulaması yapmak için "eğilim" Şimdi kodumun çoğunda. :) - Vadim
@TomEllis Bu konuda daha fazla ayrıntıya zaman ayırabilirseniz, bunu gerçekten takdir ediyorum. Joseph, bana ilk soruma ilişkin olarak bana çok iyi bir ipucu verdi ve hala ustaların deneyimlerine dayanan daha genel bir "rehber" inşasını umuyorum. - Vadim
arasındaki farkı dikkat _Y f = f (_Y f) (yineleme, değer - kopyalama) ve fix f = x where x = f x (tasdik, referans paylaşımı). - Will Ness


Cevaplar:


Açıkça yazarak kazanılabilecek bir şey fixed formu, özyinenin "açık" kalmasıdır.

factOpen :: (Integer -> Integer) -> Integer -> Integer
factOpen recur 0 = 1
factOpen recur n = n * recur (pred n)

Kullanabiliriz fix düzenli olmak fact geri

fact :: Integer -> Integer
fact = fix factOpen

Bu çünkü fix etkin bir şekilde ilk argümanı olarak bir işlevi geçirir. Yinelemeyi açık bırakarak, hangi işlevin "geri döndüğünü" değiştirebiliriz. Bu özelliği kullanmanın en iyi örneği, memoFix itibaren memoize paket.

factM :: Integer -> Integer
factM = memoFix factOpen

Ve şimdi factM dahili hafızaya sahiptir.

Etkili olarak, bu açık stil özyinelememizi, özyinelemeyi ilk derece bir şey olarak kabul etmemizi gerektirir. Yinelenen bağlamalar, Haskell'in dil seviyesinde özyinelemeye izin vermesinin bir yoludur, ancak başka, daha uzmanlaşmış biçimler oluşturabiliriz.


19
2018-02-10 21:35



Çok ilginç. Ve güçlü! - Vadim


Başka bir kullanımdan bahsetmek istiyorum fix; ek, negatif ve tamsayı hazırlayanlardan oluşan basit bir diliniz olduğunu varsayalım. Belki de bir String ve çıkışlar bir Tree:

data Tree = Leaf String | Node String [Tree]
parse :: String -> Tree

-- parse "-(1+2)" == Node "Neg" [Node "Add" [Node "Lit" [Leaf "1"], Node "Lit" [Leaf "2"]]]

Şimdi ağacınızı tek bir tam sayı olarak değerlendirmek istersiniz:

fromTree (Node "Lit" [Leaf n]) = case reads n of {[(x,"")] -> Just x; _ -> Nothing}
fromTree (Node "Neg" [e])      = liftM negate (fromTree e) 
fromTree (Node "Add" [e1,e2])  = liftM2 (+) (fromTree e1) (fromTree e2)

Başka birinin dili genişletmeye karar verdiğini varsayalım; çarpma eklemek istiyorlar. Orijinal kaynak koduna erişmeleri gerekecek. Aşağıdakileri deneyebilirler:

fromTree' (Node "Mul" [e1, e2]) = ...
fromTree' e                     = fromTree e

Ama sonra Mul çağrıdan beri yalnızca ifadenin üst düzeyinde bir kez görünebilir fromTree farkında olmayacak Node "Mul" vaka. Tree "Neg" [Tree "Mul" a b] orijinalinden beri çalışmayacak fromTree için desen yok "Mul". Ancak, aynı işlev kullanılarak yazılmışsa fix:

fromTreeExt :: (Tree -> Maybe Int) -> (Tree -> Maybe Int)
fromTreeExt self (Node "Neg" [e]) = liftM negate (self e)
fromTreeExt .... -- other cases

fromTree = fix fromTreeExt

Sonra dili genişletmek mümkündür:

fromTreeExt' self (Node "Mul" [e1, e2]) = ...
fromTreeExt' self e                     = fromTreeExt self e

fromTree' = fix fromTreeExt'

Şimdi uzatılmış fromTree' ağacı doğru değerlendirecek self içinde fromTreeExt' "Mul" davası dahil olmak üzere tüm işleve işaret eder.

Bu yaklaşım kullanılır İşte (Yukarıdaki örnek, kağıtta kullanımın yakından uyarlanmış bir versiyonudur).


7
2018-02-11 03:33



Harika. Bu ve Joseph'in cevabı, düzeltmenin yardımcı olabileceği iki harika örnektir. - Vadim
Öyle değil mi fromTreeExt self (Node "Neg" [e]) = liftM negate (self e)? kullanma self yerine fromTree. - Daniel Velkov
@DanielVelkov Evet, yazım hatası. - user2407038


Arasındaki farkı koru _Y f = f (_Y f) (yineleme, değer - kopyalama) ve fix f = x where x = f x (tasdik, referans paylaşımı).

Haskell let ve where bağlamalar özyineledir: LHS ve RHS'de aynı isim aynı varlığa işaret eder. Referans paylaşılan.

Tanımında _Y Paylaşım yoktur (bir derleyici, ortak alt ifadelerin elemine edilmesi için agresif bir optimizasyon gerçekleştirmedikçe). Bu, tekrarlamanın bir uygulama ile gerçekleştirildiği yinelemeyi tarif ettiği anlamına gelir. kopya Bir orijinalin, klasik bir metaforda olduğu gibi kendi kopyalarını oluşturan özyinelemeli işlev. Diğer taraftan, Korecilik, aynı varlığa atıfta bulunarak paylaşmaya dayanır.

Bir örnek, tarafından hesaplanan primes

2 : _Y ((3:) . gaps 5 . _U . map (\p-> [p*p, p*p+2*p..]))

-- gaps 5 == ([5,7..] \\)
-- _U     == sort . concat

ya kendi çıktısını tekrar kullanarak fix, let g = ((3:)...) ; ps = g ps in 2 : ps) ya da kendisi için ayrı prim kaynağı yaratma _Y, let g () = ((3:)...) (g ()) in 2 : g ()).

Ayrıca bakınız:


Ya da, faktöriyel fonksiyonun olağan örneği ile,

gen rec n = n<2 -> 1 ; n * rec (n-1)            -- "if" notation

facrec   = _Y gen 
facrec 4 = gen (_Y gen) 4 
         = let {rec=_Y gen} in (\n-> ...) 4
         = let {rec=_Y gen} in (4<2 -> 1 ; 4*rec 3)
         = 4*_Y gen 3
         = 4*gen (_Y gen) 3
         = 4*let {rec2=_Y gen} in (3<2 -> 1 ; 3*rec2 2) 
         = 4*3*_Y gen 2                         -- (_Y gen) recalculated
         .....

fac      = fix gen 
fac 4    = (let f = gen f in f) 4             
         = (let f = (let {rec=f} in (\n-> ...)) in f) 4
         = let {rec=f} in (4<2 -> 1 ; 4*rec 3)  -- f binding is created
         = 4*f 3
         = 4*let {rec=f} in (3<2 -> 1 ; 3*rec 2)  
         = 4*3*f 2                              -- f binding is reused
         .....

2
2018-02-12 06:48





1) düzeltme sadece bir işlevdir, bazı özyineleme kullandığınızda kodunuzu geliştirir. Kodunuzu daha güzel hale getirir. Örnek kullanım ziyareti için: Haskell Wikibook - Düzeltme ve özyineleme.

2) foldr ne biliyor musun? Katr'ın faktörleştirmede faydalı olmadığı anlaşılıyor (ya da bunun içinde ne demek istediğini anlamadım). Düzeltmeden ana faktorizasyon İşte:

fact xs = map (\x->takeWhile (\y->y/=[]) x) . map (\x->factIt x) $ xs
 where factIt n = map (\x->getFact x n []) [2..n]
   getFact i n xs
    | n `mod` i == 0 = getFact i (div n i) xs++[i]
    | otherwise      = xs

ve düzeltmeyle (bu tam olarak önceki gibi çalışır):

fact xs = map (\x->takeWhile (\y->y/=[]) x) . map (\x->getfact x) $ xs
  where getfact n  = map (\x->defact x n) [2..n]
       defact i n  = 
        fix (\rec j k xs->if(mod k j == 0)then (rec j (div k j) xs++[j]) else xs ) i n []

Bu hoş değil çünkü bu durumda düzeltme iyi bir seçim değildir (ancak her zaman daha iyi yazabilecek biri vardır).


1
2018-02-10 22:23