On Sat, 2013-01-19 at 14:56 -0800, Ben Wolfson wrote:
> > Such sets couldn't support forward domain transformation, though,
> > because membership testing could then fail to terminate.
>
> Given the definition of seq you suggested above, membership testing
> for a transformed map will also be in danger of not terminating.
> That's the only reason it's not observably incorrect.
Domain transformation need not be implemented with enumeration, as in
the case of vacuous domains, as it is not permitted for the transform to
do something like exclude keys that were present in the old domain.
> But fine---again, it's not clear to me why this makes the sets deficient.
You can test for membership of infinite sets like the even integers very
quickly. Once an arbitrary injection is applied, though, it is more
troublesome.
> > The only way you can apply both transformations is if your
> > domain is vacuous: that is, constant functions like yours are
> > the only ones that permit domain transform in either direction.
>
> [given, I assume, the proviso that the transformed result must be
> capable of further forward transformation?]
Of course. :)
> >> But in the end my more fundamental question is: what makes it the case
> >> that associatives can transform their domains forward? AFAICT the
> >> answer is "the enumerability of associatives".
> >
> > My previous email argued that the former implied the latter, rather than
> > vice versa. Forward domain transformation via injection seems more
> > fundamental than enumerability, to me.
>
> But there's a case where forward domain transformation is possible
> without (correct) enumeration being possible (you don't, contrary to
> what you said, need to produce the entire search space), which ought
> to scotch that direction of implication.
That's fair. The slightly stronger claim of Associative, then, is
useful for its exclusion of constant functions.
> > Because that definition of associative, "associating elements of a
> > domain with elements of a codomain", is entirely characterized by the
> > codomain of the associative -> function isomorphism.
Apologies, I should have said "monomorphism"; indeed, there are no
isomorphisms given the definitions I'm using :]
> > Such functions support containsKey, entryAt, assoc, and both
> > valAts.
>
> And without, too. Except that actually they don't support any of them:
>
> user=> (.containsKey even? 2)
> java.lang.IllegalArgumentException: No matching method found:
> containsKey for class clojure.core$even_QMARK_ (NO_SOURCE_FILE:0)
> user=> (get even? 2)
> nil
Yes; Clojure can't discriminate this kind of function, so implementing
even that subset of Associative I mentioned couldn't be done safely. We
can write them, though, applying the needed constraints ourselves if you
wish safety.
;; A total function whose codomain represents both boundedness and the
;; values of some other function.
(def-alias Kma (TFn [[x :variance :contravariant]
[y :variance :covariant]]
(Fn [x -> (Option (Vector* y))])))
(ann associative->kma
(All [a b] (Fn [(IPersistentMap a b) -> (Kma a b)])))
(defn associative->kma
"This is *the* associative -> function monomorphism, because it is
isomorphic to all other associative -> function monomorphisms."
[m]
(fn [k] (if-let [[_ v] (find m k)]
[v])))
(ann entry-at
(All [a b] (Fn [(Kma a b) a -> (Option (Vector* a b))])))
(defn entry-at
"As with entryAt."
[kma k]
(if-let [[v] (kma k)]
[k v]))
(ann val-at
(All [a b] (Fn [(Kma a b) a -> (Option b)]
[(Kma a b) a b -> b])))
(defn val-at
"As with valAt."
([kma k] (first (kma k)))
([kma k o] (if-let [[v] (kma k)]
v
o)))
(ann assoc'
(All [a b] (Fn [(Kma a b) a b -> (Kma a b)])))
(defn assoc'
"Preserves the earlier law suggested for assoc."
[kma k v]
(fn [k'] (if (= k k') [v] (kma k'))))
(ann contains?'
(All [a b] (Fn [(Kma a b) a -> Boolean])))
(defn contains?'
[kma k]
(if (kma k) true false)) ;yeah I know
> I suspect the implementation of assoc gains by not being e.g. (fn [m k
> v] #(if (= % k) v (m %))), not to mention the implementation of the
> maps themselves.
Agreed. However, a general assoc could detect when you are using a
specialized representation of function, preserving compatibility with
something like Kma.
> In very few cases, I think, has anyone thought "should I use a function
> or a map? Well, I need forward domain transformation, so, a map."
I imagine it goes on indirectly, that is to say "well, I need [some
implication of forward domain transformation], so, a map."
> * though one could imagine a reader macro to do the relevant transformation.
Aye, what is {}, after all?
> I don't really care about the name. If there were an interface
> IDomainToCodomain, I wouldn't complain that Associative extends
> IPersistentCollection and Seqable. (In fact, in that case, Associative
> could consist entirely in extending IDomainToCodomain and
> IPersistentCollection.
Since this interface — notwithstanding laziness — is characterized by
Kma, perhaps something about its structure provides some hint about the
name. Scala calls it PartialFunction, but I think this is somewhat
confusing.
Since constant functions can have their domains transformed forwards,
unlike Kma, perhaps it would be useful to also encode that in a
superinterface of wherever this hierarchy introduces Seqable again.
> If that separation were effected, then the decision whether to use a
> function or a not-a-function could be made on the basis of the strength
> of the guarantees one requires.
It would definitely make for a more powerful set of interfaces.
--
Stephen Compall
^aCollection allSatisfy: [:each|aCondition]: less is better
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
