With OCaml it is explicit, so you have to pass them explicitly, which is indeed a bit wordy (Implicit Modules will fix that though, whooo!).
Compare that to Haskell, which implements Implicit Witnesses not via Implicit Modules like OCaml is going to do, but via typeclasses. Look at a standard Haskell typeclass usage, any function that you do not know what the type is you have to define the witness:
treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
| x == a = True
| x < a = treeElem x left
| x > a = treeElem x right
See the type of the treeElem
function, it takes 2 arguments a -> Tree a
and returns a Bool
, but oh wait, what is that before the =>
, it is a third argument, in reality it is Ord a -> a -> Tree a
, just you replace the ->
with =>
to make it an ‘implicit argument’ instead of an ‘explicit argument’. The difference is that an Implicit Argument takes whatever it can from its call site, so when you use the function:
treeElem 42 theTree
The implicit argument you cannot explicitly give, what it does instead is look in the scope at where treeElem
is called and takes whatever bindings are available at this point and uses it (in this case it knows it is looking for the Ord
typeclass and looking through the Ord module’s registered types to see what matches with the type of the first resolved a
type, which since I pass in a 42
it knows is an Int
, so it looks for an Ord Int
class and implicitly passes it in at this point).
If you have a function that calls the treeElem
function but does not know the type, then you have to specify it here too:
findElemAsStringResult :: (Ord a) => a -> Tree a -> String
findElemAsStringResult x node = show (treeElem x node)
Notice that I don’t need to add the Show Bool
witness here because we already know what the type is, so when I call show
on the Bool
type return value it passes it in here. I do not need to pass the witness to show
since the implicit argument means it grabs it from the scope right here, and there is only one witness that fulfills it. Explicitly this entire function looks more like this:
findElemAsStringResult :: Ord a -> a -> Tree a -> String
findElemAsStringResult ord x node = show (Show Bool) (treeElem ord x node)
And that is indeed more of how it is compiled as, just it can ‘hide’ most of that for you since it knows about the types. In OCaml it looks more like this one, all explicit (but once Implicit Modules comes out then it will be just as succinct).
So yes, even typeclasses pass things around. You cannot call Show
on a type that does not have an appropriate class defined. You cannot call Show
on some value that you do not know what it is without accepting the witness in to your function (this allows dynamic linking as well). With Protocols you have to know all types ahead of time, not so with witnesses/typeclasses as only the point where the value is created must know.
Even in Haskell/OCaml if you have some type, say a record, that can hold an arbitrary type in one of its keys, then if ‘some call’ needs to Show
it in then the Show
witness is passed through every single call down in to it from the upper-most point of where the record is defined and stored all the way down. This is why implicit versions are so nice. OCaml’s explicit witnesses would be a lot more verbose if it were not possible to define modules in-line, like take the Map
module in OCaml (like elixir maps), you define the witness in the module definition:
module StringMap = Map.Make(String)
Map.Make
is a Functor, a module that takes an argument and returns a new module, this one takes a module that has a t
type of the key of the map and a compare : t -> t -> int
function to use for comparisons, of which String
already has this. So the StringMap
module is a module that only accepts Strings as keys. I can implement one for Integers like:
module IntMap = Map.Make(struct type t = int let compare l r = if l < r then 1 else if l > r then -1 else 0 end)
There is no default Int
module that fulfills these requirements (though most libraries define one for you so normally you’d never write that as-is), but I could even invert the comparison to get a swapped ordering of the IntMap, or zip-compare the integers or whatever I want. The witness becomes part of the type, so any place IntMap is used it already knows how to use Int’s. To use this in a function that does not know what the key type is then you still need to specify the type:
(* Let us create the witness module type first, OCaml already has tons of these though, but showing how it works: *)
module type HasKeyIn = sig
type con
type key
val mem: key -> con -> bool
end
(* And define a function that uses it like *)
let contains_key (type key) (type con) (module Witness : HasKeyIn with type key = key and type con = con) key map =
Witness.mem key map
(* And given these: *)
let is = IntMap.singleton 42 "Hello"
let ss = StringMap.singleton "bloop" "blorp"
(* You can do this, defining the witness inline here, usually it would be elsewhere or it would be a functor for easy-construction: *)
let true = contains_key (module struct type con = string IntMap.t type key = IntMap.key let mem k m = IntMap.mem k m end) 42 is
let true = contains_key (module struct type con = string StringMap.t type key = StringMap.key let mem k m = StringMap.mem k m end) "bloop" ss
And I could even change the mem function callback, or I could change it to be a set instead of a map, or a tree/trie, or a list, or an array, or whatever I want.
For note, the module Map.Make is defined as:
module Make: (Ord: OrderedType) => S with type key = Ord.t;
You see the Ord
witness there for OCaml of type OrderedType
, and OrderedType
is:
module type OrderedType = sig
type t
let compare: t -> t -> int
end
It is not quite as pervasive through OCaml as it is in Haskell (where it really is over-used), but they are ubiquitous and is how polymorphism works entirely type-safe and efficiently.
If curious, the Implicit Modules syntax in OCaml looks to be slated to become:
module type Show = sig
type t
val show : t -> string
end
let show {S : Show} x = S.show x
implicit module Show_int = struct
type t = int
let show x = string_of_int x
end
implicit module Show_float = struct
type t = float
let show x = string_of_float x
end
implicit module Show_list {S : Show } = struct
type t = S. t list
let show x = string_of_list S . show x
end
let () =
print_endline ("Show an int: " ^ show 5);
print_endline ("Show a float: " ^ show 1.5);
print_endline ("Show a list of ints: " ^ show [1; 2; 3]);
Since things like Show_int
are in scope then it can automatically use it, if it were not in scope then you’d get an error when trying to show 5
for example, with it saying that no implicit module that takes an argument of int with the specified signature was in scope. You can still explicitly pass modules too, which is great for overriding default functionality that you cannot easily do with typeclasses (really at all).
Here is the standard haskell’y monad in OCaml implicit modules:
module type Monad = sig
type + ’a t
val return : ’a -> ’a t
val bind : ’a t -> ( ’a -> ’b t) -> ’b t
end
let return {M : Monad } x = M.return x
let (>>=) {M : Monad } m k = M.bind m k
let map {M : Monad} (m : ’a M.t) f =
m >>= fun x -> return (f x)
let join {M : Monad} (m : ’a M.t M.t) =
m >>= fun x -> x
let unless {M : Monad} p (m : unit M.t) =
if p then return () else m
implicit module Monad_option = struct
type ’a t = ’a option
let return x = Some x
let bind m k =
match m with
| None -> None
| Some x -> k x
end
implicit module Monad_list = struct
type ’a t = ’a list
let return x = [x]
let bind m k = List.concat (List.map k m)
end
In OCaml you do +
to add integer, +.
to add floats, and some other things for other number types, with implicit modules you could instead just do:
val (+) : {N : Addable} -> N.t -> N.t -> N.t
Then you could just use +
for every single number type, or strings, or whatever else you want to be addable, just have to define an implicit module that uses the type you want to support and then done.
The original Implicit Module document that grew into the full PR to OCaml to add Implicit modules is https://arxiv.org/pdf/1512.01895.pdf (which also speaks of what witnesses are) if you wish to see how it is implemented, how the search space is defined, how it resolves it all at compile-time and all.
And nicely it is all not only implicit, saving a lot of typing, but it is still explicit as the modules have to be marked as implicit
or you have to mark it inline (like implict module TheImplicitModule = SomeExplicitModule
), thus nothing is fully ‘hidden’, yet it is still implicit and overridable.
In my MLElixir project I already have code started to support implicit arguments like that too.
Scala supports that.
Mmmm maybe a little? ^.^;
Well let’s see, let’s treat Erlang/Elixir ok/error tagged tuples as a monad and let’s make a module to handle them, and maybe a few others too:
defmodule MonadHelpers do
defmacro __using__(_) do
quote do
def value >>> cb, do: bind(value, cb)
def map(value, cb), do: bind(value, fn x -> return(cb.(x)) end)
def join(dvalue), do: bind(dvalue, fn x -> x end)
end
end
end
defmodule ResultMonad do
@type t :: {:ok, any()} | {:error, any()}
def return(value), do: {:ok, value}
def bind({:error, _value}=tagtup, _cb), do: tagtup
def bind({:ok, value}, cb), do: cb.(value)
use MonadHelpers
end
defmodule OptionMonad do
@type t :: {:ok, any()} | :error
def return(value), do: {:ok, value}
def bind(:error, _cb), do: :error
def bind({:ok, value}, cb), do: cb.(value)
use MonadHelpers
end
defmodule ListMonad do
@type t :: [any()]
def return(value), do: [value]
def bind(lst, cb), do: :lists.concat(:lists.map(cb, lst))
use MonadHelpers
end
And we can use them like:
iex> import ResultMonad
ResultMonad
iex> return(42)
{:ok, 42}
iex> return(21) >>> fn x -> x*2 end
42
iex> return(21) |> map(fn x -> x * 2 end)
{:ok, 42}
iex> return(21) \
...> |> map(fn x -> x * 2 end) \
...> |> map(&to_string/1)
{:ok, "42"}
iex> return(21) \
...> |> map(fn x -> x * 2 end) \
...> >>> fn x when x>100 -> {:ok, x}; x -> {:error, "Error with: #{x}"} end \
...> |> map(&to_string/1)
{:error, "Error with: 42"}
iex> return(21) \
...> |> map(fn x -> return(x * 2) end)
{:ok, {:ok, 42}}
iex> return(21) \
...> |> map(fn x -> return(x * 2) end) \
...> |> join()
{:ok, 42}
iex> return(21) \
...> |> map(fn x -> {:error, "blah"} end) \
...> |> join()
{:error, "blah"}
iex> return(21) \
...> |> map(fn x -> {:error, "blah"} end) \
...> |> join() \
...> >>> fn x -> x * 2 end
{:error, "blah"}
iex> import ListMonad
ListMonad
iex> return(2)
[2]
iex> return(2) \
...> |> map(fn x -> x * 2 end)
[4]
iex> lst = [0, 1, 2, 3, 4]
[0, 1, 2, 3, 4]
iex> lst \
...> |> map(fn x -> x * 2 end)
[0, 2, 4, 6, 8]
iex> lst \
...> |> map(fn x -> return(x * 2) end)
[[0], [2], [4], [6], '\b']
iex> lst \
...> |> map(fn x -> return(x * 2) end) \
...> |> join()
[0, 2, 4, 6, 8]
iex> lst \
...> |> map(fn x -> x * 2 end) \
...> |> map(fn x when x>5 -> []; x -> [x] end) # A filter predicate!
[[0], [2], [4], [], []]
iex> lst \
...> |> map(fn x -> x * 2 end) \
...> |> map(fn x when x>5 -> []; x -> [x] end) \
...> |> join() # Filtering based on the predicate! You could easily combine these into a single function
[0, 2, 4]
Monads are basically just piping on steroids, super simple.
And of course with witnesses and all such you can compose them all as much as you could ever want.
We use a lot of SML here, but getting OCaml in too.
Yeah the enum module is basically an enumeration-focused monad module, should get a more generic version.