Re: project euler 26

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

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

> On 2023-09-08 03:32, Ben Bacarisse wrote:
>> "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:
>>>>>
>>>> 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.
>
> Why should it be? You wanted to find maximum of a function. Vector is
> not a function.

I wanted the maximum of a function over a collection (range, array, map,
etc).  In some languages, collections can be scanned so you don't need
to know where the data come from.

>>> 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.
>
> Yes, because you try too hard to make it work where it probably should
> not.

If you think a resuable Ada function that can find the maximum of some F
over some 'collection' X is possible, I'd like to see how it's done.  I
can do it for some kinds of X but I have no idea how general it can be
made in Ada.  I think the answer is either that it can't be very
general, or to make it very general is too much work, or that one should
not be trying in the first place.

(I put 'collection' in quotes because I know that's an Ada term but I
don't necessarily want to restrict the solution to how Ada uses the
term.  For example, I don't think native arrays are collections in the
formal Ada library sense.)

>> I don't think this is incoherent.  The Haskell libraries ensure that any
>> collection that is logically foldable is indeed foldable.
>
> Ada arrays and library containers do not share interfaces.

I was pretty sure that was the case.  Thanks for confirming.  I think
that means there can be no truly generic solution.  But maybe it's
possible at least for all container types in the library?  (But I note
that if you think it /shouldn't/ be done, I won't expect you to show me
how.)

> Should the language allow adding
> ad-hoc interfaces to existing types. Yes, and this is possible in Ada in
> some very uncomfortable AKA cumbersome way, which is why "finding maximum"
> is not a worthy abstraction in Ada.

I suspected one might have to extend the interfaces.  If a simple
abstraction (maximise F over X) does not have a simple representation,
it's not going to be worth it.  Just write a slightly different empty
test and loop each time you need to do it.

>>>> 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".
>
> In Ada a function can use anything visible at its declaration point and at
> the location of its body. You can even declare a function inside a
> recursively called function and let it see local variables of each
> recursive call, in effect having an infinite set of functions.

At the point where I want Period.Element I can write the (almost)
one-line function that takes a Cursor and returns Period(Element(C))
entirely mechanically.  Can't the compiler do that?

Note I'm not asking if it /should/ (it may not be "Ada-like" to do
that).  I'm just curious if there really is a technical reason it can't
be done.

>> That's a lot just to use something that is supposed to be reusable.
>
> [rant on]
> An Ada programmer would just write a loop.

Yes, that's fine.  Different languages have different objectives.  Just
write the empty range test and the loop you need for each kind of
collection.  That was definitely the way things were done in the 80s.

>> 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.
>
> As I said you think in a wrong direction of abstracting the language
> "finding maximum" rather than the problem space, e.g. generalization to
> other bases, other mathematical structures etc.

Generalising to an arbitrary base is local to the function that finds
the answer for one element.  It's an entirely separate axis of
generalisation to that of where the elements come from.

It's interesting to me that you consider one simply wrong and the other
natural.  In some languages the "wrong" one does not even merit
consideration as it's just there for free.  You can concentrate on the
other bases and other structures without worrying if the program will be
able to maximise over the collection in which they are stored.  (For
example, for polynomial residues, they can't come from a range like
2..999.)

I really do appreciate your help.  I would not have got off the ground
with generics without your examples.  Also, one thing I like about
Usenet is coming across people with very different ideas about
programming.  In this case, it seems to be about what is worth
generalising and what isn't.

-- 
Ben.