Re: project euler 26

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On 2023-09-07 01:32, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On 2023-09-06 17:16, Ben Bacarisse wrote:
>>
>>> I am curious to know how reusable this is.  Can the packages be
>>> instantiated in such a way that the argument ranges over the elements
>>> of, say, and Ordered_Map?
>>
>> Sure:
>>
>>     with Ada.Containers.Ordered_Maps;
>>
>>     package Integer_Maps is
>>        new Ada.Containers.Ordered_Maps (Integer, Integer);
>>     use Integer_Maps;
>>     package Cursor_Arguments is new Generic_Arguments (Cursor);
> 
> Ah!  So the arguments correspond to the "with" functions in the order
> listed, and, since Cursor already has Next, there no need to specify
> anything.

Yes, because the formal argument is

    with function Next (Value : Argument_Type)
       return Argument_Type is <>;

If it were

    with function Next (Value : Argument_Type)
       return Argument_Type;

You would have to specify the actual. The part "is <>" tells to match a 
visible function Next.

> There are a couple of details that prevent your Maximum_At function from
> working properly in this case though.  First, we can't have an empty
> map, because X.Last can't be compared with X.First when either is
> No_Element, so the test for Right < Left fails before the desired error
> can be raised.

Yes, cursors is bad idea, in the end they all are pointers. No_Element 
is an equivalent of null which shows.

However Maximum_At will propagate Constraint_Error if either of the 
bounds is No_Element. So the implementation would work.

> Second, if I try to use a Vector rather than an Ordered_Map, I am told
> that:
> 
> test2.adb:97:05: error: instantiation error at line 12
> test2.adb:97:05: error: no visible subprogram matches the specification for "<"
> 
> It would seem that vector cursors can't be compared using < (at least by
> default).  Maybe the installation needs more arguments.

Vector has a proper index type. All you have to do is. Given

    package Integer_Vectors is
       new Ada.Containers.Vectors (Integer, Integer);

Wrap Element into a function:

    V : Integer_Vectors.Vector;
    function Element (Index : Integer) return Integer is
    begin
       return V.Element (Index);
    end Element;
    ...

and use the wrapper.

> Anyway, I am still not sure how to write a generic test for an empty
> range.

The problem is that the implementation of Cursor that breaks 
abstraction. The abstraction of an argument does not permit ideal 
non-values. Cursors and pointers have non-values. So if you want to test 
for non-values ahead, instead of surprising the function, you need to 
add a test for value validity to the abstraction:

generic
    -- Ordered argument
    type Argument_Type is private;
    with function Valid (Value : Argument_Type) return Boolean is <>;
    ...
package Generic_Arguments is

Then you would pass Has_Element for it. For integers you would use 
wrapped X'Valid (there is no Integer'Valid, unfortunately. Only X'Valid 
where X is an object).

> It's possible I was not clear about what I was aiming for.  I was hoping
> to be able to find the maximum of some arbitrary function, taking the
> function's arguments from any sequential collection.

That is a different abstraction. You need a generic collection instead 
of generic ordered values. E.g.

generic
    with package Arguments is new Ada.Containers.Ordered_Sets (<>);
    with package Values is new Generic_Values (<>);
package Generic_Comparable_Valued is
    use Arguments, Values;
    function Maximum_At
             (  Domain : Set;
                Func : access function (Argument : Element_Type)
                       return Value_Type
             )  return Value_Type;
    -- Other useless functions
end Generic_Comparable_Valued;

package body Generic_Comparable_Valued is
    function Maximum_At
             (  Domain : Set;
                Func : access function (Argument : Element_Type)
                       return Value_Type
             )  return Value_Type is
       Max      : Value_Type;
       Value    : Value_Type;
       Position : Cursor;
    begin
       if Domain.Is_Empty then
          raise Constraint_Error with "Empty set";
       end if;
       Position := Domain.First;
       Max := Func (Element (Position));
       while Position /= Domain.Last loop
          Position := Next (Position);
          Value := Func (Element (Position));
          if Max < Value then
             Max := Value;
          end if;
       end loop;
       return Max;
    end Maximum_At;
end Generic_Comparable_Valued;

> Either a simple
> range of values, an array or vector of values, a list of values or even
> an ordered map of values -- any ordered list of values.

In practice such abstraction have too much physical and mental overhead. 
E.g. large sets of values implemented differently from 
Ada.Containers.Ordered_Sets depending on the operations required. For 
example, let you need a set complement? Usually programmers simply stick 
with software patterns instead. Too much reliance of libraries make 
programs incoherent.

> The bottom line is the last argument should be something very general
> like the Period function.
> 
> A fix (though it's not really ideal) would be to use function
> composition here (inventing . as the composition operator):
> 
>    Map_Functions.Maximum_At (X.First, X.Last, Period'Access . Element'Access)
> 
> but I don't think Ada has a function composition operator, does it?

No as it would require closures. So you can have a generic composition 
operator, no problem, but not a first-class one. However you can simply 
add Maximum_At with four arguments to the package.

> Another solution would be to write Maximum_At so that it knows it has a
> cursor argument, but then I don't think it would work for native arrays,
> would it?  And we'd loose plain ranges altogether.

You can write a generic package creating array cursors:

generic
    type Index_Type is (<>);
    type Element_Type is private;
    type Array_Type is array (Index_Type range <>) of Element_Type;
package Array_Cursors is
    type Cursor is private;
    function First (Container : Array_Type) return Cursor;
    function Element (Position : Cursor) return Element_Type;
    function "<" (Left, Right : Cursor) return Boolean;
    ...
private
    package Dirty_Tricks is
       new System.Address_To_Access_Conversions (Array_Type);
    use Dirty_Tricks;
    type Cursor is record
       Domain : Object_Pointer;
       Index  : Index_Type;
    end record;
end Array_Cursors;

package body Array_Cursors is
    function "<" (Left, Right : Cursor) return Boolean is
    begin
       if Left.Domain = null or else Left.Domain /= Right.Domain then
          raise Constraint_Error with "Incomparable cursors";
       end if;
       return Left.Index < Right.Index;
    end "<";

    function Element (Position : Cursor) return Element_Type is
    begin
       if Position.Domain = null or else
          Position.Index not in Position.Domain'Range
       then
          raise Constraint_Error with "Invalid cursor";
       else
          return Position.Domain (Position.Index);
       end if;
    end Element;

    function First (Container : Array_Type) return Cursor is
    begin
       if Container'Length = 0 then
          raise Constraint_Error with "Empty array";
       else
          return (To_Pointer (Container'Address), Container'First);
       end if;
    end First;

end Array_Cursors;

> But then (I think) the only function one could pass would be something
> like Element as in you example above.  Using an ordered set of integers
> would not allow
> 
>    Map_Functions.Maximum_At (Set.First, Set.Last, Period'Access)
> 
> would it?

Ordered_Set cursors are ordered like Ordered_Map ones, so it should work.

>>> I am asking you but I am also the group.  I appreciate your help,
>>> but don't want you to feel any obligation to keep helping!
>>
>> No problem.
> 
> You seem to be on your own as far as helping out is concerned!

Because it started as a numeric puzzle. You should have asked directly 
about generics or tagged types instead.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de