Stream monad operation bind used both as a map and filter operation?

Question

I want to create a stream monad with the return and bind operations

I tried the following:

module type STREAM_MONAD_SIG =
  sig
    type 'a stream 
    val return : 'a -> 'a stream 
    val bind : 'a stream  -> ('a -> 'b stream ) -> 'b stream 
    val (>>=) : 'a stream  -> ('a -> 'b stream ) -> 'b stream 
    val div5 : 'a stream -> 'a stream
end

module StMonad : STREAM_MONAD_SIG  = struct 
  type 'a stream = Nil | Cons of 'a * ( unit -> 'a stream)
  let return v = Cons(v, fun() -> Nil)
  let rec bind v f =
    match v with 
    | Nil -> Nil
    | Cons(h, t) -> 
        match f h with
        | Nil -> bind (t()) f
        | Cons(r_h, _) -> Cons(r_h, fun () -> bind (t()) f)
  let (>>=) = bind
  let div5 s1 = s1 >>= fun x -> if x mod 5 == 0 then return x else Nil
  let add2 s1 = s1 >>= fun x -> return (x+2)
end

My question is: Can this bind function be used both as a map and filter operation based on the type of f we pass? Filter application like div5, and add2 for map.

Example Input for div5:

open StMonad;;
let st = Cons(5, fun () -> Cons(6, fun () -> Cons(10, fun () -> Nil)));;
let res = div5 st;;

Output: Cons(5, Cons(10, fun () -> Nil)).

Answer 1

Yes, map and filter would work OK with your implementation.

But what if you wanted e.g. to duplicate each element in the stream, e.g. turning 1,2,3 to 1,1,2,2,3,3? Then you'd want to bind the input stream to fun x -> (Cons x, fun() -> (Cons x, fun() -> Nil)). But that wouldn't work since your code ignores the tails of the streams produced for each element in the input stream:

....
    | Cons(h, t) -> 
        match f h with
        | Nil -> bind (t()) f
        | Cons(r_h, _) -> Cons(r_h, fun () -> bind (t()) f)
                (* ^^^ here *)
....

Your current code produces at most one element for each element in the input stream:

 [    a     b    c   .....     n       ... ]     (* input   *)
      |     |    |             |
      f     f    f             f
      |     |    |             |
 [ [a1 a2]  []  [c1] .....  [n1 n2 n3] ... ]     (* outputs *)
---------------------------------------------
 [  a1           c1  .....   n1        ... ]     (* result  *)

(*  ^^ __________^^__________^^____________         map     *)
(*          ^^ ____________________________         filter  *)

Instead, all produced elements must be spliced-in, without exception:

 [ [a1 a2]  []  [c1] .....  [n1 n2 n3] ... ]     (* outputs *)
---------------------------------------------
 [  a1 a2        c1  .....   n1 n2 n3  ... ]     (* result  *)

In code:

....
  let rec bind v f =
    match v with 
    | Nil -> Nil
    | Cons(h, t) -> appendBind (f h) t f
  and appendBind s1 t f =
    match s1 with 
    | Nil -> bind (t()) f
    | Cons(h, t1) -> (Cons h, fun () -> appendBind (t1()) t f)
....