А что насчет "фолдтри" Джона Хьюза, я что-то не так понял?

Джон Хьюз в своей знаменитой статье под названием Почему функциональное программирование имеет значение, описывает типы данных для списков и упорядоченных помеченных деревьев , 

listof * ::= Nil | Cons * (listof *)
treeof * ::= Node * (listof (treeof *))

И функция под названием foldtree, 

foldtree f g a (Node label subtrees) =
         f label (foldtree f g a subtrees)

foldtree f g a (Cons subtree rest) =
         g (foldtree f g a subtree) (foldtree f g a rest)

foldtree f g a Nil = a

Я реализовал эти два типа данных в Haskell и в настоящее время пытаюсь реализовать foldtree, 

data Listof a = Nil | Cons a (Listof a)
    deriving (Read, Show, Eq)

-- implementation of some list functions... (skipped)

data Treeof a = Node a (Listof (Treeof a))
    deriving (Read, Show, Eq)

foldtree f g a (Node label subtrees) = f label (foldtree f g a subtrees)
foldtree f g a (Cons subtree rest)   = g (foldtree f g a subtree) (foldtree f g a rest)
foldtree f g a Nil                   = a

Но я получаю несоответствия типов: 

Couldn't match expected type ‘Treeof t’
            with actual type ‘Listof (Treeof t)’
Relevant bindings include
  subtrees :: Listof (Treeof t) (bound at whyFunMatters.hs:27:28)
  label :: t (bound at whyFunMatters.hs:27:22)
  f :: t -> t1 -> t1 (bound at whyFunMatters.hs:27:10)
  foldtree :: (t -> t1 -> t1)
              -> (t1 -> t1 -> t1) -> t1 -> Treeof t -> t1
    (bound at whyFunMatters.hs:27:1)
In the fourth argument of ‘foldtree’, namely ‘subtrees’
In the second argument of ‘f’, namely ‘(foldtree f g a subtrees)’

(и т. д.)

Подумав еще немного что касается реализации Hughes (псевдо) foldtree, я не уверен, что понимаю ее, и эти несоответствия типов теперь кажутся мне очевидными. Более конкретно, тип четвертого аргумента foldtree не кажется последовательным по трем шаблонам:

  • в первом шаблоне этот аргумент имеет тип Treeof a, тогда как
    • В последних двух паттернах он имеет тип Listof (Treeof a).

Что я упускаю?

2 7
haskell algebraic-data-types

2 ответа:

Правильное определение должно состоять из пары взаимно рекурсивных функций, одна для сворачивания деревьев и одна для сворачивания лесов (списков деревьев): 

foldtree :: (a -> c -> b) -> (b -> c -> c) -> c -> Treeof a -> b
foldtree f g a (Node label subtrees) = f label (foldforest f g a subtrees)

foldforest :: (a -> c -> b) -> (b -> c -> c) -> c -> Listof (Treeof a) -> c
foldforest f g a (Cons subtree rest) = g (foldtree f g a subtree) (foldforest f g a rest)
foldforest f g a Nil                 = a
Я думаю, что автор ошибочно объединил две различные (но тесно связанные) функции вместе. Я подозреваю, что то, что написал автор, на самом деле не Хаскелл, а скорее псевдокод Хаскелла, поэтому код был просто использован для представления алгоритма неофициальным способом.

Обратите внимание, что статья, по-видимому, предположим, что это Миранда, предшественница Хаскелла,но я не могу подтвердить, что это законный код Миранды.

7

Ответ Раффлвинда-самый очевидный способ исправить сомнительное определение foldtree из знаменитой статьи Хьюза. Однако существует гораздо более лаконичное и модульное решение, требующее только одной строки кода и повторного использования foldr. Прокрутите страницу до конца этого поста, чтобы увидеть это определение. Продолжайте читать для какого-то вывода определения.

Сравните определение Раффлвинда foldforest: 

foldforest f g a (Cons subtree rest) = g (foldtree f g a subtree) (foldforest f g a rest)
foldforest f g a Nil                 = a

...с помощью Хьюзовского (слегка измененного) определения foldr из бумага: 

foldr f a (Cons e rest)              = f e (foldr f a rest)
foldr f a Nil                        = a
Разве они оба не выглядят ужасно похожими? На самом деле единственная разница заключается в том, что в foldforest мы применяем foldtree f g a к subtree и (через рекурсию) ко всем другим элементам в списке поддеревьев перед их "слиянием" с g. Можем ли мы определить оператор, который делает это и может быть передан в foldr? Давайте более подробно рассмотрим ядро foldforest, где фактически выполняется работа: g (foldtree f g a subtree). Используя композицию функций (определенную в статье Хьюза как (f . g) h = f (g h)), мы можем выразить это часть по-другому: 
foldforest f g a (Cons subtree rest) = (g . foldtree f g a) subtree (foldforest f g a rest)
Теперь давайте для краткости определим h = (g . foldtree f g a) и передадим конкретный список поддеревьев в foldforest, разворачивая рекурсию с помощью нашей новой нотации: 
foldforest f g a (Cons subtree1 (Cons subtree2 Nil)) 
                                     = h subtree1 (h subtree2 a)

Как это выглядит, чтобы развернуть рекурсию аналогичного вызова foldr?

foldr f a (Cons subtree1 (Cons subtree2 Nil))
                                     = f subtree1 (f subtree2 a)
Теперь очевидно, что мы смогли извлечь оператор из foldforest , который мы можем передать в foldr вместе с начальным состоянием a и списком Treeof s. полное определение foldtree, максимизирующее модульность и краткость, следовательно, должна быть: 
foldtree f g a (Node label subtrees) = f label (foldr (g . foldtree f g a) a subtrees)
1