<!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:
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap=""><!---->
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). </pre>
</blockquote>
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.<br>
<br>
However, I expect that in such cases they might best just implement
the best for their application themselves.<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">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).
</pre>
</blockquote>
<br>
Given these two specifications, which algorithms do you think you
would select?<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">
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.)
</pre>
</blockquote>
<br>
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.<br>
<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">The main reason I assumed arbitrary precision is that the Word types
already work like unsigned integers with modular arithmetic.
</pre>
</blockquote>
<br>
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.<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">
I recall one article with those keywords:
<a class="moz-txt-link-freetext" href="http://mlton.org/References#WangMurphy">http://mlton.org/References#WangMurphy</a> .
</pre>
</blockquote>
<br>
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 (<a class="moz-txt-link-freetext" href="http://mlton.org/Fold">http://mlton.org/Fold</a>) to provide nth projections and
injections with a single function? <br>
<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap=""><!---->
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.
</pre>
</blockquote>
[...]<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">
Contravariant functors are actually quite common. I don't particularly
like the name CFUNC, but I would prefer a short name.
</pre>
</blockquote>
These seem reasonable, but I haven't really thought much
abstracting anything to be a functor yet.<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">
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
</pre>
</blockquote>
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 <br>
<br>
signature BASIC_MONAD = sig<br>
type 'a t <br>
val return : 'a -> 'a t<br>
val >>= : 'a t * ('a -> 'b t) -> 'b t<br>
end<br>
<br>
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. <br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">
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. </pre>
</blockquote>
This is again essentially the same design I have been using.<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap=""> The MONAD signature is further split into two:
</pre>
</blockquote>
[...]<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">
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. </pre>
</blockquote>
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.<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">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.
</pre>
</blockquote>
<br>
I called them »zero« and ++. <br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">
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.
</pre>
</blockquote>
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. <br>
<br>
val fail : 'a monad<br>
val once : 'a monad -> 'a monad<br>
val ifte : 'a monad -> ('a -> 'b monad) -> 'b monad ->
'b monad<br>
<br>
The latter two are described in Kiselyov, Shan, Friedman, and Sabry
(<a class="moz-txt-link-freetext" href="http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf">http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf</a>) and
provide control over backtracking. »fail« aborts the computation
without any possibility for backtracking.<br>
<br>
Another variation I use is to actually give »zero« and »fail«
arguments<br>
<br>
type error<br>
val zero : error -> 'a monad<br>
val fail : error -> 'a monad<br>
<br>
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. <br>
<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">In addition to the above, I also have versions of the above signatures
with an extra type parameter:
</pre>
</blockquote>
[...]<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">Having two sets of signatures is a nuisance, but the extra type parameter
is needed often enough.
</pre>
</blockquote>
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 <br>
<br>
signature STATE_MONAD = sig<br>
include MONAD_CORE<br>
include MONAD_EX where type 'a monad_ex = 'a monad<br>
type state<br>
val getState : state monad<br>
val setState : state -> unit monad<br>
val run : state -> 'a monad -> 'a monad <br>
end<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">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
<a class="moz-txt-link-freetext" href="http://homepages.inf.ed.ac.uk/wadler/papers/lazyinstrict/lazyinstrict.ps">http://homepages.inf.ed.ac.uk/wadler/papers/lazyinstrict/lazyinstrict.ps</a>
and SRFI-45
<a class="moz-txt-link-freetext" href="http://srfi.schemers.org/srfi-45/srfi-45.html">http://srfi.schemers.org/srfi-45/srfi-45.html</a>
are relevant here. Memoization also has a cost and sometimes you might
want to avoid it.
</pre>
</blockquote>
I've printed these out to read over. Thanks.<br>
<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<blockquote type="cite">
<pre wrap=""> 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.
</pre>
</blockquote>
<pre wrap=""><!---->
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.
</pre>
</blockquote>
Sounds reasonable. Given that it is probably worth considering
some additional container signatures. Sets and maps at the very least.<br>
<br>
<blockquote cite="mid:1172437241.45e1f8f9f12af@www3.helsinki.fi"
type="cite">
<pre wrap="">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.
</pre>
</blockquote>
<br>
Stephen gave me commit access, but I will run patches by the list
before making significant changes.<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>