我是OCaml和算法的初学者。我试图获得5位数的数字,没有重复数字大于12345。
这是我在OCaml中所做的,我试图尽可能地使尾部递归,我也使用了流。但是,由于大小,它堆栈溢出:
type 'a stream = Eos | StrCons of 'a * (unit -> 'a stream)
let rec numberfrom n= StrCons (n, fun ()-> numberfrom (n+1))
let nats = numberfrom 1
let rec listify st n f=
match st with
|Eos ->f []
|StrCons (m, a) ->if n=1 then f [m] else listify (a ()) (n-1) (fun y -> f (m::y))
let rec filter (test: 'a-> bool) (s: 'a stream) : 'a stream=
match s with
|Eos -> Eos
|StrCons(q,w) -> if test q then StrCons(q, fun ()->filter test (w ()))
else filter test (w ())
let rec check_dup l=
match l with
| [] -> false
| h::t->
let x = (List.filter (fun x -> x = h) t) in
if (x == []) then
check_dup t
else
true;;
let digits2 d =
let rec dig acc d =
if d < 10 then d::acc
else dig ((d mod 10)::acc) (d/10) in
dig [] d
let size a=
let rec helper n aa=
match aa with
|Eos-> n
|StrCons (q,w) -> helper (n+1) (w())
in helper 0 a
let result1 = filter (fun x -> x<99999 && x>=12345 && (not (check_dup (digits2 x)))) nats
(* unterminating : size result1 *)
(*StackOverflow: listify result1 10000 (fun x->x) *)
我无法重现您报告的问题。当我加载你的代码时,我看到了这个:
# List.length (listify result1 10000 (fun x -> x));;
- : int = 10000
# List.length (listify result1 26831 (fun x -> x));;
- : int = 26831
您的系统可能比我的系统更受资源限制。
我只想说,编写尾递归函数的常用方法是反向构建列表,然后在最后反转它。这可能看起来像这样:
let listify2 st n =
let rec ilist accum st k =
match st with
| Eos -> List.rev accum
| StrCons (m, a) ->
if k = 1 then List.rev (m :: accum)
else ilist (m :: accum) (a ()) (k - 1)
in
if n = 0 then []
else ilist [] st n
如果您要求的元素多于流中的元素,那么仍然存在listify不会终止的问题。引入一种方法来检测流的结束并在该点返回Eos可能更好。例如,filter
函数可能接受一个返回三个可能值的函数(该元素应该被过滤掉,元素不应该被过滤掉,流应该结束)。
问题是您的流result1
的大小未定义。
事实上,nats
是一个永无止境的流:它永远不会返回Eos
。
但是,过滤永无止境的流会导致另一个永无止境的流,因为过滤后的流只会在基础流执行此操作后返回Eos
:
let rec filter (test: 'a-> bool) (s: 'a stream) : 'a stream=
match s with
| Eos -> Eos
| StrCons(q,w) -> if test q then StrCons(q, fun ()->filter test (w ()))
else filter test (w ())
因此,size result1
试图达到整数的末尾。
另请注意,在最新版本的标准库中,您的类型stream
称为Seq.node
。