Вариации складок на деревьях Хаскелла

Question

Учитывая дерево, определенное как:

data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Eq, Show)

Я хочу использовать функцию:

foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree _ b Leaf         = b
foldTree f b (Node lt x rt) = f (foldTree f b lt) x (foldTree f b rt)

Чтобы иметь возможность создавать эквиваленты нормальных foldr и foldl as:

foldTreeR :: (a -> b -> b) -> b -> Tree a -> b
foldTreeL :: (b -> a -> b) -> b -> Tree a -> b

Я думал, что это будет довольно просто, поскольку их определения в точности повторяют определения foldr и foldl.Я предполагал, что все, что мне нужно сделать, это подключить значения аналогичным образом аналогичным образом, чтобы я написал анонимную функцию, аккумулятор с базовым состоянием моего дерева и дерево, которое необходимо обработать.Лямбда-функция должна варьироваться в зависимости от типа выполняемого сгиба.

Вот что я придумал:

foldTreeR :: (a -> b -> b) -> b -> Tree a -> b
foldTreeR f acc t =  foldTree (\x acc -> f x acc) acc t

Я получаю ошибку:

Couldn't match type ‘a’ with ‘a -> b’ 
      ‘a’ is a rigid type variable bound by
        the type signature for:
          foldTreeR :: forall a b. (a -> b -> b) -> b -> Tree a -> b
        at Folds.hs:294:14
      Expected type: Tree (a -> b)
        Actual type: Tree a

Я не совсем уверен, как мне пройти в исходном дереве в этом случае.

Похоже, что левый сгиб будет просто вариацией того же значения, причем значения в лямбда-функции переупорядочены, а также оценены по-разному.

Может кто-нибудь помочь мне понять, как решение можетдобраться сюда?

Answer 1

Вот как вы могли бы придумать решение самостоятельно.

У нас есть

data Tree a =                               Leaf 
            | Node (Tree a) a (Tree a)                   deriving (Eq, Show)

foldTree :: (        b ->   a ->   b -> b) -> b -> Tree a -> b

foldTree    (g :: b ->   a ->   b -> b) (z :: b) :: Tree a -> b

Итак, учитывая g и z, эта функция превращает значение Tree a взначение b, превратив поддеревья t в b s и объединив их с a дерева, через g.

Можем ли мы map над этими деревьями, используя foldTree?Да:

mapTree :: (a -> c) -> Tree a -> Tree c
mapTree f t = foldTree g z t
  where
  -- we need to create a Node with the mapped element inside it
  -- already having the transformed sub-trees. Well, 
  -- creating Tree values is the job of that type's data constructors:
  g lt a rt = Node lt (f a) rt      -- f is applied to the element `a`
  -- and all leaves are transformed into the same value, which is:
  z = Leaf

Так что теперь у нас есть mapTree (f :: a -> c) :: Tree a -> Tree c.Как это поможет нам?

Что мы хотим?Мы хотим

foldTreeR :: (a -> b -> b) -> b -> Tree a -> b
-- i.e.
foldTreeR (cons :: a -> r -> r) (nil :: r) :: Tree a -> r

Итак, у нас есть cons, такое что cons (x :: a) :: r -> r.

Что если мы отобразим это cons поверх Дерева?Тип a -> r -> r на самом деле a -> (r -> r), и мы действительно только что увидели, что cons превращает (x :: a) в r -> r ( читайте его: превращает значение x или тип a в значениетипа r -> r):

mapTree (cons :: a -> r -> r) :: Tree a -> Tree (r -> r)

Зачем нам , что ?Что мы можем сделать со всеми этими r -> r функциями, которые мы теперь имеем в узлах дерева?Ну, мы можем превратить дерево в список значений в его узлах, с помощью обратного порядка:

inorder :: Tree d -> [d]
inorder t = foldTree (\l a r -> l ++ a : r) [] t

, чтобы мы могли иметь

inorder . mapTree (cons :: a -> r -> r) :: [r -> r]
          -----------------
          Tree a -> Tree (r -> r)
--------
Tree (r->r) -> [r->r]

и мы можем составьте все эти функции внутри этого списка, линейно , чтобы организовать операцию передачи результата справа налево, которая равна ... rightСвернуть!

foldTreeR_ :: (a -> r -> r) -> r -> Tree a -> r
foldTreeR_ cons z t = foldr ($) z (inorder $ mapTree cons t)
           -- or, equivalently,
           --         foldr (.) id (inorder $ mapTree cons t) z

Вот и все.

Если мы встроим все и упростим получающиеся определения, мы получим одно в другом ответе.

То же самое длялевый складной.Попробуй.

Answer 2

Мы можем восстановить линейные сгибы, проходящие через аккумулятор, из сгибов в форме дерева, следующих за типом данных, сложив в endofunctions , например:

data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Eq, Show)

-- foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b

foldTreeR :: (a -> r -> r) -> r -> Tree a -> r
foldTreeR cons z t = foldTree g id t z           -- b ~ r -> r
  where
  g lt a rt = lt . cons a . rt 

И левый сгиб:

foldTreeL :: (acc -> a -> acc) -> acc -> Tree a -> acc
foldTreeL conj z t = foldTree g id t z           -- b ~ acc -> acc
  where
  g lt a rt = rt . flip conj a . lt

---

Более подробные объяснения:

И cons a, и flip conj a имеют тип r -> r (или acc -> acc, что совпадает).Это тип функций с одинаковым типом аргумента и результата.

Такие функции известны как эндофункции, endo , указывающие на одинаковость их домена и кодомена (типы справа и слева от стрелки).Как таковые, они составляют легко: могут участвовать в операции (.), то есть в композиции функций, в результате чего композиция имеет тот же тип, что и типы операндов:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)

-- and for endofunctions,
-- ((f :: r -> r) . (g :: r -> r)) :: r -> r

Длядерево с обходом в порядке [a,b,c,...,n], правая складка превращает это дерево в композицию

(cons a . cons b . cons c . ..... . cons n) z

-- which is the same as
-- cons a (cons b (cons c ... (cons n z) ... ))

, а левая складка превращает его в

(conj' n . ..... . conj' c . conj' b . conj' a) z

, где

conj' a acc = flip conj a acc = conj acc a     -- by definition of `flip`

-- so the above composition chain is the same as
-- conj (... (conj (conj (conj z a) b) c) ...) n

с некоторыми id s, разбросанными по этой цепочке, каждый Leaf превращается в id, не влияя на всю цепочку, потому что

(id . f) x = id (f x) = f x = f (id x) = (f . id) x

так

id . f = f = f . id

т.е. id, служащий нулевым элементом по отношению к операции компоновки функции, точно так же, как 0 делает с операцией + (это, кстати, упоминается как 'моноид' , образованный . и id или 0 и +).

---

Вот как мы создали бы этот упорядоченный обходсписок для дерева:

inorder :: Tree a -> [a]
inorder t = foldTree g [] t
  where
  g lt a rt = lt ++ [a] ++ rt

Таким образом, список [a,b,...,n] фактически создается как

[] ++ [a] ++ [] ++ [b] ++ [] ++ ... ++ [n] ++ []

и правый сгиб oЕсли это дерево будет создано как

(id . cons a . id . cons b . id . .... . cons n . id) z