Notes from Compose 2017

Community
,
6

I just looked at the slides on Working with Monads in OCaml. Slide 15/17 mentions that “you can’t pass functors to functors”, and that this is an issue to implement

traverse :: Applicative f => (a -> f b) -> t a -> t (f b)

Would anyone know what exactly was being meant? Because you can in fact take functors are arguments to functors, and you can do traverse this way:

module type Functor = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

module type Applicative = sig
  type 'a t
  include Functor with type 'a t := 'a t
  val pure : 'a -> 'a t
  val app : ('a -> 'b) t -> 'a t -> 'b t
end

module type Monad = sig
  type 'a t
  include Functor with type 'a t := 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end

module type Traversal = sig
  type 'a t
  module Traverse : functor (F : Applicative) -> sig
    val traverse : ('a -> 'b F.t) -> 'a t -> 'b t F.t
  end
end

module List = struct
  type 'a t = 'a list
  let map = List.map
  let pure x = [x]
  let rec app fs xs = match fs, xs with
    | [], [] -> []
    | f::fs, x::xs ->
      let y = f x in y :: app fs xs
    | (_::_), [] | [], (_::_) -> invalid_arg "List.app"
  let return = pure
  let join = List.flatten 
  let bind m f = List.map f m |> join
  module Traverse (F : Applicative) = struct
    let rec traverse f = function
      | [] -> F.pure []
      | x::xs ->
        let y = f x in
        let ys = traverse f xs in
        let ($) = F.app in
        F.pure (fun y ys -> y::ys) $ y $ ys
  end
end

module Option = struct
  type 'a t = 'a option

  let map f = function
    | None -> None
    | Some x -> Some (f x)

  let pure x = Some x
  let app f m = match f, m with
    | Some f, Some x -> Some (f x)
    | None, _ | _, None -> None

  let return = pure
  let bind m f = match m with
    | None -> None
    | Some x -> f x
end

let () =
  let module T = List.Traverse(Option) in
  let open T in
  assert
    (traverse (function true -> Some 1 | false -> Some 2) [true; false; true]
     = Some [1; 2; 1]);
  assert
    (traverse (function true -> Some 1 | false -> None) [true; false; true]
     = None);
  ()
3 Likes