OCaml - 返回列表所有前缀的函数

Question

对于

[1;2;3]

，我想退货

[[]; [1]; [1; 2]; [1; 2; 3]]

。我碰壁了，我需要帮助，这就是我到目前为止所做的

let rev list =
let rec aux acc = function
  | [] -> acc
  | h::t -> aux (h::acc) t in
aux [] list;;

let  prefixes xs = 
let xs = rev xs in
let rec xs = function
    |[] -> [[]]
    |hd::tl ->  xs:: tl in
xs ;;`

请帮助我，我知道到目前为止我所做的大部分事情可能都是错误的。

Answer 1

通常要问的问题是，给定一个返回较短列表的所有前缀的函数，如何获取列表的前缀。

假设您的清单是

[1; 2; 3]

。较短的列表是

[2; 3]

。这个较短列表的所有前缀都是

[]

、

[2]

和

[2;3]

。如何从此列表中获取所需的前缀列表？这看起来很简单：您只需在所有这些的前面添加

1

即可。另外，您需要添加一个新的空前缀。

作为基本情况，[] 的所有前缀列表就是 []。

这似乎是解决问题的可行方法，只不过最好的方法是使用

List

模块中的函数。因为这看起来像家庭作业，我不确定这是允许的。

我希望这有帮助。

作为附带评论，你的

rev

功能对我来说看起来不错。但您可能不需要它来解决问题。也许您可以编写自己的

map

函数。

Answer 2

这是我找到的解决方案。尽管这可能不是最好的，因为我需要在最后反转列表。

let prefix l = List.rev (List.fold_left (fun acc itt -> ((List.hd acc)@[itt])::acc) [[]] l);;

Answer 3

let rec prefixes  = function
       []   -> [[]]
  | x::tl   -> []::List.map (fun li -> x :: li) (prefixes tl);; 

测试：

# prefixes [1];;
- : int list list = [[]; [1]]
# prefixes [1;2];;
- : int list list = [[]; [1]; [1; 2]]
# prefixes [1;2;3];;
- : int list list = [[]; [1]; [1; 2]; [1; 2; 3]]

Answer 4

这个看起来比之前发布的解决方案简单得多。请注意

List.map

不是尾递归。

let rec prefixes l = match l with
    [] -> []
  | x::xs -> [x] :: List.map (fun a -> x :: a) (prefixes xs);;