Fsharp / как изменить тип Node of (string * FsTree) списка в список, где 2 пути не могут быть идентичными - PullRequest
Новая
       98

Fsharp / как изменить тип Node of (string * FsTree) списка в список, где 2 пути не могут быть идентичными

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

В FSharp я хотел бы сделать следующее

для данного типа: type FsTree = Node of (string * FsTree) list

Я бы хотел определить предикат toStringList так, чтобы: toStringList myFsTree выдавал приведенный ниже результат

результат: 

[
    ["n1"];
    ["n2"; "sub_n2_1"];
    ["n2"; "sub_n2_2"];
    ["n3"; "sub_n3"; "sub_sub_n3_1"];
    ["n3"; "sub_n3"; "sub_sub_n3_2"];
    ["n3"; "sub_n3"; "sub_sub_n3_3"];
    ["n4"];
]

Где 

let myFsT = Node [
    ("n1", Node []); 
    ("n2", Node [
    ("sub_n2_1", Node []);
    ("sub_n2_2", Node [])
    ]); 
    ("n3", Node [
    ("sub_n3", Node [
    ("sub_sub_n3_1", Node []); 
    ("sub_sub_n3_2", Node []); 
    ("sub_sub_n3_3", Node []); 
    ])
    ]); 
    ("n4", Node [])
]

То, что я сделал до сих пор (здесь ниже), абсолютно неверно, я это знаю.Но я действительно застрял здесь!У кого-нибудь есть идеи, что делать? 

let rec test (fst:FsTree) = 
        match fst with
        | Node []              -> []
        | Node ((str, subFst)::restNode) -> 
            [[str] @ (test subFst)] @ (test restNode)

1 Ответ

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

Это сложная задача, потому что для этого требуются 2 взаимно рекурсивные функции: одна для Node и одна для списка внутри Node. 

let rec processNode     prepend node =
    let rec processList prepend listOfNodes =
        match   listOfNodes with
        | []                         -> []
        | (str, subNode) :: restList -> 
            let restList = processList  prepend restList
            let newPrepend = List.append prepend [ str ]
            match processNode newPrepend subNode with
            | []  -> [ newPrepend ]
            | lst -> lst
            @ restList
    match node with Node listOfNodes -> processList prepend listOfNodes

processNode [] myFsT
|> List.iter print

Вам нужна одна рекурсивная функция для перемещения по элементам всписок: processList

и еще один, чтобы перейти к подузлам в списке: processNode.

Путаница возникает из-за того, что все, что processNode делает, это получает список от Node и затем вызывает processList, поэтому их легко представить себе так, как будто они могут быть только одной функцией.

OTOH, processList является двойной рекурсивностью.Он вызывает себя, чтобы просмотреть элементы списка, и вызывает processNode, чтобы углубиться в поддерево.

Существует также параметр аккумулятора, который необходимо передать, - prepend, который содержит путь..

...