"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> 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.

Thanks. I remember that now. Given Ada's preference for words, it's a
mysterious choice.

>> 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.

Sure, but ideally we want the error we decided on for this situation.
Since the intent is to be generic, it's a shame to get one error with
some instantiations and a different one with others.

>> 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.

Sure, but the hope was to write something that does not need new
code for new situations. That's what makes it reusable.

>> 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 definitely getting what I call cumbersome.

>> 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 core of my Haskell solution is just a function decimalRepeatLength
that returns the repeat length given a divisor. But once I'd got the
answer (by applying it to 2 to 999 and getting the maximum) I wondered
what would happen if the numbers were not in a simple range. Is it easy
to write a `maximisedOver` function that finds the maximum of some
function over any ordered collection (technically, a "foldable" type in
Haskell).

Well, yes, it is easy:

function `maximisedOver` anything = maximum (fmap function anything)

so the solution to the project Euler problem is just

decimalRepeatLength `maximisedOver` [2..999]

but I can also find the maximum of this (or any other suitable) function
over an array, a hash map, a vector... whatever. No code changes
anywhere. It even works with arrays of any number of dimensions
regardless of the index bounds.

maximisedOver is genuinely generic and reusable.

I don't think this is incoherent. The Haskell libraries ensure that any
collection that is logically foldable is indeed foldable.

>> 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.

What closure is required for a function composition? There is no
environment to "close over".

> 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.

This may be the closest we can get with Ada.

>> 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;

That's a lot just to use something that is supposed to be reusable.

>> 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.

It only occurred to me after writing the non-generic solution. I
remember Ada as being something of a pioneer in it's attempt to provide
generic solutions, so I wondered how far things had come. I don't think
something really widely reusable is possible in this case.

--
Ben.