help / color / mirror / Atom feed
From: "Dmitry A. Kazakov" <>
Subject: Re: project euler 26
Date: Thu, 7 Sep 2023 11:02:05 +0200	[thread overview]
Message-ID: <udc3id$2u9g8$> (raw)
In-Reply-To: <>

On 2023-09-07 01:32, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <> 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.

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

> 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
       return V.Element (Index);
    end Element;

and use the wrapper.

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

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

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

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

    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;
    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
       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
       if Position.Domain = null or else
          Position.Index not in Position.Domain'Range
          raise Constraint_Error with "Invalid cursor";
          return Position.Domain (Position.Index);
       end if;
    end Element;

    function First (Container : Array_Type) return Cursor is
       if Container'Length = 0 then
          raise Constraint_Error with "Empty array";
          return (To_Pointer (Container'Address), Container'First);
       end if;
    end First;

end Array_Cursors;

> But then (I think) the only function one could pass would be something
> like Element as in you example above.  Using an ordered set of integers
> would not allow
>    Map_Functions.Maximum_At (Set.First, Set.Last, Period'Access)
> would it?

Ordered_Set cursors are ordered like Ordered_Map ones, so it should work.

>>> 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!
>> No problem.
> 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.

Dmitry A. Kazakov

  reply	other threads:[~2023-09-07  9:02 UTC|newest]

Thread overview: 40+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-09-04  9:19 project euler 26 CSYH (QAQ)
2023-09-04 11:06 ` Niklas Holsti
2023-09-04 12:39   ` Dmitry A. Kazakov
2023-09-04 16:01     ` Ben Bacarisse
2023-09-04 19:20       ` Dmitry A. Kazakov
2023-09-04 20:18         ` Ben Bacarisse
2023-09-04 21:00           ` Dmitry A. Kazakov
2023-09-04 23:16             ` Ben Bacarisse
2023-09-05  7:23               ` Dmitry A. Kazakov
2023-09-05 15:18                 ` Ben Bacarisse
2023-09-05 17:08                   ` Dmitry A. Kazakov
2023-09-06  1:10                     ` Ben Bacarisse
2023-09-06  7:06                       ` Dmitry A. Kazakov
2023-09-06 15:16                         ` Ben Bacarisse
2023-09-06 15:54                           ` Dmitry A. Kazakov
2023-09-06 23:32                             ` Ben Bacarisse
2023-09-07  9:02                               ` Dmitry A. Kazakov [this message]
2023-09-08  1:32                                 ` Ben Bacarisse
2023-09-08  7:23                                   ` Dmitry A. Kazakov
2023-09-09  0:25                                     ` Ben Bacarisse
2023-09-09  9:32                                       ` Dmitry A. Kazakov
2023-09-10  1:20                                         ` Ben Bacarisse
2023-09-10  8:46                                           ` Dmitry A. Kazakov
2023-09-10 19:22                                             ` Ben Bacarisse
2023-09-11  6:53                                               ` Dmitry A. Kazakov
2023-09-11 16:13                                                 ` Ben Bacarisse
2023-09-12  7:17                                                   ` Dmitry A. Kazakov
2023-09-13 12:24                                                     ` Ben Bacarisse
2023-09-14  6:33                                                       ` Dmitry A. Kazakov
2023-09-14 14:30                                                         ` Ben Bacarisse
2023-09-08  6:09                               ` G.B.
2023-09-08 21:02                                 ` Ben Bacarisse
2023-09-09  8:13                                   ` G.B.
2023-09-09 21:04                                     ` Ben Bacarisse
2023-09-10  9:11                                     ` Dmitry A. Kazakov
2023-09-05 17:35                 ` moi
2023-09-04 14:23 ` Dmitry A. Kazakov
2023-09-07  7:31 ` Francesc Rocher
2023-09-15  9:07   ` CSYH (QAQ)
2023-09-19  7:59     ` comp.lang.ada
replies disabled

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox