Karte. foldr function composition - Haskell

Question

Also, lass uns gleich auf den Punkt kommen.

:t (map.foldr) 
(map.foldr) :: (a1 -> a -> a) -> [a] -> [[a1] -> a] 

Was ist [[a1] -> a]? Ich versuche wirklich diese Komposition zu verstehen, so dass ich das tue:

-- map.foldr 

    map.foldr :: (a1 -> a -> a) -> [a] -> [[a1] -> a] 

    map :: (a1 -> b1) -> [a1] -> [b1] 
    (.) :: (y -> w) -> (x -> y) -> x -> w 
    foldr :: (a -> b -> b) -> b -> [a] -> b 

    y = (a1 -> b1)  w = ([a1] -> [b1]) 
    x = (a -> b -> b) y = (b -> [a] -> b) 

    y = (a1 -> b1) 
    y = (b -> [a] -> b) 
_________________________ 

Was in diesem Punkt geschieht? Vielen Dank!

Answer 1

Um diese Frage zu beantworten, ist es gut, daran zu erinnern, was foldr und map tun.

Je komplizierter der beiden ist foldr, die

--    list to be folded 
--        v 
foldr :: (a -> b -> b) -> b -> [a] -> b 
--   ^  ^
--folding function  terminal value 

Die Liste hat geben gefaltet zu werden ist wirklich eine Kette von conses (:) und einem Terminal leere Liste:

1 : 2 : 3 : [] 

Die Aktion von foldr ist die Ersetzung der : und [] Konstruktoren mit der faltenden Funktion und der Terminal-Wert, bzw.:

foldr (+) 0 (1 : 2 : 3 : []) == 1 + 2 + 3 + 0 

---

Die map Funktion ist einfacher. Eine Denkweise ist es als eine Funktion zu nehmen und eine Liste, und Anwendung der Funktion auf jedes Argument der Liste:

map :: (a -> b) -> [a] -> [b] 
--  ^  ^
-- function   list 

Sie können aber auch daran denken, wie eine Funktion nehmen und heben es an eine Funktion, die stattdessen auf Listen wirkt:

map :: (a -> b) -> ([a] -> [b]) 
--  ^   ^
-- function    function on lists 

---

Was bedeutet es, diese beiden Funktionen zu komponieren, map . foldr?Beachten Sie, dass dies nur die Funktionen der Anwendung einer nach dem anderen - insbesondere

(map . foldr) f == map (foldr f) 

Da Sie gelten foldr zuerst, müssen Sie es auf eine Funktion f :: a -> b -> b anwenden, und Sie eine andere Funktion zurück:

foldr f :: b -> [a] -> b 
--  ^ ^
--terminal val list to be folded 

Nun wenden Sie map, die die Funktion auf Listen handeln Lifte:

map (foldr f) :: [b] -> [[a] -> b] 
--    ^  ^
--list of terminal vals  functions that fold lists 

Diese Art ungerade sieht, bu t es ist gültig. Anstelle eines einzelnen Terminalwertes geben Sie ihm eine Liste der Terminalwerte, und Sie erhalten eine Liste der Falzfunktionen zurück - eine für jeden Terminalwert, den Sie geliefert haben.

---

Um es klarer wir an einer bestimmten Funktion aussehen könnte, (+), die

(+) :: Num a => a -> a -> a 

Wenn wir das in der obigen Gleichung ersetzen geben hat, wir

(map . foldr) (+) :: Num a => [a] -> [[a] -> a] 
--       ^  ^
--   list of terminal vals   functions that fold lists 

bekommen Wenn Wir wenden es jetzt auf die Liste [0, 1, 2] an. Wir erhalten eine Liste von drei Funktionen:

(map . foldr) (+) [0,1,2] :: Num a => [[a] -> a] 

Wir können das map ($x) Idiom verwenden, um jede der Funktionen in der Liste auf ein bestimmtes Argument anzuwenden. Es muss eine Liste von Zahlen sein, und ich wähle [3,4,5]. Achten Sie sorgfältig:

> map ($[3,4,5]) ((map.foldr) (+) [0,1,2]) 
[12, 13, 14] 

Die Liste [3,4,5] dreimal gefaltet wurde (+) als Klappfunktion, und jedes Mal mit einem anderen Terminal-Wert mit:

3 + 4 + 5 + 0 == 12 
3 + 4 + 5 + 1 == 13 
3 + 4 + 5 + 2 == 14 

Wenn der Endwert 0 ist, bekommen wir einfach die Summe der Werte: 3 + 4 + 5 == 12. Wenn der Terminal-Wert 1 ist, erhalten wir 1 mehr als die Summe der Werte (13) und wenn der Terminal-Wert 2 ist, erhalten wir zwei mehr als die Summe der Werte (14).

Answer 2

map.foldr :: (a1 -> a -> a) -> [a] -> [[a1] -> a] 

map :: (a1 -> b1) -> [a1] -> [b1] 
(.) :: (y -> w) -> (x -> y) -> x -> w 
foldr :: (a -> b -> b) -> b -> [a] -> b 

-- if you substitute: x = (a -> b -> b) y = (b -> [a] -> b) 
-- then you get for map :: (b -> ([a] -> b)) -> [b] -> [[a] -> b] 
-- so if composition operator applied: 
map . foldr :: (a -> b -> b) -> [b] -> [[a] -> b] 

Answer 3

Um fortzufahren, wo Sie die beiden Definitionen von y aufhörte, gleich sein müssen:

y = (a1 -> b1) = (b -> [a] -> b) 
       = (b -> ([a] -> b)) 

so können wir schließen, dass:

a1 = b 
b1 = [a] -> b 

Die Funktion Zusammensetzung wurde zwei geliefert hat Funktionsargumente, so ist der resultierende Typ nur:

x -> w 

Aber wir wissen:

x = a -> b -> b 
w = [a1] -> [b1] = [b] -> [[a] -> b] 

also der Ergebnistyp ist:

(x -> w) = ((a -> b -> b) -> ([b] -> [[a] -> b])) 
     = (a -> b -> b) -> [b] -> [[a] -> b] 

, die deckungsgleich ist:

(a1 -> a -> a) -> [a] -> [[a1] -> a]