Re: [Caml-list] recursive records

[oleg@okmij.org]

Brigitte Pientka wrote:

> type 'a susp = Susp of (unit -> 'a)
>
> type 'a str = {hd: 'a  ; tl : ('a str) susp}
>
> let rec ones = {hd = 1 ; tl = Susp (fun () -> ones)}
>
> This works fine and many examples can be elegantly written this way.  However,
> when I define the stream ones via the function delay, OCaml fails.
>
>   let delay f = Susp f
>    let rec ones = {hd = 1 ; tl = delay (fun () -> ones)};;
>                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> Error: This kind of expression is not allowed as right-hand side of `let rec'
>
> Could someone explain why this fails?

To be fair, OCaml already provides a few relaxations for let rec
definitions, which are described in Sec 7.3 of
        http://caml.inria.fr/pub/docs/manual-ocaml/extn.html
Alain Frisch has demonstrated one such extension: lazy.

I believe though there is a better way to represent your co-patterns
in OCaml -- using objects. Objects are already have a fix-points in
them, and objects are naturally coinductive: an object receives a
message, changes its state and results in an object ready for more
messages. The only think we can do with objects is to observe them,
but sending them messages. This sounds just like the definition of
co-induction. Here how it looks like:

(* defining the class type is not necessary, but helpful.
   It defines the type 'a str that is useful when writing signatures.
   I like to write signatures
*)
class type ['a] str = object ('self)
        method hd : 'a
        method tl : 'self
end;;

class ones = object (self) 
  method hd = 1
  method tl = self
end
;;

let ones = new ones;;

let take : int -> 'a str -> 'a list = fun n str ->
 let rec loop acc str = function
   | n when n <= 0 -> List.rev acc
   | n -> loop (str#hd :: acc) (str#tl) (n-1) (* Co-patterns! str#hd and str#tl *)
 in loop [] str n
;;

take 5 ones;;
   - : int list = [1; 1; 1; 1; 1]