Что ж, мы можем прокомментировать тип Churchlist таким образом, чтобы прояснить его:
-- Tell me...
type Churchlist t u = (t -> u -> u) -- ...how to handle a pair
-> u -- ...and how to handle an empty list
-> u -- ...and then I'll transform a list into
-- the type you want
Обратите внимание, что это тесно связано с функцией foldr
:
foldr :: (t -> u -> u) -> u -> [t] -> u
foldr k z [] = z
foldr k z (x:xs) = k x (foldr k z xs)
foldr
— это очень общая функция, которая может реализовывать все виды других функций списка. Тривиальный пример, который поможет вам, реализует копию списка с foldr
:
copyList :: [t] -> [t]
copyList xs = foldr (:) [] xs
Используя закомментированный выше тип, foldr (:) []
означает следующее: «если вы видите пустой список, верните пустой список, а если вы видите пару, верните head:tailResult
».
Используя Churchlist
, вы можете легко написать аналог следующим образом:
-- Note that the definitions of nil and cons mirror the two foldr equations!
nil :: Churchlist t u
nil = \k z -> z
cons :: t -> Churchlist t u -> Churchlist t u
cons x xs = \k z -> k x (xs k z)
copyChurchlist :: ChurchList t u -> Churchlist t u
copyChurchlist xs = xs cons nil
Теперь, чтобы реализовать map
, вам просто нужно заменить cons
подходящей функцией, например:
map :: (a -> b) -> [a] -> [b]
map f xs = foldr (\x xs' -> f x:xs') [] xs
Отображение похоже на копирование списка, за исключением того, что вместо того, чтобы просто копировать элементы дословно, вы применяете f
к каждому из них.
Внимательно изучите все это, и вы сможете написать mapChurchlist :: (t -> t') -> Churchlist t u -> Churchlist t' u
самостоятельно.
Дополнительное упражнение (простое): запишите эти функции списка в терминах foldr
и напишите аналоги для Churchlist
:
filter :: (a -> Bool) -> [a] -> [a]
append :: [a] -> [a] -> [a]
-- Return first element of list that satisfies predicate, or Nothing
find :: (a -> Bool) -> [a] -> Maybe a
Если вам хочется заняться чем-нибудь посложнее, попробуйте написать tail
вместо Churchlist
. (Начните с написания tail
вместо [a]
, используя foldr
.)
person
Luis Casillas
schedule
17.09.2012