[curry] Re: Recursion in Set Functions

From: Andy Jost <Andrew.Jost_at_synopsys.com>
Date: Sun, 4 Jul 2021 19:32:56 +0000

After more experimentation, I have found the problem only occurs when the a=
uxiliary function is declared in a "where" clauses, as was done in all of m=
y 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 be=
tween 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 an=
y mention, e.g., here<https://www.informatik.uni-kiel.de/~curry/tutorial/tu=
torial.pdf>, that they must be defined at file scope, but maybe that is nec=
essary?

-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 numbe=
r of times any character repeats three times in a string. For example, "aa=
aa" has penalty two, while "aabaa" has penalty zero.

I thought it might be fun to use a functional pattern, so I wrote the follo=
wing:

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 s=
electValue 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 rem=
ove a character, I just want to choose one of them.

I tried coding this several ways (below), but each time the result is "no v=
alue found." I am using PAKCS 3.3.0.

Is this the expected behavior? Does it suggest a problem with the implemen=
tation of set functions or with my understanding of them? Can anyone point=
 towards a solution using functional patterns? Other methods -- e.g., a pu=
re-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 + pen=
alty4 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

Received on Mo Jul 05 2021 - 11:17:11 CEST

This archive was generated by hypermail 2.3.0 : Sa Sep 18 2021 - 07:38:49 CEST