# [curry] Re: Recursion in Set Functions

From: Michael Hanus <mh_at_informatik.uni-kiel.de>
Date: Tue, 6 Jul 2021 18:20:55 +0200

Hi Andy,

I updated the documentation of CurryPP and the Curry tutorial in this
sense. For instance, I added a note to the section on default rules, see
https://www.informatik.uni-kiel.de/~curry/tutorial/html/curry-tutorial.Ch3.S5.html#SS6

I hope this suffices.

Thanks for your remarks,

Michael

On 05.07.21 19:18, Andy Jost wrote:
> Hi Michael,
>
> Thank you for the explanation. It makes sense, now. Please let me know if I can help in any way (e.g., by contributing or reviewing documentation changes).
>
> -Andy
>
> -----Original Message-----
> From: Michael Hanus <mh_at_informatik.uni-kiel.de>
> Sent: Monday, July 5, 2021 2:17 AM
> To: Andy Jost <ajost_at_synopsys.com>; 'curry_at_lists.RWTH-Aachen.DE' <curry_at_lists.RWTH-Aachen.DE>
> Subject: Re: [curry] Re: Recursion in Set Functions
>
> Hi Andy,
>
> after reading your first message, I realized the problem, but I must admit that the documentation is not satisfying. Since set functions are not part of the language syntax but implemented via a library, illegal uses are not immediately shown. For this purpose, the `curry-check` tool performs some checks. Actually, it reports a wrong use of set functions in your first example.
>
> Conceptually, for each n-ary function `f` there is a n-ary set function `f^set` returning the set of values for `f` applied to n argument values. With the set function library, `f^set` is written as (setn f).
>
> For top-level functions, this works as expected, but for local functions there is a problem. Since local functions are just syntactic sugar for top-level functions where additional arguments are passed (by the lambda lifting process), the arity of a local function is not obvious. Therefore, `setn` should never be applied to local functions. Although this property is not checked by the front end of PAKCS, it is checked by curry-check.
>
> Since the semantics of default rules is defined via set functions, they are only processed for top-level functions (i.e., adding them for local functions just define other operations).
> Thus, it is reasonable to check also this use by curry-check to avoid such mistakes...future work...
>
> Regards,
>
> Michael
>
> On 04.07.21 21:32, Andy Jost wrote:
>> After more experimentation, I have found the problem only occurs when
>> the auxiliary function is declared in a "where" clauses, as was done
>> in all of my attempts.  If I move all definitions to the file scope,
>> the programs work as I expect.  The attached program demonstrates this.
>>
>>
>>
>> Is this behavior expected?  My understanding is that the only
>> difference between the two declaration types is name visibility.  Am I wrong?
>>
>>
>>
>> Perhaps this issue is related to the use of default rules?  I didn't
>> see any mention, e.g., here
>> <https://urldefense.com/v3/__https://www.informatik.uni-kiel.de/*curry
>> /tutorial/tutorial.pdf__;fg!!A4F2R9G_pg!KToP9gm5b58_EwlCAbNYGCNKJEtDCHNPPSXKkOeh0vym-4gxan3bNbb-j--QT-Rkz8E\$ >, that they must be defined at file scope, but maybe that is necessary?
>>
>>
>>
>> -Andy
>>
>>
>>
>> *From:* Andy Jost
>> *Sent:* Saturday, July 3, 2021 3:44 PM
>> *To:* 'curry_at_lists.RWTH-Aachen.DE' <curry_at_lists.RWTH-Aachen.DE>
>> *Subject:* Recursion in Set Functions
>>
>>
>>
>> Hi,
>>
>>
>>
>> I have run into an unexpected (to me) behavior when using set
>> functions.  I want to write a function that calculates a "penalty"
>> that equals the number of times any character repeats three times in a
>> string.  For example, "aaaa" has penalty two, while "aabaa" has
>> penalty zero.
>>
>>
>>
>> I thought it might be fun to use a functional pattern, so I wrote the
>> following:
>>
>>
>>
>> penalty1 (b++[x,x,x]++e) = 1 + penalty1 (b++[x,x]++e)
>>
>> penalty1'default _ = 0
>>
>>
>>
>> Although this works, it scales as the factorial of the longest
>> substring of repeated characters.
>>
>>
>>
>> I thought I could improve it by introducing a set function and then
>> using selectValue to cut down the search space.  My idea was to
>> recursively remove one character from an arbitrary triple, repeating
>> until there are no more triples and counting the iterations.  Rather
>> than choosing every way to remove a character, I just want to choose
>> one of them.
>>
>>
>>
>> I tried coding this several ways (below), but each time the result is
>> "no value found."  I am using PAKCS 3.3.0.
>>
>>
>>
>> Is this the expected behavior?  Does it suggest a problem with the
>> implementation of set functions or with my understanding of them?  Can
>> anyone point towards a solution using functional patterns?  Other
>> methods -- e.g., a pure-Haskell solution -- are trivial, so there's no
>> need to point them out.
>>
>>
>>
>> Thanks,
>>
>> -Andy
>>
>>
>>
>>
>>
>> penalty2 pw = selectValue \$ (set1 aux) pw
>>
>>     where
>>
>>         aux (b++[x,x,x]++e) = 1 + penalty2 (b++[x,x]++e)
>>
>>         aux'default _ = 0
>>
>>
>>
>> penalty3 pw = selectValue \$ (set1 aux) pw
>>
>>     where
>>
>>         aux (b++[x,x,x]++e) = 1 + aux (b++[x,x]++e)
>>
>>         aux'default _ = 0
>>
>>
>>
>> penalty4 pw = let pw' = next pw in if pw' == [] then 0 else 1 +
>> penalty4 pw'
>>
>>     where
>>
>>         next pw' = selectValue \$ (set1 aux) pw'
>>
>>         aux (b++[x,x,x]++e) = b++[x,x]++e
>>
>>         aux'default _ = []
>>
>>
>>
>>
>> _______________________________________________
>> curry mailing list -- curry_at_lists.rwth-aachen.de To unsubscribe send
>> an email to curry-leave_at_lists.rwth-aachen.de
>> https://urldefense.com/v3/__https://lists.rwth-aachen.de/postorius/lis
>> ts/curry.lists.rwth-aachen.de__;!!A4F2R9G_pg!KToP9gm5b58_EwlCAbNYGCNKJ
>> EtDCHNPPSXKkOeh0vym-4gxan3bNbb-j--Q9Mt6Kp0\$
>>
> _______________________________________________
> curry mailing list -- curry_at_lists.rwth-aachen.de
> To unsubscribe send an email to curry-leave_at_lists.rwth-aachen.de
> https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
>
_______________________________________________
curry mailing list -- curry_at_lists.rwth-aachen.de
To unsubscribe send an email to curry-leave_at_lists.rwth-aachen.de
https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
Received on Di Jul 06 2021 - 18:21:41 CEST

This archive was generated by hypermail 2.3.0 : Do Jun 20 2024 - 07:15:14 CEST