Есть у меня тип n-арного дерева, определенным следующим образом:
type 'a Tree =
| Node of 'a * 'a Tree seq
| Leaf of 'a
И захотелось мне написать для него функцию свертки. Родилось нечто следующее:
let rec fold procLeaf procNode = function
| Leaf(x) -> procLeaf x
| Node(x, children) -> children |> Seq.map (fold procLeaf procNode) |> procNode x
А теперь возник вопрос. Как сделать эту функцию хвостово-рекурсивной с помощью CPS? Если бы ветвей было наперед известное конечное число, я процесс представляю, но вот как вывести такую большую-большую лямбду из n вложенных вызовов fold', а потом еще и все аргументы из всех лямбд передать последовательностью в procNode — ума не приложу.
Здравствуйте, Mangar, Вы писали: M> Если бы ветвей было наперед известное конечное число
А что меняется от того, что их число неизвестно? Ты же проходишь по ним через map.
Перепиши с map на велосипедную функцию — и все встанет на свои места.
Другое дело, что от переписывания в cps обход дерева может и не стать оптимальнее. Я не силен в твоем языке и не знаю, есть ли там такое понятие как stack overflow, но если нет — то контекст выполнения (либо объем съеденного стека, либо размер континуации) и так и так будет расти при спуске вниз по дереву и уменьшаться при подъеме вверх.
Здравствуйте, Mr.Cat, Вы писали:
MC>А что меняется от того, что их число неизвестно? Ты же проходишь по ним через map. MC>Перепиши с map на велосипедную функцию — и все встанет на свои места.
Меняется то, что, когда я вызываю i-го потомка, мне надо передать в него функцию континуации, которая состоит из вложенных лямбд с параметрами от i-го до n-го и вызовов от (i+1)-го до n-го, а в самой глубине собрать все аргументы всех лямбд в одну последовательность (seq), и передать ее в функцию обработки вершины.
Я что-то как-то не въезжаю, как подобное выглядит.
MC>Другое дело, что от переписывания в cps обход дерева может и не стать оптимальнее. Я не силен в твоем языке и не знаю, есть ли там такое понятие как stack overflow, но если нет — то контекст выполнения (либо объем съеденного стека, либо размер континуации) и так и так будет расти при спуске вниз по дереву и уменьшаться при подъеме вверх.
Это F#. Да, stack overflow в нем есть. Именно поэтому я и хочу переписать все это дело на CPS — перетянуть все в кучу. Я прекрасно понимаю, что я просто эмулирую стек в куче этими континуациями, и что ее объем в памяти наростает по мере погружения. Но вот переполнения стека не будет.
Здравствуйте, Mangar, Вы писали: M>Меняется то, что, когда я вызываю i-го потомка, мне надо передать в него функцию континуации, которая состоит из вложенных лямбд с параметрами от i-го до n-го и вызовов от (i+1)-го до n-го, а в самой глубине собрать все аргументы всех лямбд в одну последовательность (seq), и передать ее в функцию обработки вершины. M>Я что-то как-то не въезжаю, как подобное выглядит.
Не, как-то это не так выглядит. По идее, тебе нужно перевести в cps по отдельности все используемые тобой функции (начни с map). Ты увидишь, что длинная континуация строится не сразу, а просто увеличивается при каждом вызове. Например, в вызов fold, который внутри map передается континуация вида "вернись сюда и продолжи делать map".
Re: CPS для свертки n-арного дерева
От:
Аноним
Дата:
03.02.10 12:11
Оценка:
Здравствуйте, Mangar, Вы писали:
M>А теперь возник вопрос. Как сделать эту функцию хвостово-рекурсивной с помощью CPS?
А зачем отдельные функции для листов и ветвей? Можно же одной обойтись.. с CPS типа так получилось:
let rec mfoldl f node acc =
let rec mfoldli node acc next =
match node with
|Leaf v -> next (f acc v)
|Node (v,ns) -> Seq.fold (fun fn n -> (fun a -> mfoldli n a fn)) next ns (f acc v)
mfoldli node acc id
let inp = Node (1,[Leaf 2 ; Node (3,[Leaf 4 ; Leaf 5]) ; Node (6,[Leaf 7])])
printfn "%A" <| mfoldl (+) inp 0
Здравствуйте, Аноним, Вы писали:
А>А зачем отдельные функции для листов и ветвей? Можно же одной обойтись.. с CPS типа так получилось:
А>
А>let rec mfoldl f node acc =
А> let rec mfoldli node acc next =
А> match node with
А> |Leaf v -> next (f acc v)
А> |Node (v,ns) -> Seq.fold (fun fn n -> (fun a -> mfoldli n a fn)) next ns (f acc v)
А> mfoldli node acc id
А>let inp = Node (1,[Leaf 2 ; Node (3,[Leaf 4 ; Leaf 5]) ; Node (6,[Leaf 7])])
А>printfn "%A" <| mfoldl (+) inp 0
А>
Отдельные нужны, потому что функция для листа выдает ответ на основании данных листа, а функция ветви — на основании данных ветви и результатов свертки каждого из потомков. Т.е. у меня в оригинальном посте procNode имеет тип 'a -> seq<'b> -> 'b.
Принцип вашего кода понятен, спасибо огромное. Только вот, к примеру, я не представляю, как с помощью свертки через единственную функцию f вычислить высоту дерева за одно сведение к fold.
В моей версии это было бы:
let height tree =
fold (fun _ -> 1) (fun _ subs -> 1 + Seq.max subs) tree
Вот отсюда и проблема, собственно — надо одновременно и функции континуации вкладывать одна в другую, и ответы их все собирать в последовательность для вызова функции ветви.
если seq заменить за list, можно сделать что-то такое:
type 'T Tree =
| Leaf of 'T
| Node of 'T * list<'T Tree>
let foldTree fLeaf fNode t =
let rec processNode node k =
match node with
| Leaf(v) -> k (fLeaf v)
| Node (v, nodes) -> processList nodes (fun rs -> k (fNode v rs)) []
and processList nodes k acc =
match nodes with
| [] -> k (List.rev acc)
| x::xs -> processNode x (fun r -> processList xs k (r::acc))
processNode t id
let height t =
foldTree
(fun x -> 1)
(fun x xs -> 1 + List.max xs)
t
