Создание дерева по заданному пути списка строк в f # - PullRequest
Новая
       22

Создание дерева по заданному пути списка строк в f #

0 голосов
/ 23 ноября 2018

У меня есть определение типа: 

type FsTree = Node of (string * FsTree) list

Я создаю пустой узел: 

let createEmptyFsTree () : FsTree = Node[]

Я хотел бы построить дерево из пути списка строк, например:

let fs1 = create ["MainNode";"nodeA";"nodeB"] (createEmptyFsTree())
let fs2 = create ["MainNode";"nodeC";"nodeD"] fs1
let fs3 = create ["MainNode";"nodeC";"nodeE"] fs2

Результат будет: 

Node [("MainNode", Node [

                             ("nodeA", Node [("nodeB", Node [])]);
                             ("nodeC", Node [
                                         ("nodeD", Node[]);
                                         ("nodeE", Node[])])])]

Это мой код до сих пор.Я застрял на 2 дня.Пожалуйста, помогите. 

let create (p : string list) (fs : FsTree) =
        let rec create (p : string list) (fs : FsTree) =
            match fs with 
            | Node n -> match p, n with
                        | h :: t, (name, rsNode) :: rsTree when name = h -> Node([(h, (create t rsNode))] @ rsTree)
                        | _, lNode :: rsTree -> Node([lNode]@rsTree)
                        | h :: t, [] -> Node ([h, (create t (createEmptyFsTree()))])
                        | [],[] -> Node[]
        create p fs

Я могу создать дерево только с первого пройденного пути: 

Node [("MainNode", Node [("nodeA", Node [("nodeB", Node [])])])]

1 Ответ

0 голосов
/ 23 ноября 2018

Сложность этой проблемы заключается в том, что существует несколько структур (путь - list, каждый узел - list и поддерево), которые необходимо пройти рекурсивно в одно и то же время, чтобы он работал,Делать это в одной функции становится очень трудно.

Вот почему мне нравится упрощать проблему, разбивая ее на более мелкие части.Здесь мы собираемся использовать 2 взаимно рекурсивных функции (обратите внимание на синтаксис).Сначала я собираюсь переименовать функции, чтобы лучше понять, что они делают.Я также избегаю повторять одно и то же имя для функций и переменных, поскольку это сбивает с толку.Моя первая функция будет иметь дело только с обходом пути p: 

let rec addPath (p : string list)   (Node ns) =
    match p with
    | []       -> Node                    ns
    | hp :: tp -> Node (addHeadPath hp tp ns)

Я использую сопоставление с шаблоном по второму параметру (Node ns), чтобы получить список подузлов, потому что следующая функция будет проходить через этоlist.

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

and addHeadPath hp tp ns =
    match ns with
    | []                          -> [hp, addPath tp (Node[]) ]
    | (nn, st) :: tn when nn = hp -> (nn, addPath tp st       ) ::                   tn
    | hn       :: tn              -> hn                         :: addHeadPath hp tp tn

addHeadPathTo является взаимно рекурсивным с addPathTo, поэтому я связываю их вместе с and вместо другогоlet rec.

Опять же сначала рассматривается пустой случай, который возвращает список с одним узлом и вызывает addPathTo, чтобы добавить оставшуюся часть пути.Второй случай, когда узел уже существует, и в этом случае мы добавляем остаток пути к поддереву st.Третий случай продолжает просматривать список узлов, вызывая себя рекурсивно.

Вы вызываете его следующим образом: 

createEmptyFsTree()
|> addPath ["MainNode";"nodeA";"nodeB"] 
|> addPath ["MainNode";"nodeC";"nodeD"]
|> addPath ["MainNode";"nodeC";"nodeE"]    
|> printfn "%A"
...