Bit strings

Consider the following type to represent bit strings:

type bitstring = E | Z of bitstring | U of bitstring;;

where E represents the empty string, Z s the string made by a 0 followed by s, and U s the string made by a 1 followed by s.

Write the following functions:

string_of_bitstring : bitstring -> string

converts a bitstring into a string.

len : bitstring -> int

computes the length of a bitstring.

countZ : bitstring -> int
countU : bitstring -> int

count the number of 0s and of 1s in a bitstring.

concat : bitstring -> bitstring -> bitstring

concatenates two bitstrings.

equals : bitstring -> bitstring -> bool

checks if two bitstrings are equal.

tl : bitstring -> bitstring

computes the tail of a bitstring; For instance:

tl (Z(U(Z(U (Z E)))))
- : bitstring = U (Z (U (Z E)))

tl E
- : bitstring = E

prefix : bitstring -> bitstring -> bool

such that prefix s1 s2 detects if s1 is a prefix of s2.

substring : bitstring -> bitstring -> bool

such that substring s1 s2 detects if s1 is a substring of s2.

Provide feedback