Многие катаморфизмы кажутся достаточно простыми, в основном заменяя каждый конструктор данных на пользовательскую функцию, например
data Bool = False | True
foldBool :: r -- False constructor
-> r -- True constructor
-> Bool -> r
data Maybe a = Nothing | Just a
foldMaybe :: b -- Nothing constructor
-> (a -> b) -- Just constructor
-> Maybe a -> b
data List a = Empty | Cons a (List a)
foldList :: b -- Empty constructor
-> (a -> b -> b) -- Cons constructor
-> List a -> b
Однако для меня неясно, что происходит, если используется тот же конструктор типов, но с другим аргументом типа. Например. вместо передачи List a
до Cons
, а что насчет
data List a = Empty | Cons a (List (a,a))
Или, может быть, более сумасшедший случай:
data List a = Empty | Cons a (List (List a))
foldList :: b -- Empty constructor
-> ??? -- Cons constructor
-> List a -> b
Две правдоподобные идеи для части ???
- это
-
(a -> b -> b)
, то есть заменяя все приложения конструктораList
рекурсивно) -
(a -> List b -> b)
, т.е. просто заменить все приложенияList a
.
Какое из двух будет правильным - и почему? Или это будет совсем другое?