From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on ip-172-31-65-14.ec2.internal X-Spam-Level: X-Spam-Status: No, score=-3.2 required=3.0 tests=BAYES_00,NICE_REPLY_A, T_FILL_THIS_FORM_SHORT,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 Path: eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: project euler 26 Date: Thu, 7 Sep 2023 11:02:05 +0200 Organization: A noiseless patient Spider Message-ID: References: <878r9mudvj.fsf@bsb.me.uk> <87a5u1u1yv.fsf@bsb.me.uk> <8734ztttpc.fsf@bsb.me.uk> <87fs3ssl6v.fsf@bsb.me.uk> <87a5u0rts0.fsf@bsb.me.uk> <87jzt3qqlb.fsf@bsb.me.uk> <87o7ieq3ne.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Thu, 7 Sep 2023 09:02:05 -0000 (UTC) Injection-Info: dont-email.me; posting-host="3e4fde5204bf1fe9ab276fdba6340f70"; logging-data="3089928"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19G+JSG5ZU5CTeA/QI409dl05geV34nefo=" User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101 Thunderbird/102.15.0 Cancel-Lock: sha1:lELjRaGNb9vWkPe0cpNcugNaqiw= In-Reply-To: <87o7ieq3ne.fsf@bsb.me.uk> Content-Language: en-US Xref: news.eternal-september.org comp.lang.ada:65613 List-Id: 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 begin 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: 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 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 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: 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; > 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. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de