[MLton-user] Extended Basis Library: proposed addition to OPTION/Option

Geoffrey Alan Washburn geoffw at cis.upenn.edu
Mon Feb 26 18:58:36 PST 2007


	Here is my proposed implementation of »Option.collate«. I haven't 
tested it (at least not this particular instance) but I'm hopeful the 
logic is correct.  Stylistic suggestions are also welcome.


Index: detail/option.sml
===================================================================
--- detail/option.sml   (revision 5344)
+++ detail/option.sml   (working copy)
@@ -8,4 +8,10 @@
     open Option
     val isNone = fn NONE   => true
                   | SOME _ => false
+
+   fun collate cmp = fn (NONE, NONE)       => EQUAL
+                      | (SOME _, NONE)     => GREATER
+                      | (NONE, SOME _)     => LESS
+                      | (SOME x1, SOME x2) => cmp (x1, x2)
+
  end
Index: public/data/option.sig
===================================================================
--- public/data/option.sig      (revision 5344)
+++ public/data/option.sig      (working copy)
@@ -13,4 +13,10 @@

     val isNone : 'a t UnPr.t
     (** Returns {true} if given option is {NONE}; otherwise returns 
{false}. *)
+
+   val collate : 'a Cmp.t -> 'a t Cmp.t
+   (** Returns {EQUAL} if given {(NONE,NONE)}; {GREATER} if given 
{(SOME _, NONE)};
+       {LESS} if given {(NONE, SOME _)}; for {(SOME _, SOME _)} it uses 
the provided
+       comparison function. *)
+
  end



Geoffrey Alan Washburn wrote:
> Vesa Karvonen wrote:
>>
>> Yes, I've thought about the same thing.  I think that it would be best to
>> name functions by the properties that they are supposed to have (the
>> properties that the user depends on) rather than by the algorithms they
>> might employ (which one might want to change later as faster algorithms
>> are implemented).  
>     It is certainly a reasonable approach, I just wondered whether some 
> people might object on the grounds that using asymptotic complexity as a 
> primary specification gives a lot of leeway.  So if there eventually 
> were different implementations of the extended basis, they might observe 
> significantly different performance characteristics with different 
> implementations.
> 
>     However, I expect that in such cases they might best just implement 
> the best for their application themselves.
> 
>> This is like it is in the C++ STL, for example.  So,
>> one could use a name like
>>
>>   sortByCmp
>>
>> for the generally fastest comparison based sorting function and
>>
>>   stableSortByCmp
>>
>> for the sorting function that is as fast as possible while being stable
>> (O(n log n) and preserves relative order of equal elements).
>>   
> 
>     Given these two specifications, which algorithms do you think you 
> would select?
> 
>> Just wondering, do you use flattenOpt often?  Would it be difficult to
>> rewrite the code to use mapPartial (or something else) so that options
>> would not be added to lists?  (I mean, if flattenOpt is particularly
>> convenient in some cases, then maybe we should just add it.)
>>   
> 
>     No, it only came up in two or three places, and changing the code to 
> use mapPartial (or rather my monadic version of it) seems to be clearer 
> anyway.
> 
> 
>> The main reason I assumed arbitrary precision is that the Word types
>> already work like unsigned integers with modular arithmetic.
>>   
> 
>     Hmm.  I hadn't really thought about using words, but that may be 
> practical enough for my purposes.  Though I imagine someone still might 
> like a natural number abstraction.
> 
>> I recall one article with those keywords:
>>
>>   http://mlton.org/References#WangMurphy .
>>   
> 
>     Ah, I saw the Wizard of TILT material while I was at CMU.  While not 
> quite as good as language support, the recursion scheme solution looks 
> eminently practical.  Has anyone tried using something like the Fold 
> library (http://mlton.org/Fold) to provide nth projections and 
> injections with a single function? 
> 
> 
>>
>> Good.  As it happens, I was just working on writing concept signatures for
>> Monads (and Functors) as I received your e-mail.  See the draft signatures
>> with notes below.
>>
>>   
>     [...]
>> Contravariant functors are actually quite common.  I don't particularly
>> like the name CFUNC, but I would prefer a short name.
>>   
>     These seem reasonable, but I haven't really thought much abstracting 
> anything to be a functor yet.
>> The Monad core signature:
>>
>>   signature MONAD_CORE = sig
>>      type 'a monad
>>      val return : 'a -> 'a monad
>>      val >>= : 'a monad * ('a -> 'b monad) -> 'b monad
>>   end
>>   
>     This is essentially the same as what I had come up with for what I 
> had called BASIC_MONAD. Though I had chosen to go with the signature
> 
>     signature BASIC_MONAD = sig
>        type 'a t
>        val return : 'a -> 'a t
>        val >>= : 'a t * ('a -> 'b t) -> 'b t
>     end
> 
> As using »t« as the type seems to be convention used most other places, 
> but with »where type« constraints I don't know that it really matters 
> that much.
>    
>> The point here is that there is a functor
>>
>>   functor MkMonad (Arg : MONAD_CORE) : MONAD
>>
>> that makes a MONAD (with extra derived utility functions) given a
>> MONAD_CORE. 
>     This is again essentially the same design I have been using.
>    
>>  The MONAD signature is further split into two:
>>
>>   
>     [...]
>> The MONAD_EX signature, which one usually does not refer to explicitly,
>> specifies the derived Monad operations.  The MONAD signature is just the
>> conjunction of MONAD_CORE and MONAD_EX.  
>     This isn't quite how I thought to split things (I was using a more 
> strict hierarchy), but it is probably better given how you want to share 
> between MONAD and MONADP.
> 
>> The reason for having MONAD_EX is
>> to avoid duplicating specifications when specifying MONADP (MonadPlus):
>>
>>   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 ++. 
> 
>>   signature MONADP_EX = sig
>>      type 'a monadp_ex
>>      val sum : 'a monadp_ex List.t -> 'a monadp_ex
>>   end
>>
>>   signature MONADP = sig
>>      include MONADP_CORE
>>      include MONAD_EX where type 'a monad_ex = 'a monad
>>      include MONADP_EX where type 'a monadp_ex = 'a monad
>>   end
>>
>> Without the EX signatures, one would have to duplicate specifications in
>> MONADP.  There is also a functor
>>
>>   functor MkMonadP (Arg : MONADP_CORE) : MONADP
>>
>> for making a MONADP out of a MONADP_CORE.
>>
>> The set of derived operations in MONAD_EX and MONADP_EX is not complete -
>> I plan to add new derived operations as I see use for them.
>>   
>     It might be worth either adding some additional operations to 
> MONADP_CORE, or perhaps make things even more elaborate.  I have three 
> other MONADP operations that cannot (usually) be defined in terms of 
> MONADP_CORE. 
> 
>     val fail : 'a monad
>     val once : 'a monad -> 'a monad
>     val ifte : 'a monad -> ('a -> 'b monad) -> 'b monad -> 'b monad
> 
> The latter two are described in Kiselyov, Shan, Friedman, and Sabry 
> (http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf) and 
> provide control over backtracking.  »fail« aborts the computation 
> without any possibility for backtracking.
> 
>     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.
> 
> 
>> In addition to the above, I also have versions of the above signatures
>> with an extra type parameter:
>>   
>     [...]
>> Having two sets of signatures is a nuisance, but the extra type parameter
>> is needed often enough.
>>   
>     It depends upon your application I expect, but while I used to use 
> an extra parameter for my state monad signature, I've since switched to 
> something that would look like
> 
>     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
> 
>> The tradeoffs have to do with the degree of laziness, possibility of space
>> leaks, ease of programming and efficiency.  Even lists are lazier, but
>> also likely to be slightly slower and heavier to program with than odd
>> lists.  Wadler's article
>>
>>   http://homepages.inf.ed.ac.uk/wadler/papers/lazyinstrict/lazyinstrict.ps
>>
>> and SRFI-45
>>
>>   http://srfi.schemers.org/srfi-45/srfi-45.html
>>
>> are relevant here.  Memoization also has a cost and sometimes you might
>> want to avoid it.
>>   
>     I've printed these out to read over.  Thanks.
> 
> 
>>>     It may also be worth asking whether making lazy lists part of the 
>>> Extended Basis is reasonable.  Offhand I'm not sure if there was a 
>>> rationale behind not including sets and maps as part of the Standard
>>> Basis, and whether the same rationale applies to the Extended Basis.
>>>     
>>
>> Well, I think that there are too few SML libraries.  I think that lazy
>> lists are something that people use often enough that it makes sense to
>> provide a reasonable implementation in the Extended Basis library.
>>   
>     Sounds reasonable.  Given that it is probably worth considering some 
> additional container signatures.  Sets and maps at the very least.
> 
>> If you don't mind the overhead of sending patches and waiting for them to
>> be applied, then you don't need commit access.  Personally, I feel that it
>> adds a bit of overhead and then there is the danger that small, but
>> useful, additions never get suggested.
>>   
> 
>     Stephen gave me commit access, but I will run patches by the list 
> before making significant changes.
> 
> 
> -- 
> [Geoff Washburn|geoffw at cis.upenn.edu|http://www.cis.upenn.edu/~geoffw/]
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> MLton-user mailing list
> MLton-user at mlton.org
> http://mlton.org/mailman/listinfo/mlton-user





More information about the MLton-user mailing list