OCaml Users ML

こんにちは．向井と申します．


先日より，「互いに素」を計算するプログラムで頭を悩ませています．お知恵
を拝借したく，メールしました．

http://www.sampou.org/cgi-bin/cahier.cgi?Cahier%3a2004-01-02&l=jp
↑この URL で，真理値からなるテーブルで互いに素かどうか判断させる
Haskell のプログラムがあるのですが，同じことを OCaml でやろうとすると，
This kind of expression is not allowed as right-hand side of `let rec'
と言われてしまい，コンパイルできません．


この話から派生して，いくつか別アプローチがあり，
http://www.sampou.org/cgi-bin/cahier.cgi?comment%3aCahier%3a2004-01-02&l=jp
http://www.sampou.org/cgi-bin/cahier.cgi?comment%3aCahier%3a2004-01-03&l=jp
この2つは実装できました．

しかし，
http://www.sampou.org/cgi-bin/cahier.cgi?comment%3aCahier%3a2004-01-05&l=jp
の方は同じくエラーが出てコンパイルできなくなります．


このエラーメッセージは，なぜ出るのでしょうか？　また， OCaml ではこの
ような記述をする方法はないのでしょうか？


私の書いたプログラムを付します．「遅延リスト」のモジュールを自作してい
るのでやや長いですが，肝心の定義じたいはそれほどでもないと思います．

--
module type LSEQ =
sig
type 'a seq;;

val empty : 'a seq;;
val is_empty : 'a seq -> bool;;

val of_list : 'a list -> 'a seq;;
val to_list : 'a seq -> 'a list;;
val of_a : 'a -> 'a seq;;

val cons : 'a -> 'a seq Lazy.t -> 'a seq;;
val append : 'a seq -> 'a seq -> 'a seq;;

val head : 'a seq -> 'a;;
val tail : 'a seq -> 'a seq;;
val take : int -> 'a seq -> 'a seq;;
val nth : int -> 'a seq -> 'a;;
val map : ('a -> 'b) -> 'a seq -> 'b seq;;

val cycle : 'a seq -> 'a seq;;

val ( @! ) : 'a seq -> int -> 'a;;
val ( @: ) : 'a -> 'a seq -> 'a seq;;
end


module Lseq : LSEQ =
struct
type 'a seq = Nil | Cons of 'a * ('a seq Lazy.t);;
exception Empty

let empty = Nil;;
let is_empty = function
| Nil -> true
| _ -> false;;

let rec of_list = function
| [] -> Nil
| x::xs -> Cons(x, lazy(of_list xs));;

let rec to_list = function
| Nil -> []
| Cons(h, t) -> h::to_list (Lazy.force t);;

let of_a a = Cons(a, lazy(empty))

let cons n s = Cons(n, s);;
let rec append s1 s2 = match s1, s2 with
| Nil, _ -> s2
| Cons(h1, t1), _ -> Cons(h1, lazy(append (Lazy.force t1) s2));;

let head = function
| Nil -> raise Empty
| Cons(h, _) -> h;;
let tail = function
| Nil -> raise Empty
| Cons(_, t) -> Lazy.force t;;

let rec take n = function
| Nil -> Nil
| Cons(h, t) ->
if n = 0 then Nil
else Cons(h, lazy(take (n-1) (Lazy.force t)));;

let rec nth n = function
| Nil -> raise Empty
| Cons(h, t) -> if n = 0 then h else nth (n-1) (Lazy.force t);;

let rec map f = function
| Nil -> Nil
| Cons(h, t) -> Cons(f h, lazy(map f (Lazy.force t)));;

let cycle s =
let rec ap = function
| Nil -> ap s
| Cons(h, t) -> Cons(h, lazy(ap (Lazy.force t)))
in ap s;;

let ( @! ) s n = nth n s;;
let ( @: ) e s = cons e (lazy s);;
end;;



open Lseq;;

let rec from n = cons n (lazy (from (n+1)));;
let natural = from 0;;

let rec col = function
| 0 -> (fun m -> false)
| 1 -> (fun m -> true)
| n -> (fun m -> (row n) (m mod n))
and row n = (fun m -> (col m) n);;

let rec s = function
| 0 -> false @: true @: (cycle (of_a false))
| n -> map (nth n) (map s (cycle (take n natural)));;

let rec ss = (false @: true @: (cycle (of_a false))) @:
(map (fun n -> map (nth n) (cycle (take n ss))) (from 1));;

let rec ss = map s natural
and s = function
| 0 -> cycle (of_a false)
| 1 -> cycle (of_a true)
| n -> cycle (map (nth n) (take n ss));;