[m-users.] How to declare a set of typeclasses?

[Sean Charles (emacstheviking)]

OK, I have fixed it all and made it compile and amazingly it works, here's what I had to do, a great learning experience this evening for sure.

:- pred collisions_between2(
    coll_type::in, % Check
    list(S)::in,   % Shots0
    list(T)::in,   % Targets0
    list(S)::out,  % Shots
    list(T)::out   % Targets
) is det <= ( hittable(S), hittable(T) ).

%
% ideal: two list of things, none with hit flags set, actuall, indifferent.
% on exit: two NEW list of list, some with hit flags set, some without.
%
collisions_between2(Check, Shots0, Targets0, Shots, Targets) :-
    list.foldl2(
        outer(Check, Targets0),
        Shots0,
        set.init:set(S), Shots1,
        set.init:set(T), Targets1
    ),
    Shots   = set.to_sorted_list(Shots1),
    Targets = set.to_sorted_list(Targets1),
    trace [io(!IO)] (
        io.format("COLL2: Shots: %i\n", [i(list.length(Shots))], !IO),
        io.format("COLL2: Targs: %i\n", [i(list.length(Targets))], !IO)
    ).

:- pred outer(
    coll_type::in,           % Check
    list(T)::in,             % Targets (Targets0 from caller)
    S::in,                   % Shot
    set(S)::in, set(S)::out, % !L1acc
    set(T)::in, set(T)::out  % !L2acc
) is det <= ( hittable(S), hittable(T) ).

outer(Check, Targets, Shot, !L1acc, !L2acc) :-
    list.foldl2(
        inner(Check, Shot),
        Targets,
        !L1acc,
        !L2acc
    ).

:- pred inner(
    coll_type::in,          % Check
    S::in,                   % Shot
    T::in,                   % Target
    set(S)::in, set(S)::out, % L1acc
    set(T)::in, set(T)::out  % !L2acc
) is det <= ( hittable(S), hittable(T) ).

inner(Check, Shot, Target, !L1acc, !L2acc) :-
    ( if did_collide(Check, Shot, Target) then
        set_hit(Shot, Shot1),
        set_hit(Target, Target1),
        set.insert(Shot1, !L1acc),
        set.insert(Target1, !L2acc)
    else
        set.insert(Shot, !L1acc),
        set.insert(Target, !L2acc)
    ).

The only mystery is that I didn't have to provide the `equality` predicate as described in "8 User-defined equality and comparison" of the referece.
So what did mercury do for me that I didn't have to do.

Would it be more efficient if, for each of my DU types that implements the hittable typeclass also proved an implementation of `where equality...` and returned the simple internal integer index assigned to it, guaranteed unique for the entire game session?


Thanks for everybody helping me out.
Sean.


> On 11 Oct 2023, at 22:16, Sean Charles (emacstheviking) <objitsu at gmail.com> wrote:
> 
> collisions_between2(Check, Shots0, Targets0, Shots, Targets) :-
>     Outer = (pred(
>         Shot::in,
>         !.S::in, !:S::out,
>         !.T::in, !:T::out
>     ) is det <= (hittable(S), hittable(T)) :-
>         Inner = (pred(
>             Target::in,
>             !.S::in, !:S::out,
>             !.T::in, !:T::out
>         ) is det <= (hittable(S), hittable(T)) :-
>             ( if did_collide(Check, Shot, Target)
>             then
>                 set_hit(Shot, Shot1),
>                 set_hit(Target, Target1),
>                 set.insert_new(Shot1, !S),
>                 set.insert_new(Target1, !T)
>             else
>                 set.insert_new(Shot, !S),
>                 set.insert_new(Target, !T)
>             )
>         ),
>         list.foldl2(Inner, Targets0, !S, !T)
>     ),
>     list.foldl2(
>         Outer, Shots0,
>         set.init:set(S), ShotsX,
>         set.init:set(T), TargetsX
>     ),
>     trace [io(!IO)] (
>         io.format("COLL2: Shots: %i\n", [i(list.length(Shots))], !IO),
>         io.format("COLL2: Targs: %i\n", [i(list.length(Targets))], !IO)
>     ).
> 
> Errors:
> 
> level_ufo.m:809: Error: the clause head part of a lambda expression should have
> level_ufo.m:809:   one of the following forms: `pred(<args>) is <determinism>'
> level_ufo.m:809:   `any_pred(<args>) is <determinism>'
> level_ufo.m:809:   `func(<args>) = <retarg> is <determinism>'
> level_ufo.m:809:   `any_func(<args>) = <retarg> is <determinism>'
> level_ufo.m:809:   `func(<args>) = <retarg>'
> level_ufo.m:809:   `any_func(<args>) = <retarg>',
> level_ufo.m:809:   or one of those forms preceded by either `semipure' or
> level_ufo.m:809:   `impure'.
> 
> It doesn't seem like it is acceptable on a lambda expression, so will I have to break this code out into discrete predicates?
> 
> 
> 
>> On 10 Oct 2023, at 23:42, Zoltan Somogyi <zoltan.somogyi at runbox.com> wrote:
>> 
>> 
>> On 2023-10-11 09:19 +11:00 AEDT, "Sean Charles (emacstheviking)" <objitsu at gmail.com> wrote:
>>> Then I did what I thought would work:
>>> 
>>> :- type l1_set(T) == set(hittable(T)) <= hittable(T).
>> 
>> If what you are after is "the type of a set of things where each thing is hittable",
>> what you need to do is to simply use "set(T)" where you want this, *and*
>> add the typeclass constraint "<= hittable(T)" to the declarations of the
>> predicates and functions where such an argument appears. For an example,
>> have a look at e.g. sparse_bitset.m in the standard library.
>> 
>>> And here is the actual code where I am trying to use it, I am operating on the assumption
>>> that by default Mercury has some way of creating a unique hash for each object
>> 
>> That assumption is incorrect. The int.m, uint.m and string.m modules
>> of the standard library define hash functions, but for other types,
>> providing a hash function is up to you. And while there exist algorithms
>> for creating perfect hash functions (i.e. hash functions that don't generate
>> any collisions on a given set of input values),
>> 
>> - they guarantee the absence of collisions *only* for that set of values,
>> - they require the values of that set to be specified in advance,
>> - and even then they fail to generate a hash function for some sets.
>> 
>> Even cryptographically secure hash functions can have collisions.
>> The pigeon-hole principle guarantees this for any hash function
>> that generates a hash value of a fixed size for inputs of unbounded size.
>> 
>>> Ah.. it is section 3.8 of the online page https://mercury-in.space/crash.html#orga13c54a
>> 
>> That section does not talk about hashing.
>> 
>> Zoltan.
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurylang.org/archives/users/attachments/20231011/ac2bae32/attachment.html>