Haskell - найти путь к значению узлов

Question

Вопрос для этой проблемы:

Дерево содержит данные типа a.Функция findpath, которой даны функция f, некоторые данные x и дерево t, возвращает списки путей (возможно, пустых) в t узлам формы Node d, где fd равно x.

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

data Btree a = ND | Data a |  Branch (Btree a) (Btree a)
           deriving (Show,Eq)

data Dir = L | R 
       deriving (Show,Eq)

type Path =  [Dir]

Моя попытка решить эту функцию:

findpath :: Eq b => (a -> b) -> b -> Btree a -> [Path]
findpath f x (Data d)                = [[]]
findpath f x ND                      = [[]]
findpath f x (Branch (Data d) right) = [[L]] ++ (findpath f x right)
findpath f x (Branch left (Data d))  = [[R]] ++ (findpath f x left)

Данные, использованные для тестирования:

tree1 = Branch ND ND
tree2 = Branch ND (Data 3)
tree3 = Branch tree1 tree2

Вызов функции для проверки функции:

1. findpath (2*) 3 tree2
2. findpath (2*) 2 tree2
3. findpath (2*) 3 tree1

Выходные данные:

1. [[R],[]]
2. [[R],[]] - incorrect
3. Throws exception

Любая помощь по функции findpath будет высоко оценена,

Answer 1

Давайте рассмотрим все по одному случаю, используя точно случаи из определения данных Btree.То есть, поскольку

data Btree a = ND | Data a | Branch (Btree a) (Btree a)

, тогда мы рассмотрим ровно следующие формы деревьев, а не другие:

1. ND
2. Data d
3. Branch l r

Давайте начнем.

findpath f x ND = {- TODO -}

Напомним спецификацию:

Функция findpath, которой дана функция f,некоторые данные x и дерево t возвращают список путей (возможно, пустых) в t в узлы вида Data d, где fd равно x.

(я предположил, где вынаписал «Узел d», вы имели в виду «Данные d», чтобы выровнять с вашим определением деревьев, и изменили «списки» на «список».)

В текущем случае у нас есть f и x, как описано, и t = ND.Подставляя их в описание того, что мы должны вернуть, мы получаем:

список путей в ND к узлам формы Data d, где ...

Поскольку ND не содержит узлов вида Data d, таких путей нет.Итак:

findpath f x ND = []

Следующий случай:

findpath f x (Data d) = {- TODO -}

Теперь у нас есть t = Data d.Пересматривая спецификацию снова, мы должны вернуть

список путей в Data d к узлам формы Data d, где fd равен x.

Хорошону, тогда мы должны проверить, равен ли f d равен x или нет, хей?

findpath f x (Data d) = if f d == x
    then {- TODO -}
    else {- TODO -}

Если f d == x, то существует ровно один путь к узлу формы Data d, гдеfd равен x, а именно - пустой путь.Если нет f d == x, то таких путей нет.Итак:

findpath f x (Data d) = if f d == x
    then [[]]
    else []

И последний случай:

findpath f x (Branch l r) = {- TODO -}

Еще раз пересматривая спецификацию, теперь с t = Branch l r мы должны вернуть

список путей в Branch l r к узлам вида Data d, где fd равен x.

Теперь вы можете чувствовать себя немного застрявшими.В конце концов, l и r настолько общие, что трудно понять, есть ли в них пути к узлам формы Data d, верно?Так как же узнать, существует ли путь в Branch l r, который в конце концов заканчивается на узле Data d?Конечно, если бы был только способ узнать ответ на эти два подзапроса, возможно, мы могли бы расширить эти пути, а?

К счастью, у нас есть функция, которая отвечает на подзапрос: findpath сама.Итак, давайте ответим на подзапросы, а затем подумаем, что делать.

findpath f x (Branch l r) = {- TODO -} where
    pathsInL = findpath f x l
    pathsInR = findpath f x r

Хорошо, у нас есть несколько путей в дереве l, которые ведут к узлам вида Data d, где f xравно d (соответственно, некоторые пути в дереве r).Как мы можем преобразовать эти пути в пути в дереве Branch l r?Легко: добавив L (соответственно R) к каждому из путей.Затем мы можем объединить два набора путей вместе.

На этом этапе я перестану предоставлять код: я думаю, что ключ, пропускающий понимание для вас, уже должен быть выше в предоставленном рекурсивном скелете.Однако я предложу некоторые функции, которые могут оказаться полезными при выделении последних маленьких кусочков скелета:

1. (:) можно использовать для добавления нового Dir к Path.
2. map может использоваться для обновления функции, которая модифицирует один Path в функцию, которая изменяет весь список Path s.
3. (++) может использоваться дляобъединить два списка Path s, создав один список, в котором есть все элементы каждого из двух аргументов.

Дайте ему шанс, и дайте нам знать, где вы застряли в следующий раз!