История изменений

Что такое по сути foldr? Это замена n-арных конструкторов данных на n-арные функции.

Тип foldr для твоего дерева (использую твои обозначения):

foldr :: (a -> b -> b) -> b -> RoseTree a -> b
f :: a -> b -> b
acc :: b

Твоё дерево выглядит как

RoseTree a = RoseTree a (RoseTree a : RoseTree a : RoseTree a : ... : RoseTree a : [])

У нас три конструктора под замену: RoseTree, (:) и []. Заменять должны на подходящие по арности и типам функции. И в результате должен получиться тип b.

Очевидно, что конструктор RoseTree надо заменить на f. А вот дальше возникают сложности. Обозначим пока замену (:) как ?, а замену [] как ??

b = f a (RoseTree a ? RoseTree a ? RoseTree a ? ... ? RoseTree a ? ??)

Т.к. второй аргумент у f имеет тип b, значит ? должен возвращать тип b. И первым аргументом ? должен принимать тип RoseTree a. То есть

? :: RoseTree a -> c -> b

Тип c мы пока не знаем. Подумаем, на что мы можем заменить ??. Это нуль-арный конструктор, значит мы его должны заменить на какую-то константу. Константа у нас по сути одна, это acc.

Значит ?? = acc и ?? :: b. Отсюда моментально получаем, что c = b.

Значит

? :: RoseTree a -> b -> b

Только одна функция имеет такой тип, это flip (foldr f). Теперь мы готовы делать foldr:

b = f a (RoseTree a `flip (foldr f)` RoseTree a `flip (foldr f)` RoseTree a `flip (foldr f)` ... `flip (foldr f)` RoseTree a `flip (foldr f)` acc)

Осталось свернуть этот паровоз в скобках в обычный foldr (уже для списков! не для дерева), собственно и получаем

f x (foldr (flip (foldr f)) acc ts)

Что такое по сути foldr? Это замена n-арных конструкторов данных на n-арные функции.

Тип foldr для твоего дерева (использую твои обозначения):

foldr :: (a -> b -> b) -> b -> RoseTree a -> b
f :: a -> b -> b
acc :: b

Твоё дерево выглядит как

RoseTree a = RoseTree a (RoseTree a : RoseTree a : RoseTree a : ... : RoseTree a : [])

У нас три конструктора под замену: RoseTree, (:) и []. Заменять должны на подходящие по арности и типам функции. И в результате должен получиться тип b.

Очевидно, что конструктор RoseTree надо заменить на f. А вот дальше возникают сложности. Обозначим пока замену (:) как ?, а замену [] как ??

b = f a (RoseTree a ? RoseTree a ? RoseTree a ? ... ? RoseTree a ? ??)

Т.к. второй аргумент у f имеет тип b, значит ? должен возвращать тип b. И первым аргументом ? должен принимать тип RoseTree a. То есть

? :: RoseTree a -> c -> b

Тип c мы пока не знаем. Подумаем, на что мы можем заменить ??. Это нуль-арный конструктор, значит мы его должны заменить на какую-то константу. Константа у нас по сути одна, это acc.

Значит ?? = acc и ?? :: b. Отсюда моментально получаем, что c = b.

Значит

? :: RoseTree a -> b -> b

Только одна функция имеет такой тип, это flip (foldr f). Теперь мы готовы делать foldr:

b = f a (RoseTree a `flip (foldr f)` RoseTree a `flip (foldr f)` RoseTree a `flip (foldr f)` ... `flip (foldr f)` RoseTree a `flip (foldr f)` acc)

Осталось свернуть этот паровоз в скобках в обычный foldr (уже для списков! не для дерева), собственно и получаем

f x (foldr (flip (foldr f)) acc ts)