<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffee" text="#000000">
Vesa Karvonen wrote:<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> - 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
</pre>
</blockquote>
<pre wrap=""><!---->
This is called |< in Fn. There is also a Wiki page
<a class="moz-txt-link-freetext" href="http://mlton.org/InfixingOperators">http://mlton.org/InfixingOperators</a>
that introduces it. The Fold technique, which I'm also using,
<a class="moz-txt-link-freetext" href="http://mlton.org/Fold">http://mlton.org/Fold</a>
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.
</pre>
</blockquote>
<br>
This fine then, I just hadn't looked closely enough at the piping
operators.<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> - 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
</pre>
</blockquote>
<pre wrap=""><!---->
I assume the name is a typo. </pre>
</blockquote>
Right, copy and paste error.<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<pre wrap="">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.
</pre>
</blockquote>
See my comments for »partition«/»divide« below.<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> - 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
</pre>
</blockquote>
<pre wrap=""><!---->
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)
</pre>
</blockquote>
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. <br>
<br>
Providing »ByCmp« and »ByToInt« means that it would probably be
worthwhile to also provide some sorting functions<br>
<br>
val sortByCmp : 'a BinPr.t -> 'a t -> 'a t<br>
val sortByToInt : ('a -> Int.t) -> 'a t -> 'a t<br>
<br>
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<br>
<br>
val sortMerge : 'a BinPr.t -> 'a t -> 'a t<br>
val sortQuick : 'a BinPr.t -> 'a t -> 'a t<br>
val sortRadix : ('a -> Int.t) -> 'a t -> 'a t<br>
<br>
and so forth.<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> - 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
</pre>
</blockquote>
<pre wrap=""><!---->
Sounds good with similar worries. :) Maybe use a name like nubByEq to
allow for faster alternatives? </pre>
</blockquote>
Right, I've changed my signature, the implementation isn't
complete, to be<br>
<br>
val uniqueByEq : 'a BinPr.t -> 'a t UnPr.t<br>
val uniqueByCmp : 'a Cmp.t -> 'a t UnPr.t<br>
<br>
val divideByEq : 'a BinPr.t -> 'a t -> 'a t t<br>
val divideByCmp : 'a Cmp.t -> 'a t -> 'a t t<br>
<br>
val nubByEq : 'a BinPr.t -> 'a t -> 'a t<br>
val nubByCmp : 'a Cmp.t -> 'a t -> 'a t<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<pre wrap="">What about the name of unique?
</pre>
</blockquote>
<br>
I'm not sure what you mean. Do you mean an alternative to »unique«
or do you mean using the »ByFoo« convention?<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<pre wrap="">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.
</pre>
</blockquote>
<br>
Sure.<br>
<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> - 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
</pre>
</blockquote>
<pre wrap=""><!---->
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. </pre>
</blockquote>
<br>
Yes, it would seem that this is equivalent to just using
»mapPartial«/»mapPartial id«.<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> - A function for lifting comparison to options
val compareOpt : 'a Cmp.t -> 'a Option.t -> Order.t
</pre>
</blockquote>
<pre wrap=""><!---->
Sounds good. I would call it Option.collate as in Alice ML
<a class="moz-txt-link-freetext" href="http://www.ps.uni-sb.de/alice/manual/library/option.html">http://www.ps.uni-sb.de/alice/manual/library/option.html</a>
and use the spec
val collate : 'a Cmp.t -> 'a Option Cmp.t
</pre>
</blockquote>
<br>
Okay, I've revised my implementation to match this.<br>
<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> - 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.).
</pre>
</blockquote>
<pre wrap=""><!---->
Yes, these sound like good additions. I assume you mean arbitrary
precision natural numbers. </pre>
</blockquote>
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.<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<pre wrap="">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.
</pre>
</blockquote>
<br>
Sounds good. I have some signatures for monads that may be worth
including.<br>
<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> - 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.
</pre>
</blockquote>
<pre wrap=""><!---->
You mean like, IIRC, iterate in Haskell? </pre>
</blockquote>
Yes. <br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<pre wrap="">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). </pre>
</blockquote>
I am aware of some possible choices, but I don't know (or remember)
the tradeoffs.<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<pre wrap="">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.)
</pre>
</blockquote>
<br>
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.<br>
<br>
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 <br>
Basis, and whether the same rationale applies to the Extended Basis.<br>
<br>
<blockquote cite="mid:1171844769.45d8eea1d9fed@www1.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> - Association list operations.
</pre>
</blockquote>
<pre wrap=""><!---->
Sounds good.
</pre>
<blockquote type="cite">
<pre wrap="">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.
</pre>
</blockquote>
<pre wrap=""><!---->
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?
</pre>
</blockquote>
<br>
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?<br>
<br>
<br>
<pre class="moz-signature" cols="72">--
[Geoff Washburn|<a class="moz-txt-link-abbreviated" href="mailto:geoffw@cis.upenn.edu">geoffw@cis.upenn.edu</a>|<a class="moz-txt-link-freetext" href="http://www.cis.upenn.edu/~geoffw/">http://www.cis.upenn.edu/~geoffw/</a>]
</pre>
</body>
</html>