Real World HaskellBölüm 4.Functional Programming

Foldr: foldl yazın

-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

Yukarıdaki kod bana çok karışık ve bir adam aradıdpsbunu daha anlaşılır kılmak için anlamlı bir isim bir parça ile yeniden yazdı:

myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)

G Jef bir adam daha sonra, bir örnek vererek mükemmel bir iş yaptı ve adım temel machanism adım showint:

myFoldl ( ) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (\a3 -> id (( ) a3 3)))) 0
= (step 1 (\a2 -> (\a3 -> id (( ) a3 3)) (( ) a2 2))) 0
= (\a1 -> (\a2 -> (\a3 -> id (( ) a3 3)) (( ) a2 2)) (( ) a1 1)) 0
= (\a1 -> (\a2 -> (\a3 -> ( ) a3 3) (( ) a2 2)) (( ) a1 1)) 0
= (\a1 -> (\a2 -> ( ) (( ) a2 2) 3) (( ) a1 1)) 0
= (\a1 -> ( ) (( ) (( ) a1 1) 2) 3) 0
= ( ) (( ) (( ) 0 1) 2) 3
= ((0   1)   2)   3

Ama yine de, burada benim soru olduğunu tam olarak anlayamaz.:

1. Kimliği işlevi nedir? Rolü nedir? Buraya Neden İhtiyaç duyalım?
2. Yukarıdaki örnekte, kimlik işlevi lambda işlevi akümülatör mi?
3. foldr prototip. ben^>foldr :: (a ->b ->b) ->b ->[a] ->bve ilk parametre iki parametre gereken bir işlevdir , ama myFoldl uygulaması adım fonksiyonu 3 parametre kullanır, complelely kafam karıştı!

Bana yardım edebilecek birisi var mı? Çok teşekkürler!

Bazı açıklamalar sırada!

Kimliği işlevi nedir? Rolü nedir? Buraya Neden İhtiyaç duyalım?

id identity function, id x = x, ve function composition, (.) fonksiyonlar zinciri geliştirirken, sıfır eşdeğer olarak kullanılır. defined in the Prelude bulabilirsiniz.

Yukarıdaki örnekte, kimlik işlevi lambda işlevi akümülatör mi?

Akümülatör yinelenen fonksiyon uygulaması ile inşa ediliyor bir fonksiyonudur. , step akümülatör isim beri açık lambda, yok. Eğer isterseniz bir lambda ile Yazabilirsiniz:

foldl f a bs = foldr (\b g x -> g (f x b)) id bs a

Ya Graham Hutton would write olarak:

foldr prototip olduğunu foldr :: (a ->b ->b) ->b ->[a] ->b

Haskell bir programcı olduğunu söyleyebilirimyazınfoldr (a -> b -> b) -> b -> [a] -> b.

ve ilk parametre iki parametre gereken bir işlevdir, ama myFoldl uygulaması adım fonksiyonu 3 parametre kullanır, complelely kafam karıştı

Bu kafa karıştırıcı ve büyülü! Bir numara oynuyoruz ve sırayla başlangıç değeri için bir sonuç vermeye uygulanan bir işlevi olan akü, değiştirin.

Graham Hutton yukarıdaki Madde foldr foldl açmak için hile açıklıyor. Tarafından foldl özyinelemeli bir tanım yazmaya başlıyoruz:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []       = v
foldl f v (x : xs) = foldl f (f v x) xs

Ve sonra statik değişken f dönüşüm yoluyla onu yeniden:

foldl :: (a -> b -> a) -> a -> [b] -> a    
foldl f v xs = g xs v
    where
        g []     v = v
        g (x:xs) v = g xs (f v x)

Hadi v içe doğru yüzer gibi şimdi g yeniden yazmak:

foldl f v xs = g xs v
    where
        g []     = \v -> v
        g (x:xs) = \v -> g xs (f v x)

Bir bağımsız değişken bir fonksiyonu olarak g düşünüp aynı şekilde, bir fonksiyon verir:

foldl f v xs = g xs v
    where
        g []     = id
        g (x:xs) = \v -> g xs (f v x)

Şimdi g, işe yaramayan bir liste yürüyen bir işlevi, bazı fonksiyon f uygulamak zorundayız. Son değer, kimlik işlevi vardır, ve her adımda bir fonksiyonu olarak oluşur.

Amaelinizin altında var zaten çok benzer bir özyinelemeli listeler foldr! fonksiyonu

Bu g fonksiyon çok benzer özyinelemeli bir düzen gibi görünüyor. Eldeki mevcut tüm büyü (nam-ı diğer Kuş, Meertens ve Malcolm) kullanarak özel bir kural geçerlidir . püf noktası: ^strong>kat evrensel özelliğilisteler işleyen bir fonksiyonu g için iki tanım, ifade arasında bir eşdeğerlik ki:,

Yani, kıvrımlar evrensel özelliği olan devletler

    g = foldr k v

g iki denklem eşdeğer olmalıdır, k v bazıları için:

    g []     = v
    g (x:xs) = k x (g xs)

Önceki foldl bizim tasarımlar v == id biliyoruz. İkinci denklem için, ihtiyacımız olsa içinhesaplayınk tanımı:

    g (x:xs)         = k x (g xs)        
<=> g (x:xs) v       = k x (g xs) v      -- accumulator of functions
<=> g xs (f v x)     = k x (g xs) v      -- definition of foldl
<=  g' (f v x)       = k x g' v          -- generalize (g xs) to g'
<=> k = \x g' -> (\a -> g' (f v x))      -- expand k. recursion captured in g'

Olan, k v sağladığı hesaplanan tanımları değiştirme foldl olarak: tanımı

foldl :: (a -> b -> a) -> a -> [b] -> a    
foldl f v xs =
    foldr
        (\x g -> (\a -> g (f v x)))
        id
        xs
        v

Özyinelemeli g yerine, foldr kombinatorik ve akümülatör olur bir işlevi yerleşik aracılığıyla bir zincir besteleri f her öğe listesinde, ters sırada (yani kat sol yerine sağ).

Bu kesinlikle biraz ileri, derinden bu dönüşümü anlamak içinkatlanabilir evrensel özelliğibu dönüşümü mümkün kılan,, Hutton öğretici, aşağıda bağlantısı öneririm.

Referanslar

• Haskell Wiki: foldr and foldr
• A tutorial on the universality and expressiveness of fold, J. Fonksiyonel Programlama 9 (4): Graham Hutton 355-372, Temmuz 1999.
• Malcolm, G. Algebraic data types and program transformation.), Doktora Tezi, Groningen Üniversitesi.