F# type with `and` and Lazy?

Question

I read the following type definition. What does it do?

type StreamCell<'a> =
    | Nill
    | Cons of 'a * Stream<'a>
and Stream<'a> = Lazy<StreamCell<'a>>

I tried to define the value with the type.

let x = Lazy(1::2::Nill)  // Type is Lazy<list<int>>
let y = Lazy(Nill::1)  // Lazy<StreamCell<obj>>

I thought the type of x and y should be StreamCell?

Answer 1

The and in F# exists to define recursive types. In most other languages there exists no order. Once you define a class, function and so on. You can access it. But in F# order is important. You only can access thinks that are already defined.

Because of this, usually it would not be possible to define recursive types, or in generall circular types. What i think is a good idea. But sometimes, you want this, and in this case, you must define the types that should be recursive with an and.

A simple example would be

type A = A of B
type B = B of A

and this will fail. Because when you define A, there is no B. So B must be defined before A. But you cannot define B before A because it depends on A.

So instead of using type you use and instead.

type A = A of B
 and B = B of A

You cannot create a value of this type because it would be infinite, but it's only for understanding the problem. Next, your example is not the best, because.

and Stream<'a> = Lazy<StreamCell<'a>>

is only a Type Alias. Here you define Stream<'a> as an alias to Lazy<StreamCell<'a>>. But the compiler will usually not use Stream<'a>. This only helps if you would write the type manually in your function definitions. Your definition could also be.

type StreamCell<'a> =
    | Nill
    | Cons of 'a * Lazy<StreamCell<'a>>

In your example

let x = Lazy(1::2::Nill) 

You use :: and this IS NOT the Cons you define with your stream. You will use the cons operator that is defined with F#, and that is the built-in list. This is the reason why you see Lazy<List<int>> as a type.

If you want to define your stream with two values you need to write.

let x = Cons(1,lazy Cons(2, lazy Nill))

As a general note i would rename Cons to Next or something else. To avoid confusion and create helper function to create Nill and Next values.

---

Addition

and can also be used to change the Order of definition, and make it more obvious, which types belong together.

type Person = {
    Name: string
    Sex:  Sex
}

and Sex =
    | Male
    | Female

let person = { Name="David"; Sex=Male }

---

Example

Here is a full-blown example how i would do a Stream type on what you provided.

type Stream<'a> =
    | Nill
    | Next of 'a * Lazy<Stream<'a>>

let nill     = Nill
let next h t = Next(h,t)

let rec unfold gen state =
    match gen state with
    | None          -> Nill
    | Some(x,state) -> next x (lazy unfold gen state)

let rec fold f acc xs =
    match xs with
    | Nill      -> acc
    | Next(h,t) -> fold f (f acc h) (t.Force())

let rec rev stream =
    fold (fun acc x -> next x (lazy acc)) nill stream

let toList stream =
    fold (fun acc x -> x::acc ) [] (rev stream)

let rec take x stream =
    if x > 0 then
        match stream with
        | Nill      -> Nill
        | Next(h,t) -> next h (lazy take (x-1) (t.Force()))
    else
        Nill

let fromTo start stop =
    unfold (fun acc -> if acc<stop then Some(acc,acc+1) else None) start

let x  = next 1   (lazy next 2   (lazy next 3   (lazy nill)))
let y  = next 1.0 (lazy next 2.0 (lazy next 3.0 (lazy nill)))

printfn "%A" (toList (take 2 x))
printfn "%A" (toList (take 2 y))
printfn "%A" (toList (take 2 (fromTo 1 100)))
printfn "%A" (toList (take 5 (fromTo 1 1_000_000_000)))