Re: project euler 26

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

On 2023-09-09 02:25, Ben Bacarisse wrote:
> "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:
>>>>>
> 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.

Hmm, the thing we discussed was a maximum element in array or map rather 
than a maximum of a function over the *domain* set of array or map. In a 
typed language array /= domain of array.

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

To start with, no such function exists. Not in a typed language. Note 
that a generic function is not a function. So instead we must consider 
language constructs for the purpose. Generic instantiation is one of 
them, some class might be another, but in Ada we just use loops. (And 
yes, people liking writing programs while standing on their heads, may 
use recursion... (:-))

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

The limits of generality are defined by the interfaces. In Ada types are 
designed to implement needed interfaces upfront. If you want to do that 
after the fact, you need some other adapter types to shove an existing 
type into something it was not designed for.

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

If a library is designed with this purpose in mind, that is trivial as 
you just pointed out. All collection types in the library would 
implement the required interface. End of story.

> (But I note
> that if you think it /shouldn't/ be done, I won't expect you to show me
> how.)

That is not a language question. It is a question of the library design. 
What if the library did not follow the desired design? That would be a 
language question and Ada offers some means, but not enough from my 
point of view due to the limitation of its type system.

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

You cannot in a strongly typed language without breaking too much 
things. You must create another type related to the old one and 
implementing the new interface (superclass). That would do the trick. 
Ada cannot this, so you go for the poor man's substitute: a mix-in. I.e. 
you create a new type that references an object of the old type. E.g. 
see array cursors example in my earlier post.

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

No.

(Ada indeed composes functions in some limited number of cases, e.g. an 
explicit type conversion of [in] out arguments. But these are predefined.)

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

Actually compositions might be useful in many cases and adapting 
interfaces is one of them.

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

You can loop in Ada over empty ranges, no problem.

> That was definitely the way things were done in the 80s.

Yes, before the Dark Ages of Computing...

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

Because one is a software design artifact and another is the result of 
problem space analysis.

> In some languages the "wrong" one does not even merit
> consideration as it's just there for free.

Being a part of design it has all possible merits to consider and then 
reject it. That is in the position of a puzzle solver. Now in the 
position of a library designer, the Ada standard library has an 
[informal] interface that supports what you wanted:

1. Cursor
2. Key at the cursor
3. Element at the cursor
4. Iterate procedure

So, for the Ada standard library it might look like this:

generic
    type Container_Type (<>) is limited private;
    type Element_Type is private;
    type Key_Type is private;
    type Cursor_Type is private;
    with function "<" (Left, Right : Element_Type) return Boolean is <>;
    with function Key (Position : Cursor_Type) return Key_Type is <>;
    with function Element
                  (  Position  : Cursor_Type
                  )  return Element_Type is <>;
    with procedure Iterate
                   (  Container : Container_Type;
                      Process   : not null access procedure
                                  (Position : Cursor_Type)
                   )  is <>;
function Generic_Container_Maximum_At (Container : Container_Type)
    return Key_Type;

function Generic_Container_Maximum_At (Container : Container_Type)
    return Key_Type is
    Found  : Boolean := False;
    Max    : Element_Type;
    Result : Key_Type;
    procedure Walker (Position : Cursor_Type) is
    begin
       if Found then
          if Max < Element (Position) then
             Result := Key (Position);
             Max    := Element (Position);
          end if;
       else
          Result := Key (Position);
          Max    := Element (Position);
          Found  := True;
       end if;
    end Walker;
begin
    Iterate (Container, Walker'Access);
    if Found then
       return Result;
    else
       raise Constraint_Error with "Empty container";
    end if;
end Generic_Container_Maximum_At;

Instantiation:

    package Integer_Maps is
       new Ada.Containers.Ordered_Maps (Integer, Integer);
    use Integer_Maps;
    function Integer_Map_Max is
       new Generic_Container_Maximum_At (Map, Integer, Integer, Cursor);

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