英文:
Flattening a Nested List in OCaml
问题
我在做问题7的OCaml练习。它基本上要求给定一个嵌套列表的定义：
type 'a node =
| One of 'a
| Many of 'a node list
编写一个名为flatten的函数来展开它：
assert (
flatten [ One "a"; Many [ One "b"; Many [ One "c"; One "d" ]; One "e" ] ]
= [ "a"; "b"; "c"; "d"; "e" ])
网站提供的解决方案如下：
let flatten list =
let rec aux acc = function
| [] -> acc
| One x :: t -> aux (x :: acc) t
| Many l :: t -> aux (aux acc l) t
in
List.rev (aux [] list)
;;
我想知道为什么他们使用x :: acc然后在最后反转列表，而不是使用acc @ [x]，这样就可以避免在最后反转列表了？
英文:
I'm doing problem 7 of the OCaml exercises. It basically asks given a nested list as defined:
> ocaml
> type 'a node =
> | One of 'a
> | Many of 'a node list
>
Write a function function flatten that flattens it:
> ocaml
> assert (
> flatten [ One "a"; Many [ One "b"; Many [ One "c"; One "d" ]; One "e" ] ]
> = [ "a"; "b"; "c"; "d"; "e" ])
>
The solution provided by the website is as follows:
> ocaml
> let flatten list =
> let rec aux acc = function
> | [] -> acc
> | One x :: t -> aux (x :: acc) t
> | Many l :: t -> aux (aux acc l) t
> in
> List.rev (aux [] list)
> ;;
>
I'm wondering why they do x :: acc and then reverse the list instead of acc @ [x] which would avoid the need to reverse the list at the end?
答案1
得分: 4
如何工作的@? 嗯，让我们定义它。
let rec (@) lst1 lst2 =
match lst1 with
| [] -> lst2
| x::xs -> x :: (xs @ lst2)
因此，为了将一个列表附加到另一个列表，我们必须遍历第一个列表的所有元素。如果我们在循环内执行此操作，随着第一个列表变得更长，到达其末尾所需的时间也会更长。用大O符号表示，这具有O(n^2)或"二次"性能。对于小样本大小来说还可以，但对于大样本大小来说就不划算了。
然而，:: 操作的时间复杂度是_常数_时间。无论列表有多大，将一个值附加到其前面总是需要相同的时间。如果我们在循环中执行这个操作，就会得到O(n)或"线性"性能。
反转一个列表也是线性时间的。运行_两个_线性时间操作是否代价高昂？当然，比运行_一个_更昂贵，但考虑两次n与n平方的比较：
| n | 2n | n^2 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 2 | 1 |
| 2 | 4 | 4 |
| 3 | 6 | 8 |
| 4 | 8 | 16 |
| 100 | 200 | 10,000 |
| 10,000 | 20,000 | 100,000,000 |
| 1,000,000 | 2,000,000 | 1,000,000,000,000 |
另外需要注意的是，OP展示的flatten实现中使用了::，但它不是尾递归的。以下是一个尾递归版本：
let flatten lst =
let rec aux lst to_process acc =
match lst, to_process with
| [], [] -> acc
| [], _ -> aux to_process [] acc
| (One v)::xs, _ -> aux xs to_process (v :: acc)
| (Many lst')::xs, _ -> aux lst' (xs @ to_process) acc
in
List.rev @@ aux lst [] []
英文:
How does @ work? Well, let's define it.
let rec (@) lst1 lst2 =
match lst1 with
| [] -> lst2
| x::xs -> x :: (xs @ lst2)
So, in order to append one list to another, we have to iterate over all of the first list. If we do this within a loop, as that first list gets longer, it takes longer to get to the end of it. In big-O notation, this has O(n^2) or "quadratic" performance. Fine for small sample sizes, but prohibitive for large sample sizes.
However, :: occurs in constant time. It doesn't matter how big the list is, it will always take the same amount of time to cons a value onto the front of it. If we do that in a loop, we get O(n) or "linear" performance.
Reversing a list also works in linear time. Is it costly to run two linear time operations? Certainly more so that running one, but consider two times n vs. n squared:
| n | 2n | n^2 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 2 | 1 |
| 2 | 4 | 4 |
| 3 | 6 | 8 |
| 4 | 8 | 16 |
| 100 | 200 | 10,000 |
| 10,000 | 20,000 | 100,000,000 |
| 1,000,000 | 2,000,000 | 1,000,000,000,000 |
An additional note: the implementation of flatten shown by the OP which utilizes :: is not tail-recursive. The following would be:
let flatten lst =
let rec aux lst to_process acc =
match lst, to_process with
| [], [] -> acc
| [], _ -> aux to_process [] acc
| (One v)::xs, _ -> aux xs to_process (v :: acc)
| (Many lst')::xs, _ -> aux lst' (xs @ to_process) acc
in
List.rev @@ aux lst [] []
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论