mapa. skład funkcji foldra - Haskell

Question

Przejdźmy od razu do rzeczy.

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

Co to jest [[A1] -> a]? ja naprawdę staram się zrozumieć tę kompozycję, więc robię to:

-- 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) 
_________________________ 

Co się dzieje w tym momencie? Dziękuję Ci!

Answer 1

Aby odpowiedzieć na to pytanie, dobrze jest przypomnieć, co foldr i map do.

Im bardziej skomplikowana z dwóch jest foldr, który ma typ

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

liście, aby być złożony jest naprawdę łańcuch wagoników (:) i terminala pustej listy:

1 : 2 : 3 : [] 

działaniem z foldr ma zastąpić konstruktory : i [] z funkcją składania i wartością końcową, odpowiednio:

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

---

Funkcja map jest prostsza. Jednym ze sposobów myślenia o nim jest jak podjęcie funkcji oraz listę i zastosowanie funkcji do każdego argumentu listy:

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

Jednak można również pomyśleć o tym, jak przy funkcji i podnosząc ją do będzie funkcją, która działa na listach zamiast:

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

---

Co to znaczy komponować te dwie funkcje, map . foldr?Zauważ, że to jest właśnie zastosowanie funkcji jedna po drugiej - w szczególności

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

Ponieważ zastosowanie foldr pierwsze, musisz być zastosowanie go do funkcji f :: a -> b -> b i wrócić inną funkcję:

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

teraz stosuje map, który unosi funkcję do działania na listach:

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

Ten typ wygląda dziwnie, bu t to jest ważne. Teraz zamiast pojedynczej wartości terminalowej podajesz listę wartości końcowych i otrzymujesz listę funkcji składających z powrotem - jedną dla każdej podanej wartości terminalu.

---

Aby uczynić go bardziej zrozumiałym mogliśmy spojrzeć na konkretnej funkcji, (+), który ma wpisać

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

Jeśli podstawimy że do powyższego równania otrzymujemy

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

If teraz stosujemy go do listy [0, 1, 2] otrzymujemy listę trzech funkcji:

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

Możemy użyć idiomu map ($x), aby zastosować każdą z funkcji na liście do konkretnego argumentu. Musi to być lista liczb, a ja wybiorę [3,4,5]. Oglądaj uważnie:

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

Lista [3,4,5] został złożony trzy razy stosując (+) jako funkcji składanej i za każdym razem z inną wartością zacisk:

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

Gdy wartość końcowa jest 0, po prostu dostać suma wartości: 3 + 4 + 5 == 12. Gdy wartość końcowa to 1, otrzymamy o jeden więcej niż sumę wartości (13), a gdy wartość końcowa to 2, otrzymamy o dwa więcej niż suma wartości (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

Aby kontynuować w którym zostało przerwane, dwie definicje y musi być równa:

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

więc możemy stwierdzić, że:

a1 = b 
b1 = [a] -> b 

Skład funkcja została dostarczona dwa argumenty funkcji, więc wynikowy typ to po prostu:

x -> w 

Ale wiemy:

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

Więc, typ wynik to:

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

który jest przystający do:

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