[curry] Re: Recursion in Set Functions

From: Michael Hanus <mh_at_informatik.uni-kiel.de>
Date: Mon, 5 Jul 2021 11:16:33 +0200

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://www.informatik.uni-kiel.de/~curry/tutorial/tutorial.pdf>, 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://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 Mo Jul 05 2021 - 11:17:36 CEST

This archive was generated by hypermail 2.3.0 : Do Feb 01 2024 - 07:15:13 CET