Fold/Recursion over Multiway Tree in f #

Question

Я пытаюсь адаптировать Brian's Fold для Bianary Trees (http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/), чтобы применить к Multiway деревьям.

Резюмируя из блога Брайена:

структура данных:

type Tree<'a> = 
    | Node of (*data*)'a * (*left*)Tree<'a> * (*right*)Tree<'a> 
    | Leaf 

let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf)), 
        Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf))) 

Binary Tree Fold функция

let FoldTree nodeF leafV tree = 
    let rec Loop t cont = 
     match t with 
     | Node(x,left,right) -> Loop left (fun lacc ->  
           Loop right (fun racc -> 
           cont (nodeF x lacc racc))) 
     | Leaf -> cont leafV 
    Loop tree (fun x -> x) 

примеры

let SumNodes = FoldTree (fun x l r -> x + l + r) 0 tree7 
let Tree6to0 = FoldTree (fun x l r -> Node((if x=6 then 0 else x), l, r)) Leaf tree7 

Многосторонние дерево версия[не (полностью) работает]:

Структура данных

type MultiTree = | MNode of int * list<MultiTree> 

let Mtree7 = MNode(4, [MNode(2, [MNode(1,[]); MNode(3, [])]); 
        MNode(6, [MNode(5, []); MNode(7, [])])]) 

Fold функция

let MFoldTree nodeF leafV tree = 
    let rec Loop tree cont = 
     match tree with 
     | MNode(x,sub)::tail -> Loop (sub@tail) (fun acc -> cont(nodeF x acc)) 
     | [] -> cont leafV 
    Loop [tree] (fun x -> x) 

Пример 1 Возвращает 28 - похоже на работу

let MSumNodes = MFoldTree (fun x acc -> x + acc) 0 Mtree7 

Пример 2

не работает

let MTree6to0 = MFoldTree (fun x acc -> MNode((if x=6 then 0 else x), [acc])) Mtree7 

Первоначально я думал, что MFoldTree нужен был map.something где-то, но я получил он должен работать с оператором @.

Любая помощь по второму примеру и/или исправление того, что я сделал в функции MFoldTree, было бы замечательно!

Приветствия

dusiod

Answer 1

Другим решением может быть

let rec mfold f a (MNode(x,s)) = f (List.fold (fun a t -> mfold f a t) a s) x 

действительно, мы можем рассматривать дерево как погонные структуры (сложить его).

Используйте случай

> mfold (+) 0 Mtree7;; 
val it : int = 28 

Фильтр же с нормальным складку (потому что mfold нормальная складка):

> mfold (fun a x -> if x = 6 then a else x + a) 0 Mtree7;; 
val it : int = 22 

Эта функция может быть общим (как List.fold, Array.fold ... могут быть дженериками).

«но намерение второго вернуть все дерево модифицированного таким образом, что любые узлы, которые имели значение 6, например, теперь имеют значение 0»

Но это не fold вычисления, является map!

Вы можете сделать easilly (лечение, опять же, как погонные структуры)

let rec mmap f (MNode(x,s)) = MNode(f x, List.map (mmap f) s) 

Используйте случай

> mmap (fun x -> if x=6 then 0 else x) Mtree7;; 
val it : MultiTree = 
    MNode 
    (4, 
    [MNode (2,[MNode (1,[]); MNode (3,[])]); 
     MNode (0,[MNode (5,[]); MNode (7,[])])]) 

Опять же, я предлагаю сделать это для каждого возможного списка контейнера (Seq, List , Array, ...), это позволяет пользователю выбирать лучшую стратегию в контексте.

Примечания:

• Я новичок в F #, простите меня, если какой-то не так.
• размер стека не должен быть проблемой, уровень стека равен глубине дерева.

Answer 2

Хитрость заключается в том, что вам нужно передать одну дополнительную функцию спасовать.

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

Этого недостаточно для многодорожечных деревьев. Здесь нам нужна функция nodeF, вызываемая со значением в узле, и результат, полученный путем агрегирования всех значений поддеревьев. Но вам также нужна функция - скажем combineF, которая объединяет значение, полученное из нескольких поддеревьев узла.

Ваша функция складка является хорошим началом - вам просто нужно добавить еще один рекурсивный вызов для обработки tail:

let MFoldTree nodeF combineF leafV tree = 
    let rec Loop trees cont = 
     match trees with 
     | MNode(x,sub)::tail -> 
      // First, process the sub-trees of the current node and get 
      // a single value called 'accSub' representing (aggregated) 
      // folding of the sub-trees. 
      Loop sub (fun accSub -> 
       // Now we can call 'nodeF' on the current value & folded sub-tree 
       let resNode = nodeF x accSub 
       // But now we also need to fold all remaining trees that were 
       // passed to us in the parameter 'trees'.. 
       Loop tail (fun accTail -> 
       // This produces a value 'accTail' and now we need to combine the 
       // result from the tail with the one for the first node 
       // (which is where we need 'combineF') 
       cont(combineF resNode accTail))) 
     | [] -> cont leafV 
    Loop [tree] (fun x -> x) 

Суммируя легко, потому что мы просто используем оператор + для обеих функций:

let MSumNodes = MFoldTree (+) (+) 0 Mtree7 

Фильтрация дерева более сложная. Функция nodeF получит элемент в узле и список дочерних узлов (то есть результат агрегирования) и создает узел . Функция combineF получит результат от первого узла (то есть значение MultiTree) и список дочерних элементов, созданных из оставшихся узлов. Начальное значение производится из пустого дерева является пустым список:

let MTree6to0 = 
    MFoldTree (fun x children -> MNode((if x=6 then 0 else x), children)) 
      (fun head tail -> head::tail) [] Mtree7