[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