Попытка сгладить дерево в Хаскеле с помощью упорядоченного обхода

Question

Попытка использовать данную функцию сгиба для выравнивания дерева в списке.

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

Вот что я пытался сделать до сих пор:

treeToList :: Tree a -> [a]
treeToList = treeFold (\xs x ys -> xs ++ x : ys) (\x -> [x])

По какой-то причинеЯ не могу полностью обернуть голову, как это сделать?Чувствую, что есть что-то, что я не совсем понял о Хаскеле.Любая помощь будет оценена вместе с тем, как ее решить.Спасибо!

Редактировать:

Я понимаю, что сигнатура типа, которую я здесь использую, граничит с бессмысленным.В сигнатуре типа treeFold, основываясь на том, что я могу думать, вторым аргументом (b), вероятно, является список, так как в этом случае он действует как накопитель.Это сделало бы третий аргумент (Tree a) некоторой версией аргумента слева от уравнения.Два аргумента внутри функции должны быть левым и правым поддеревьями в узле.Третий аргумент - это просто значение узла.Внутри функции мне нужно объединить левое дерево, правое дерево и значение в обычном порядке, но все различные варианты, которые я пробовал, имели некоторые проблемы

Answer 1

Типы должны соответствовать:

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

treeToList = treeFold (\xs   x    ys -> xs ++ (x : ys))    z
-------------------------------------------------------------------
                        b    a    b     b      a   b       b
                                              --------
                                              b

Поскольку x и ys участвуют в одном и том же :, их типы должны быть совместимы:

(:) ::   a  -> [a]  ->  [a]
x   ::   a
ys  ::          b
-------------------
              b ~ [a]

Таким образом, мыиметь

treeFold ::           ( [a] -> a -> [a] -> [a]           ) -> [a] -> Tree a->[a]

treeToList = treeFold (\ xs    x    ys  -> xs ++ (x : ys))     z
-------------------------------------------------------------------
                         [a]   a    [a]    [a]    a   [a]     [a]
                                                 --------
                                                 [a]

Вывод: последний аргумент z должен иметь тип [a].

Что означает этот аргумент?Как обычно в случае сгибов, каждый «вариант» в определении типа данных имеет соответствующий аргумент для функции сгиба.

Ваше (отсутствующее) определение типа данных:

data Tree a = Node (Tree a)    a   (Tree a)       | Leaf

итип сгиба

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

, что соответствует " рекурсивным результатам типу хранения"

data TreeF a r = NodeF  r      a      r           | LeafF

Таким образом z - это значение для преобразования каждогоLeaf до ".

Самый естественный выбор для него это просто [].На самом деле, единственный выбор, потому что мы ничего не знаем о типе a (в [a]).

Answer 2

Тип treeFold равен

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

Вы хотите вернуть список значений, [a].

Поэтому тип результата b должен быть равен [a], что дает нам сигнатуру специализированного типа

treeFold :: ([a] -> a -> [a] -> [a]) -> [a] -> Tree a -> [a]

Обратите внимание, что второй аргумент имеет тип [a].

Какое значение вы вместо этого передаете?