Given these type declarations in OCaml for a stream type, how to I write a flatten function?

``````exception Empty_list

type 'a stream = Stream of 'a * (unit -> 'a stream) | Nil

let shead s = match s with
| Stream (a, _) -> a
| Nil -> raise Empty_list

let stail s = match s with
| Stream (_, s) -> s ()
| Nil -> raise Empty_list

let stream_to_list s =
let rec stream_to_list s accumulator = match s with
| Nil -> accumulator
| Stream (_, _) -> stream_to_list (stail s) (shead s :: accumulator)
in List.rev (stream_to_list s [])
``````

The flatten function would take an arbitrarily nested set of streams and produce a completely flattened version that’s a result of an inorder traversal of the nesting structure and contains only the leaves. This would mean that the result of `shead` on each member of this new thing would return something that was not a stream.

The idea is that `stream_to_list (flatten s)` would give back a list in which no element was a stream.

Solution

Your desired function is ill-typed and cannot exist in a language with parametric polymorphism like OCaml: `'a stream -> 'b stream where 'b is not a stream` is not a valid type.

Parametric polymorphism requires that polymorphic functions does not change their behavior in function of the type of their argument. This useful both in term of semantics, types can be erased once type checking is done, and for type theoretical reason: proofs (aka the program) cannot inspect the theorem (aka the type) that they are trying to prove.

If you want to flatten multiple times a nested streams they are two options:

• if the nested level is known statically, you can use `flatten` multiple times. Note that it is straightforward to flatten a number of time exponential with the size of the code
``````let flatten16 x =
let flatten2 x = flatten (flatten x) in
let flatten4 x = flatten2 (flatten2 x) in
let flatten8 x = flatten4 (flatten4 x) in
flatten8 (flatten8 x)
``````

This is completely sufficient in practice since types don’t grow exponentially in human written code.

• If the level of nesting is arbitrary, the level of nesting needs to be visible on the value level (which is already needed to construct the stream). This can be achieved with the following variant type:
``````type 'a nested_seq = Seq of 'a Seq.t | Nested of 'a Seq.t nested_seq

``````

(Your type is equivalent to `Seq.t` from the standard library)

Then flattening a `'a nested_seq` to a `'a Seq.t` is a well-defined notion and that can be done with some polymorphic recursion:

``````let rec flatten: 'a. 'a nested_seq -> 'a Seq.t = fun x ->
match x with
| Seq x -> x
| Nested s -> Seq.flat_map Fun.id (flatten s)
(* or `Seq.concat (flatten s)` in OCaml 4.13 or with a sequence libray  *)
``````

Aside: `shead` and `stail` are anti-patterns: in order to safely use those functions, you need to pattern match their future argument, and them discard the matched value in each branches.

In other words,

``````let head s =
match s with
| Nil -> None
| Stream _ -> Some (shead s)
``````

is both less clear and less safe than

``````let head s =
match s with
| Nil -> None
| Stream (s, _) -> Some s
``````

(The option functions are useful to compose with generic option functions (from the option monad for instance)).

﻿﻿