Re: Recursion vs Iteration

From

Vitaly Lugovsky (2:5080/1003)

To

Oleg I. Khovayko

Date

2003-01-17T23:21:25Z

Area

RU.ALGORITHMS

From: Vitaly Lugovsky <vsl@ontil.ihep.su>

Oleg I. Khovayko <olegh@ncbi.nlm.nih.gov> wrote:

> let rec tfindl f nl =
>   let rec nxtlyr = function
>     hd :: tl ->
>      (match hd with
>        Tnode(v,l,r) -> if f v than raise (Found(v)) else
>          l::r::(nxtlyr tl) | Tnone -> nxtlyr tl
>       )
>    | [] -> []
>   in tfindl f (nxtlyr nl)

 А вот теперь поизвращаемся. Дабы мощщу и универсальность рекурсии показать,
да и просто заради маразма.

 Предположим, что следующие функции у нас и так уже есть (по крайней мере
у меня они многа-многа где используются).

let rec dolist f l =
  let ll = f l in
  match ll with [] -> [] | _ -> dolist f ll

let s x = x

 Так как мы работаем с деревьями, то и такая вся из себя generic функция
тоже есть, и много где ещё нужна:

let dotree f n fl fr t =
  match t with Tnone -> n |
   Tnode(v,l,r) -> f v (fl l) (fr r)

 Тогда, послойный поиск получится таким:

let tfind2 f0 l0 =
  dolist (fun nl -> List.flatten (List.map (dotree
     (fun v l r -> f0 v; [l;r]) [] s s) nl)) [l0]

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

--- ifmail v.2.15dev5
 * Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)