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=-1.9 required=3.0 tests=BAYES_00,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: Ben Bacarisse Newsgroups: comp.lang.ada Subject: Re: project euler 26 Date: Fri, 08 Sep 2023 02:32:00 +0100 Organization: A noiseless patient Spider Message-ID: <8734zpo3fz.fsf@bsb.me.uk> 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 Injection-Info: dont-email.me; posting-host="b39237310d6b9749d50605be679823cd"; logging-data="3353710"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+lNG/gOXpyQNl8hCFtHpS5bmPpZW6FgNc=" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.2 (gnu/linux) Cancel-Lock: sha1:VA7mSM6RR1yC0et/H0ccopaN9vE= sha1:frIkL3EMPPkqYVarZuapZsrTgwY= X-BSB-Auth: 1.1114e8f5b2bcbb70f427.20230908023201BST.8734zpo3fz.fsf@bsb.me.uk Xref: news.eternal-september.org comp.lang.ada:65618 List-Id: "Dmitry A. Kazakov" writes: > 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. 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.