笛卡尔乘积(复杂性改进)
笛卡尔乘积(复杂性改进)
提问于 2018-06-02 17:33:55
我想写一个函数，给出两个序列的cartesiant乘积，这就是我所做的，但我认为它可能很有趣，因为我想使用s1浏览第一个序列一次，并使用map浏览第二个序列n次，然后附加所有结果：
`let cartesian_product a b =
let na = length a in
let nb = length b in
init
(na * nb)
(fun j -> let i = j / nb in
at a i, at b (j - i*nb))
`这就是我当时所做的：
`let rec cartesian_product a b =
let rec aux x b () = match b () with
| Nil -> Nil
| Cons(e, b) -> Cons ((x, e), aux x b)
in
match a () with
| Nil -> nil
| Cons (x, a) -> append (aux x b) (cartesian_product a b)`但是我没有使用map (有没有更好的方法)？？
回答 2
Stack Overflow用户
发布于 2018-06-02 18:40:34
您的aux函数本质上是map的一个特例，因此您可以这样写：
let rec cartesian_product a b = match a () with
| Nil -> Nil
| Cons (x, a) -> append (map (fun e -> (x, e)) b) (cartesian_product a b)经验法则是，当您觉得需要编写一个名为aux的函数时，请后退一步，考虑是否可以使用map或fold。实际上，您可以通过使用fold而不是自己解构序列来改进我的代码。
Stack Overflow用户
发布于 2018-06-04 18:26:57
下面是一个结构为list的算法示例：
let cartesian_product a b =
let open List in
let mk_tuple l n = map (fun x -> (n,x)) l in
a |> map (mk_tuple b) |> fold_left append []这将为您提供：
cartesian_product [0;1] [2;3];;
- : (int * int) list = [(0, 2); (0, 3); (1, 2); (1, 3)]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50655463
复制相关文章
相似问题
腾讯云开发者
