Re: project euler 26

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

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