[MLton-user] Re: RFC: Extended Basis Library

[Geoffrey Alan Washburn]

Vesa Karvonen wrote:

> Note that the misc-util library in mltonlib already has a merge sort implementation:
> 
>   http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/com/ssh/misc-util/unstable/sorted-list.sml?view=auto
>   http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/com/ssh/misc-util/unstable/sorted-list-test.sml?view=auto

Are you recommending moving these into extended basis?

I've been thinking that it would make sense to develop a signature 
»SORTABLE« in »public/sequence«.  However, I am not sure how to best 
address the cardinality policy in your implementation above.  When 
sorting arrays (and perhaps vectors as well) I expect it would be 
undesirable to use a cardinality policy that alters the length of the
array.  I'm not sure if the correct thing to do here would be to instead
of providing a policy argument to just provide two sets of functions if
it makes sense for the underlying sequence.
	
> That shouldn't be too hard.  Looking at page 4 of the article, I think
> that something like this should suffice (uncompiled):
> 
>   fun prjF ? = Fold.fold (prj, id) ?
>   fun S ? = Fold.step0 prj_succ ?
> 
> Instead of
> 
>   case prjn x of
>     ...
> 
> you could then write
>              __n__
>             /     \
>   case prjF S ... S $ x of
>     ...

	Okay, I'll have to look into giving this a try.

>>>   signature MONADP_CORE = sig
>>>      include MONAD_CORE
>>>      val zero : 'a monad
>>>      val plus : 'a monad BinOp.t
>>>   end
>>>
>>> I'm not sure if the names zero and plus are the best.
>>     I called them »zero« and ++. 
> 
> Hmmm... The symbolic ++ and an infix declaration for ++ might be better.
> What about associativity and precedence?  We should probably reconsider
> the precedences of all monadic operators.

Haskell uses

   infix 1 >> >>=
   infixr 1 =<<

I haven't seen any infix uses of mplus other than via `mplus`.

> In section 4.1 of the article, the authors specify a new type class called
> LogicM that inherits from MonadPlus rather than change the MonadPlus
> class.  I think that any extra primitives should go into another
> (extended) signature.  The basic MonadPlus class (or MONADP_CORE) is
> useful for many things without the extra primitives.  

	True.

> Also, from my quick
> reading of the article, I get the impression that once and ifte (and
> interleave and >>-) can be implemented in terms of msplit + MonadPlus, so
> I'm not sure that having once and ifte in a CORE signature makes sense.

I had meant to mention that technically »msplit« is more primitive, but 
for my purposes I actually found it easier to write »once«, etc. 
directly.  But that

>>     Another variation I use is to actually give »zero« and »fail« arguments
>>
>>        type error
>>        val zero : error -> 'a monad
>>        val fail : error -> 'a monad
>>
>> and then a »where type« constraint is used to specify the nature of 
>> »error« values.  I'm not sure how to fit this in well.
> 
> AFAIU, the fail function in Haskell's Monad type class is there mainly for
> practical reasons related to the Haskell language and the same reasons do
> not apply to SML.  In particular, in SML, you can just raise an exception
> if you detect an *error* during a computation.  

Having »fail« in practice seems to be a little more convenient than 
raising an exception.  At least, my idiom tends to look something like

	(some computation) >> (fail errorMsg)

and simply replacing it with a

	(some computation) >> (raise errorExn)

would have the incorrect semantics, so additional thunking would be 
necessary everywhere

	(some computation) >> (thunkM (fn () => raise errorExn))

I suppose arguably a reasonable middle ground would be to give »fail« 
the type

	val fail : exn -> 'a monad

giving

	(some computation) >> (fail errorExn)


I'll need to think some more about the options regarding »zero«.

> OTOH, if you want to have
> a monad with more control, e.g. over backtracking, than is offered by
> MonadPlus (or MONADP_CORE), then you should use an extension of it,
> e.g. LogicM (or, say, LOGICM_CORE).  So, I would rather see signatures
> LOGICM_CORE, LOGICM_EX and LOGICM rather than have MONADP_CORE changed.

	Sure.

>>
>>     signature STATE_MONAD = sig
>>        include MONAD_CORE
>>        include MONAD_EX where type 'a monad_ex = 'a monad
>>        type state
>>        val getState : state monad
>>        val setState : state -> unit monad
>>        val run : state -> 'a monad -> 'a monad
>>     end
> 
> Is the type of run correct?


	No it isn't.  I probably should haven't tried synthesizing it on the 
fly.  The actual type I use is

	val run : state -> 'a monad -> ((state, 'a) Pair.t, error) Sum.t

But given that at present »zero« doesn't take an error argument, it 
would be

	val run : state -> 'a monad -> (state, 'a) Pair.t


> Something like that could also be provided in addition to other monad
> signatures.  However, I would factor that into combinable signatures.
> Something like this:
> 
>   signature MONAD_WS = sig (* WS = WITH_STATE *)
>      type 'a monad_ws
>      type monad_ws_state
>      val getState : monad_ws_state monad_ws
>      val setState : monad_ws_state -> Unit.t monad_ws
>      val run : monad_ws_state -> 'a monad_ws UnOp.t
>   end
> 
>   signature MONAD_STATE = sig
>      include MONAD
>      include MONAD_WS where type 'a monad_ws = 'a monad
>   end
> 
> Doing it like this means that you can then combine MONAD_WS with
> MONADP_CORE
> 
>   signature MONADP_STATE = sig
>      include MONADP
>      include MONAD_WS where type 'a monad_ws = 'a monad
>   end
> 
> and LOGICM
> 
>   signature LOGICM_STATE = sig
>      include LOGICM
>      include MONAD_WS where type 'a monad_ws = 'a monad
>   end


Sure that sounds like a good plan.

Though that turns out to be quite a few signatures.  It would be nice if 
something like »Ramsey, Fisher, Govereau«'s proposal were adopted.

My implementation has a number of functions that probably would be best 
put into the MONAD_EX signature (and the MkMonad functor)

   (* Like "o" but for monadic functions *)
   val oo : ('b -> 'c monad) * ('a -> 'b monad) -> ('a -> 'c monad)

   (* Turn a "pure" function into a bindable function *)
   val lift  : ('a -> 'b) -> 'a -> 'b monad

   (* Turn a "pure" thunk into a computation *)
   val thunk : 'a Thunk.t -> 'a monad

   (* Ignore the result of a computation *)
   val ignore : 'a monad -> unit monad

   (* Perform some computation only if the guard is true *)
   val when : bool -> unit monad -> unit monad

   (* Perform some computation only if the guard is false *)
   val unless : bool -> unit monad -> unit monad

then there are a few more that pretty much deal entirely with lists.  I 
don't know if it makes sense to put them in MONAD_EX or somewhere else. 
  Right now I've given them them the names used in Haskell just for my 
benefit, but it would probably be better to give them more SML like names

   val tabulateM : int -> (int -> 'a monad) -> 'a List.t monad
   val mapM : ('a -> 'b monad) -> 'a List.t -> 'b List.t monad
   val mapM_ : ('a -> 'b monad) -> 'a List.t -> unit monad
   val appM : ('a -> unit monad) -> 'a List.t -> unit monad
   val foldlM : ('a * 'b -> 'b monad) -> 'b -> 'a List.t -> 'b monad
   val foldrM : ('a * 'b -> 'b monad) -> 'b -> 'a List.t -> 'b monad

Let me know I what you think and I can prepare a patch for these.

I almost have a patch for the »ByEq« and »ByCmp« functions ready, but I 
wanted to wait until we hashed out the sorting signature(s) as discussed 
above.

Another bit of code I have that might make sense in the extended basis 
is my »ListTriple« signature and structure.  Is it basically just »zip« 
and »unzip« for triples instead of pairs, but could be extended to match 
»ListPair«.  However, maybe it would be better to write a »ZIP« 
signature for sequences based upon »Fold« and the »PRODUCT« signature.