我刚刚读过这个线程 https://groups.google.com/d/msg/racket-users/BuUzcJtd3Ig/zqYIjVyJdjoJ并觉得很有趣。
我实施remove from the left
几分钟后即可运行:
(*
* remove duplicate from left:
* 1 2 1 3 2 4 5 -> 1 2 3 4 5
* *)
let rem_from_left lst =
let rec is_member n mlst =
match mlst with
| [] -> false
| h::tl ->
begin
if h=n then true
else is_member n tl
end
in
let rec loop lbuf rbuf =
match rbuf with
| [] -> lbuf
| h::tl ->
begin
if is_member h lbuf then loop lbuf tl
else loop (h::lbuf) rbuf
end
in
List.rev (loop [] lst)
我知道我可以实施is_member
by Map
or hashtable
让它更快,但此刻这不是我关心的。
在实施的情况下remove from the right
,我可以通过以下方式实现它List.rev
:
(*
* remove duplicate from right:
* 1 2 1 3 2 4 5 -> 1 3 2 4 5
* *)
let rem_from_right lst =
List.rev (rem_from_left (List.rev lst))
我想知道我们是否可以通过其他方式实现它?
这就是我要实施的方式remove_from_right
:
let uniq_cons x xs = if List.mem x xs then xs else x :: xs
let remove_from_right xs = List.fold_right uniq_cons xs []
同样,你可以实现remove_from_left
如下:
let cons_uniq xs x = if List.mem x xs then xs else x :: xs
let remove_from_left xs = List.rev (List.fold_left cons_uniq [] xs)
两者都有各自的优点和缺点:
- 虽然
List.fold_left
是尾递归并占用恒定空间,但它以相反的顺序折叠列表。因此,您需要List.rev
结果。
- 虽然
List.fold_right
不需要跟随List.rev
然而它需要线性空间而不是常数空间来产生结果。
希望有帮助。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)