OCaml给定自定义stream类型声明如何实现flatten扁平化函数?
OCaml 嵌套流flatten函数实现
现有基础定义
你给出的基础流类型与工具函数如下:
exception Empty_list type 'a stream = Stream of 'a * (unit -> 'a stream) | Nil let shead s = match s with | Stream (a, _) -> a | Nil -> raise Empty_list let stail s = match s with | Stream (_, s) -> s () | Nil -> raise Empty_list let stream_to_list s = let rec stream_to_list s accumulator = match s with | Nil -> accumulator | Stream (_, _) -> stream_to_list (stail s) (shead s :: accumulator) in List.rev (stream_to_list s [])
实现思路
由于OCaml是静态类型语言,原多态stream无法直接存储「基础值」和「嵌套流」两种类型的元素,因此我们首先定义可区分的嵌套元素类型,再基于惰性流拼接实现递归中序展开:
- 定义
nested_elem变体类型,区分叶子节点和嵌套流节点 - 实现惰性流拼接函数
stream_append,保证流的惰性特性不会被破坏 - 递归遍历输入流:遇到叶子节点直接返回,遇到嵌套流先展开嵌套流再拼接后续流的展开结果,符合中序遍历要求
完整实现代码
(* 嵌套流元素类型:区分叶子值和嵌套流 *) type 'a nested_elem = | Leaf of 'a | Nested of 'a nested_elem stream (* 辅助函数:惰性拼接两个流 *) let rec stream_append s1 s2 = match s1 with | Nil -> s2 | Stream (hd, tl) -> Stream (hd, fun () -> stream_append (tl ()) s2) (* 扁平化函数:中序递归展开所有嵌套流,仅保留叶子节点 *) let rec flatten s = match s with | Nil -> Nil | Stream (elem, tl) -> match elem with | Leaf v -> Stream (v, fun () -> flatten (tl ())) | Nested nested_s -> stream_append (flatten nested_s) (flatten (tl ()))
验证示例
我们构造一个三层嵌套的流测试效果:
(* 构造最内层流:[3] *) let inner_stream = Stream (Leaf 3, fun () -> Nil) (* 构造中间层流:[2, 嵌套inner_stream, 4] *) let mid_stream = Stream (Leaf 2, fun () -> Stream (Nested inner_stream, fun () -> Stream (Leaf 4, fun () -> Nil))) (* 构造最外层流:[1, 嵌套mid_stream, 5] *) let outer_stream = Stream (Leaf 1, fun () -> Stream (Nested mid_stream, fun () -> Stream (Leaf 5, fun () -> Nil))) (* 测试扁平化结果 *) let result = stream_to_list (flatten outer_stream) (* 输出结果为:[1; 2; 3; 4; 5],无任何stream类型元素 *)
内容的提问来源于stack exchange,提问作者Omnifarious
相关产品推荐
相关产品推荐

