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 _ = []
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., herehttps://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@lists.RWTH-Aachen.DE' curry@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 _ = []
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@lists.RWTH-Aachen.DE' curry@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@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@lists.rwth-aachen.de https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
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@informatik.uni-kiel.de Sent: Monday, July 5, 2021 2:17 AM To: Andy Jost ajost@synopsys.com; 'curry@lists.RWTH-Aachen.DE' curry@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@lists.RWTH-Aachen.DE' curry@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@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@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$
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/%7Ecurry/tutorial/html/curry-tutorial.Ch3...
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@informatik.uni-kiel.de Sent: Monday, July 5, 2021 2:17 AM To: Andy Jost ajost@synopsys.com; 'curry@lists.RWTH-Aachen.DE' curry@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@lists.RWTH-Aachen.DE' curry@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@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@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@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@lists.rwth-aachen.de https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
-
Andy Jost -
Michael Hanus