Haskell: foldr vs foldr1

Question

Jeśli mam tej funkcji insert:

insert x []  = [x] 
insert x (h:t) 
    | x <= h  = x:(h:t) 
    | otherwise = h:(insert x t) 

To daje posortowaną listę:

foldr insert [] [1,19,-2,7,43] 

ale tym:

foldr1 insert [1,19,-2,7,43] 

produkuje 'nie można skonstruować nieskończony typ: a0 = [a0] '

Jestem zdezorientowany tym, dlaczego drugie połączenie nie działa.

Przyjrzałem się definicjom zarówno dla i foldr1 i śledziłem oba z prostymi funkcjami arytmetycznymi, ale wciąż nie mogę wymyślić jasnego wyjaśnienia, dlaczego drugie połączenie nie działa.

Answer 1

Ponieważ foldr1 próbuje to zrobić:

insert 43 -7 

który zakończy się niepowodzeniem.

Answer 2

Typ foldr1 to (a -> a -> a) -> [a] -> a, tj. Argumenty i wyniki tej funkcji mają ten sam typ. Jednak insert ma typ Ord a => a -> [a] -> [a]. Dla foldr1 insert jest dobrze wpisany, a i [a] musi być tego samego typu.

Ale to oznaczałoby, że a == [a] == [[a]] == [[[a]]] == ..., tj. a jest typem nieskończenie wielu list.

Answer 3

Spójrzmy na niektóre rodzaje podpisów.

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr1 :: (a -> a -> a) ->  [a] -> a 

W obu przypadkach pierwszy argument jest funkcją dwóch argumentów.

• dla foldr1, te dwa argumenty muszą mieć ten sam typ (a wynik ma tego typu także)
• dla foldr, te dwa argumenty mogą mieć różne typy (a rezultat ten sam typ jako drugi argument)

Jaki jest twój typ insert?

Answer 4

Problem jest następujący:

foldr byłoby zrobić w ten sposób:

1. zestaw wyników do insert 43 []
2. wyniku ustawiony insert 7 result
3. i tak dalej

to wyraźnie Prace.

Zważywszy foldr1 byłoby spróbować wykonać następujące czynności:

1. zestaw wyników do insert 7 43
2. wyniku ustawiony insert -2 result
3. itp

który jest zdecydowanie nie tak. Możesz zobaczyć, foldr1 wymaga, aby argumenty dla operacji były tego samego typu, co nie jest w przypadku insert.

Answer 5

Podobają mi się tutaj podane odpowiedzi na pytania o typ, ale chciałbym też podać opis operacyjny, wyjaśniający, dlaczego nie chcemy tego do kontroli typu. Weźmy źródło foldr1 zacząć:

foldr1   :: (a -> a -> a) -> [a] -> a 
foldr1 _ [x] = x 
foldr1 f (x:xs) = f x (foldr1 f xs) 

Teraz spróbujmy uruchomić program.

foldr1 insert [1,19,-2,7,43] 
= { list syntax } 
foldr1 insert (1:[19,-2,7,43]) 
= { definition of foldr1 } 
insert 1 (foldr1 insert [19,-2,7,43]) 
= { three copies of the above two steps } 
insert 1 (insert 19 (insert (-2) (insert 7 (foldr1 insert [43])))) 
= { definition of foldr1 } 
insert 1 (insert 19 (insert (-2) (insert 7 43))) 

... whoops! To insert 7 43 nigdy nie zadziała. =)