Учитывая функциональную структуру данных (в данном случае, дерево), обычно есть две основные вещи, которые вы можете сделать с ней:
- map
- fold
При сопоставлении вы берете функцию f :: a -> b и структуру origTree :: Tree a и применяете функцию к элементам структуры, в результате чего получается newTree :: Tree b.(Обратите внимание, что канонический способ сделать структуру сопоставимой - это сделать ее Functor и определить fmap)
Складывание - это то, где вы каким-то образом соединяете все элементы структуры вкакое-то новое значение.Когда вы сказали, что у вас есть функция Tree и (+), я сразу подумал о складывании: суммировании всех элементов в дереве.(Обратите внимание, что канонический способ сделать структуру складной - это сделать ее экземпляром Foldable (сюрприз!) И определить foldMap или foldr)
Однако, похоже, ваша домашняя задача состоит в том, чтобыопределите функцию отображения для вашего дерева.
Теперь, касаясь вашего собственного вопроса, превращаем функцию в дерево.Немного неясно, что именно вы подразумеваете под «a», «1031» и «1032» в своем дереве, но давайте немного поиграем с идеей.Ради простоты я не собираюсь делать полностью общую функцию.Кроме того, поскольку ваши функции "деревья" довольно однобокие, я называю их FunHistory вместо Tree.Это будет представлять историю приложений функций.
data FunHistory a b = Result b (FunHistory a b)
| Application (a -> FunHistory a b) a (FunHistory a b)
| Base (a -> FunHistory a b)
Теперь этот тип немного странный.Result содержит результат типа b, а также ссылку на предыдущую историю приложений функций.Base содержит функцию с историей приложений функций и возможностью создания будущей истории, если задано значение типа a.Application, следовательно, является промежуточной записью, которая предоставляет возможность создания будущей истории, а также отмечает прошлую историю и какое значение было применено к этой прошлой истории.
Теперь давайте сделаем некоторые функциидля удобства.Пристегните ремень безопасности, это может стать ухабистым.
mkHist :: (a -> b) -> FunHistory a b
mkHist f = let h = Base (\x -> Result (f x) h) in h
Используя функцию с одним аргументом, мы можем создать из нее историю ... магией.Этот специфический вкус магии называется «лень» и «рекурсивное разрешение».
Давайте продолжим и создадим функцию, которая будет принимать FunHistory и входное значение, и перемещать историю дальше.К сожалению, это не полная функция;он не определен для Result типа FunHistory.
-- The caller should make sure it isn't a `Result` type before using this function
app :: a -> FunHistory a b -> FunHistory a b
app x (Result _ _) = undefined
app x (Application f _ _) = f x
app x (Base f) = f x
Это прекрасно и просто для функций с одним аргументом, но промежуточный конструктор Application никогда не требуется для таких простых случаев.Давайте попробуем создать смарт-конструктор для функции с двумя аргументами:
mkHist2 :: (a -> a -> b) -> FunHistory a b
mkHist2 f = let h = Base (\x -> mkHist' f x h)
in h
mkHist' f x h = let h' = Application (\y -> Result (f x y) h') x h
in h'
Давайте попробуем это сейчас для функции с тремя аргументами:
mkHist3 :: (a -> a -> a -> b) -> FunHistory a b
mkHist3 f = let h = Base (\x -> mkHist2' f x h)
in h
mkHist2' f x h = let h' = Application (\y -> mkHist' (f x) y h') x h
in h'
Теперь функция с 4 аргументами:
mkHist4 :: (a -> a -> a -> b) -> FunHistory a b
mkHist4 f = let h = Base (\x -> mkHist3' f x h)
in h
mkHist3' f x h = let h' = Application (\y -> mkHist2' (f x) y h') x h
in h'
Хорошо, посмотрите на это;эти функции выглядят почти так же, как mkHist3 и mkHist2' соответственно!Следующим шагом здесь будет обобщение этих функций в класс типов, чтобы он масштабировался до функций с произвольным числом входов.Подвох в том, что все входы должны иметь одинаковый тип.
[предупреждение: этот код не проверен, но я несколько уверен, что он в основном корректен ... ish]
instance (Show a, Show b) => Show (FunHistory a b) where
show (Base _) = "base"
show (Application _ x h) = "app " ++ show x ++ ", " ++ show h
show (Result r h) = "result: " ++ r ++ ", " ++ show h