Re: project euler 26

[Ben Bacarisse <ben.usenet@bsb.me.uk>]

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

> On 2023-09-06 03:10, Ben Bacarisse wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>> 
>>> On 2023-09-05 17:18, Ben Bacarisse wrote:
>>>
>>>> There was
>>>> boiler plate code in my program that could be abstracted out into a
>>>> generic function (or package?) so that any function can be maximised
>>>> over some range or, better yet, any iterable type (if that's how Ada
>>>> does things).
>>>
>>>> Can someone here show me how?
>>>
>>> You define some classes. Either generic or tagged. E.g. a generic class of
>>> functions that uses two generic classes of the argument and the value:
>>>
>>> generic
>>>     -- Ordered argument
>>>     type Argument_Type is private;
>>>     with function Next (Value : Argument_Type)
>>>        return Argument_Type is <>;
>>>     with function "<" (Left, Right : Argument_Type)
>>>        return Boolean is <>;
>>>     with function "=" (Left, Right : Argument_Type)
>>>        return Boolean is <>;
>>>     -- Comparable value
>>>     type Value_Type is private;
>>>     with function "<" (Left, Right : Value_Type ) return Boolean is <>;
>>>     -- Function type
>>>     with function Func (Argument : Argument_Type) return Value_Type;
>>> function Generic_Maximum_At (Left, Right : Argument_Type)
>>>     return Value_Type;
>>>
>>> and the implementation
>>>
>>> function Generic_Maximum_At (Left, Right : Argument_Type)
>>>     return Value_Type is
>>>     Argument : Argument_Type := Left;
>>>     Max      : Value_Type;
>>>     Value    : Value_Type;
>>> begin
>>>     if Right < Left then
>>>        raise Constraint_Error with "Empty interval";
>>>     end if;
>>>     Max := Func (Argument);
>>>     while not (Argument = Right) loop
>>>        Argument := Next (Argument);
>>>        Value := Func (Argument);
>>>        if Max < Value then
>>>           Max := Value;
>>>        end if;
>>>     end loop;
>>>     return Max;
>>> end Generic_Maximum_At;
>>>
>>> or you can choose to pass the function as an argument:
>>>
>>> generic
>>>     -- Ordered argument
>>>     type Argument_Type is private;
>>>     with function Next (Value : Argument_Type)
>>>        return Argument_Type is <>;
>>>     with function "<" (Left, Right : Argument_Type)
>>>        return Boolean is <>;
>>>     -- Comparable value
>>>     type Value_Type is private;
>>>     with function "<" (Left, Right : Value_Type) return Boolean is <>;
>>> function Generic_Maximum_At
>>>           (  Left, Right : Argument_Type;
>>>              Func : access function (Argument : Argument_Type)
>>>                     return Value_Type
>>>           )  return Value_Type;
>>>
>>> Or you can make it a package which is usually a better choice as one can
>>> pack into it several entities sharing the same generic interface:
>>>
>>> generic
>>>     -- Ordered argument
>>>     type Argument_Type is private;
>>>     with function Next (Value : Argument_Type)
>>>        return Argument_Type is <>;
>>>     with function "<" (Left, Right : Argument_Type )
>>>        return Boolean is <>;
>>>     with function "=" (Left, Right : Argument_Type)
>>>        return Boolean is <>;
>>>     -- Comparable value
>>>     type Value_Type is private;
>>>     with function "<" (Left, Right : Value_Type) return Boolean is <>;
>>> package Generic_Discrete_Comparable_Valued is
>>>     function Maximum_At
>>>              (  Left, Right : Argument_Type;
>>>                 Func : access function (Argument : Argument_Type)
>>>                        return Value_Type
>>>              )  return Value_Type;
>>>     -- Other useless functions
>>> end Generic_Discrete_Comparable_Valued;
>>>
>>> The generic classes of arguments/values can be in turn factored out into
>>> reusable generic packages:
>>>
>>> generic
>>>     -- Ordered argument
>>>     type Argument_Type is private;
>>>     with function Next (Value : Argument_Type) return Argument_Type is <>;
>>>     with function "<" (Left, Right : Argument_Type) return Boolean is <>;
>>>     with function "=" (Left, Right : Argument_Type) return Boolean is <>;
>>> package Generic_Arguments is
>>> end Generic_Arguments;
>>>
>>> generic
>>>     -- Comparable value
>>>     type Value_Type is private;
>>>     with function "<" (Left, Right : Value_Type ) return Boolean is <>;
>>> package Generic_Values is
>>> end Generic_Values;
>>>
>>> generic
>>>     with package Arguments is new Generic_Arguments (<>);
>>>     with package Values is new Generic_Values (<>);
>>> package Generic_Discrete_Comparable_Valued is
>>>     use Arguments, Values;
>>>     function Maximum_At
>>>              (  Left, Right : Argument_Type;
>>>                 Func : access function (Argument : Argument_Type)
>>>                        return Value_Type
>>>              )  return Value_Type;
>>>     -- Other useless functions
>>> end Generic_Discrete_Comparable_Valued;
>> Thank you.  I can't yet see how to use any of these alternatives, but
>> that's my problem.
>
> It is pretty much straightforward. E.g. the last one:

Sure, but I am new to Ada.  Well actually I first wrote Ada in the early
80s, but the project didn't go with Ada (too new I suspect) so reading
one book was the extent of my learning.

>    package Arguments is new Generic_Arguments (Integer, Integer'Succ);
>    package Values is new Generic_Values (Integer);

I'd probably choose more generic names for the packages since these are
more general than the names suggest.  I might go with Generic_Enumerated
(since it has 'Next') and Generic_Ordered.

Just to test I knew what was going on, I changed 'while not (Argument =
Right)' to 'while Argument < Right' so as to remove the need for having
an "=" function.  I doubt there are any types with "<" but not "=" but I
wanted to confirm I understood the code.

>    package Functions is
>       new Generic_Discrete_Comparable_Valued (Arguments, Values);
>
>
> Now you can print the maximum of your Period function:
>
>    Put_Line
>    (  "Max at"
>    &  Integer'Image (Functions.Maximum_At (2, 999, Period'Access))
>    );

Thanks.

(A minor issue: to meet the specification we either need 1000 here or
the loop needs to be changed to include the upper bound (like the for
loop did in the original).  Whilst it's easy to pass "one past the top
index" for Integer and so on, if the code can be made more generic it
would have to use all the values in the range because Ada has not done
the C++ hack of having XXX.end() be an iterator "one past" the actual
end of a range.)

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?  In some languages (C++!) one could pass a
pair of iterators here (cursors, I think in Ada-speak).  I tried to do
that but I don't think Ada's cursors are ordered by < though they do
have a Next function.  And if that method does work (it's quite likely
it was only my ignorance of the language that stopped it working) would
it work for built-in arrays which don't seem to have cursors.

Maybe a more generic a solution would involve passing something that can
be iterated over, rather than two values of an "enumerated" type?  I
mean enumerated in the mathematical sense -- it may be the wrong word in
Ada.

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!

>> Are there any good online sources on Ada generic
>> programming so I can find out how to implement and use this short of
>> package?
>
> Actually I provided an implementation above. Here it is again:

Sorry, missed that first time round.

-- 
Ben.