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

[Geoffrey Alan Washburn]

Vesa Karvonen wrote:
>>          - A function »apply« (or »$« in Haskell) in the FN signature.
>>          At least I didn't see 	this anywhere.  It is essentially
>>
>>                  infixr $ 5 (* Or whatever precedence makes sense *)
>>                  fun (f : 'a -> 'b )$ (x : 'a) : 'b = f x
>>     
>
> This is called |< in Fn.  There is also a Wiki page
>
>   http://mlton.org/InfixingOperators
>
> that introduces it.  The Fold technique, which I'm also using,
>
>   http://mlton.org/Fold
>
> uses the $ symbol for the Fold technique.  I've previously considered
> using the $ symbol for this operator also, but... I prefer to reserve it
> for the Fold technique.
>   

    This fine then, I just hadn't looked closely enough at the piping 
operators.

>>          - A function »unique« on lists. Given a list and a binary
>>          predicate, test whether no elements are related to each other
>>
>>                  val nub : 'a BinPr.t -> 'a List.t -> Bool.t
>>     
>
> I assume the name is a typo.  
    Right, copy and paste error.

> I'd write the spec as
>
>   val unique : 'a BinPr.t -> 'a List.t UnPr.t
>
> which is slightly shorter.
>
> The function is propably good, but the above description doesn't quite
> give me a complete picture of the semantics of the function.  What is the
> semantics of the binary predicate supposed to be?  Should it be an
> equivalence relation, partial order, or is any relation ok?  What is the
> time complexity of the operation?  I tend to avoid encouraging inherently
> inefficient (Theta(n^2)) algorithms.
>   
    See my comments for »partition«/»divide« below.

>>          - A function »partition« on lists (not the same as
>>          List.partition in the Standard Basis). Given a list and a
>>          binary predicate, divide the list up into equivalence classes
>>
>>                  val partition : 'a BinPr.t ->
>>                                  'a List.t ->
>>                                  ('a List.t) List.t
>>     
>
> Perhaps the name could be divideByEq (assuming the predicate corresponds
> to an equivalence relation).  Again, I just worry slightly about the time
> complexity.  Note that depending on the information given, an operation
> like this can be performed with various asymptotic time complexities:
>
>   divideByEq    ->  O(n^2)
>   divideByCmp   ->  O(n log n)
>   divideByToInt ->  O(n)
>   
    Splitting this into two (or three) different functions as proposed 
makes sense.  Currently, my implementation is just »divideByEq«, but 
I'll probably add »divideByCmp« soon as I can certainly use it in a 
number of places. 

    Providing »ByCmp« and »ByToInt« means that it would probably be 
worthwhile to also provide some sorting functions

       val sortByCmp : 'a BinPr.t -> 'a t -> 'a t
       val sortByToInt : ('a -> Int.t) -> 'a t -> 'a t

However, I'm not sure how to select which algorithms should be used 
here.  Even if they are required to have time complexity of O(n log n) 
and O(n) respectively, that leaves a number of choices.  I'm not sure if 
instead it would be preferable to just name them by algorithm

       val sortMerge : 'a BinPr.t -> 'a t -> 'a t
       val sortQuick : 'a BinPr.t -> 'a t -> 'a t
       val sortRadix : ('a -> Int.t) -> 'a t -> 'a t

and so forth.

>>          - A function »nub« on lists (this is what Haskell calls it)
>>          Given a list and a binary predicate (equality is the common
>>          case) that returns a list of representative elements for each
>>          equivalence class the binary predicate induces
>>
>>                  val nub : 'a BinPr.t -> 'a List.t -> 'a List.t
>>     
>
> Sounds good with similar worries. :) Maybe use a name like nubByEq to
> allow for faster alternatives?  
    Right, I've changed my signature, the implementation isn't complete, 
to be

       val uniqueByEq : 'a BinPr.t -> 'a t UnPr.t
       val uniqueByCmp : 'a Cmp.t -> 'a t UnPr.t
   
       val divideByEq : 'a BinPr.t -> 'a t -> 'a t t
       val divideByCmp : 'a Cmp.t -> 'a t -> 'a t t

       val nubByEq : 'a BinPr.t -> 'a t -> 'a t
       val nubByCmp : 'a Cmp.t -> 'a t -> 'a t

> What about the name of unique?
>   

    I'm not sure what you mean.  Do you mean an alternative to »unique« 
or do you mean using the »ByFoo« convention?

> The three functions (unique, divide, nub) seem related (all seem to deal
> with equivalence classes).  I would collect them under the same title in
> the LIST signature.
>   

    Sure.


>>          - A function »flattenOpt« on lists that returns the list of
>>          elements that exist in the list
>>
>>                  val flattenOpt : ('a Option.t) List.t -> 'a List.t
>>     
>
> Hmm... Is this just mapPartial id?  If it is, then I'm not sure whether to
> provide it.  It is not very common to need to create a list with option
> elements.  

  Yes, it would seem that this is equivalent to just using 
»mapPartial«/»mapPartial id«.

>>          - A function for lifting comparison to options
>>
>>                  val compareOpt : 'a Cmp.t -> 'a Option.t -> Order.t
>>     
>
> Sounds good.  I would call it Option.collate as in Alice ML
>
>   http://www.ps.uni-sb.de/alice/manual/library/option.html
>
> and use the spec
>
>   val collate : 'a Cmp.t -> 'a Option Cmp.t
>
>   

    Okay, I've revised my implementation to match this.


>>          - A structure for natural numbers (complex numbers might be
>>          useful as well.  It might also make sense to provide a generic
>>          »numeric« signature for operations that make sense for all sorts
>>          of numeric types (integers, reals, etc.).
>>     
>
> Yes, these sound like good additions.  I assume you mean arbitrary
> precision natural numbers.  
    Hmm.  I hadn't actually thought about using it for natural numbers 
that large, but that is probably the correct design choice.  It would 
probably also be useful to provide a kind of unary view of the natural 
numbers, but offhand I'm not sure if there is a standard idiom for 
faking »views« in Standard ML.

> I would consider implementing complex numbers
> as one or more functors.  About the signatures.  Yes, I agree it makes
> sense.  Writing "concept" signatures, as I call them, is on my list of
> things to do.
>   

    Sounds good.  I have some signatures for monads that may be worth 
including.


>>          - Lazy lists.  This would probably have a very similar signature
>>          to LIST (perhaps even just a superset) with an additional
>>          operation for creating infinite lists from a generating
>>          function.
>>     
>
> You mean like, IIRC, iterate in Haskell?  
    Yes.  

> Sounds basically good.  I assume
> that you are aware of the various design choices for implementing lazy
> lists (like whether to make them odd or even, whether to always memoize or
> not, etc...).  I've wanted to provide lazy lists, but haven't yet sorted
> out to what would be the best approach (if there is one) (I have a couple
> of variations on my hardrive).  
    I am aware of some possible choices, but I don't know (or remember) 
the tradeoffs.

> Also, I think many algorithms on lists,
> lazy lists and other sequences could be implemented as a functor to reduce
> duplication.  (But refactorings like that can also done later.)
>   

    It might actually be better to treat these as streams instead of 
lists.  A common ancestor signature might be shared between them and the 
various IO streams.

    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.

>>          - Association list operations.
>>     
>
> Sounds good.
>
>   
>> I'm not particularly tied to any of the names I'm using here, so open to 
>> changes that match the feel of the rest of the basis.
>>     
>
> See above for some suggestions.  I think that additions like you are
> suggesting would be good.  Next I'd like to see patches for a couple of
> additions.  Don't collect all additions to a single patch.  Have you
> considered asking for commit access to mltonlib?
>   

    I hadn't really thought about it, but I'm not sure whether my 
throughput is going to be enough to warrant it.  Right now most of the 
suggestions that I do have implemented were developed as part of my 
dissertation project, which has been keeping me busy enough as it is.  
Still, I'll try to send along some patches for a few things soon.  
Should I send them to you directly, or also CC the list?


-- 
[Geoff Washburn|geoffw at cis.upenn.edu|http://www.cis.upenn.edu/~geoffw/]

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mlton.org/pipermail/mlton-user/attachments/20070225/3c496607/attachment.htm