实现一个适用于循环列表的 'List.map' 函数

Question

所以，我发现 Ocaml 支持使用 let rec 创建循环列表。

utop # let rec ones = 1::ones;;
val ones : int list = [1; <cycle>]

非常简洁，甚至可以在 utop 中打印出来而不会爆炸。

但是当我尝试对这种数据使用 List.map 时，它确实爆炸了：

utop # let twos = List.map ((+) 1) ones;;
Stack overflow during evaluation (looping recursion?).
Raised by primitive operation at Stdlib__List.map in file "list.ml", line 92, characters 32-39
Called from Stdlib__List.map in file "list.ml", line 92, characters 32-39
...

这有点令人失望，但并非完全出乎意料。

现在的问题是，是否可以实现一个 'better' 地图函数来正确处理这个问题。 IE。你会做这样的事情：

let twos = betterMap ((+) 1) ones;;

它不会爆炸，而是能够正确检测循环并产生：

val twos : int list = [2; <cycle>]

由于 ones 的列表虽然在自身上循环，但实际上是一个有限结构，所以感觉这应该是可能的。但是怎么办？

Answer 1

只有当周期在统计上已知时，才能创建循环列表。因此，如果事先不知道列表中循环的拓扑结构，就不可能创建适用于任何循环列表的映射函数。例如，此函数适用于 1-cycle 列表：

let map_1_cycle f = function
  | [] -> []
  | a :: l ->
     let rec answer = f a :: answer in
     answer

通用解决方案是使用序列，因为作为惰性列表的一种形式，它们对元素的无限序列有更好的支持：

let ones = Seq.repeat 1
let twos = Seq.map ((+) 1) ones

实现一个适用于循环列表的 'List.map' 函数

Implement a 'List.map' function that works on a circular list

ocaml

circular-reference