How do I translate Prolog's cuts to Curry?

Question

Here's an algorithm in Curry which takes n and matches on two strings within edit distance n of each other.

lev :: Eq a => Int -> [a] -> [a] -> ()
lev n (a : b) (a : c) =
  lev n b c
lev n (_ : b) (_ : c) | n > 0 =
  lev (n - 1) b c
lev n (_ : b) c | n > 0 =
  lev (n - 1) b c
lev n b (_ : c) | n > 0 =
  lev (n - 1) b c
lev n [] [] =
  ()

This modifies the naive recursive algorithm so that we limit the number of edits we can try. Once we try n edits we give up.

If we translate this into Prolog we get

p(_, [], []).
p(N, [A|B], [A|C]) :-
  p(N, B, C).
p(N, [_|B], C) :-
  N>0,
  p(N-1, B, C).
p(N, B, [_|C]) :-
  N>0,
  p(N-1, B, C).
p(N, [_|B], [_|C]) :-
  N>0,
  p(N-1, B, C).

While these do limit the number of edits they can try, there is no limit to the branching factor. So it has exponential running time with respect to the size of the input. In Prolog I can fix this with a cut:

p(_, [], []).
p(N, [A|B], [A|C]) :-
  !, p(N, B, C).
p(N, [_|B], C) :-
  N>0,
  p(N-1, B, C).
p(N, B, [_|C]) :-
  N>0,
  p(N-1, B, C).
p(N, [_|B], [_|C]) :-
  N>0,
  p(N-1, B, C).

Now the branching factor is capped and this runs in linear time. However I can't make this same change in Curry since Curry lacks cuts.

What is the idiomatic Curry way to implement this?

Answer 1

Unfortunately, there is no "idomatic" way in Curry to achieve a cut, it depends on what you want to do. Most of the time, however, it is best to translate the corresponding non-deterministic, flexible pattern match into a rigid match. Here is what I came up with:

In your case, we want the decision between the first and second rule to be deterministic (not quite, I'll get to that).

Thus, we can move the decision into an if. Since we still want a flexible choice between the n > 0 rules, we can move that part of the match into a flexible case in the else branch.

lev2 _ []         []         = ()
lev2 n xs@(x : b) ys@(y : c) = 
  if x == y 
    then lev2 n b c 
    else case (xs, ys) of 
      (_ : b, _ : c) | n > 0 -> lev2 (n - 1) b c
      (_ : b, c    ) | n > 0 -> lev2 (n - 1) b c
      (b    , _ : c) | n > 0 -> lev2 (n - 1) b c    

Edit: The following was part of my original answer. For the revised question with a differently placed cut, the earlier part of this answer is sufficient. The rest is not required, but might serve as an example on how to translate a differently placed cut (p(N, [A|B], [A|C]) :- p(N,B,C), !.).

This solution, however, is not a faithful translation of the cut. In case that the recursive call to lev2 in the then branch produces no result, we currently do not try a different match. I assume that you do want to try a different one, so we can use encapsulation via set functions to check if the recursive call had a solution or not.

lev2 _ []         []         = ()
lev2 n xs@(x : b) ys@(y : c) = 
  if x == y 
   then let allSols = set0 (lev2 n b c) -- get set of all solutions
        in if notEmpty allSols         
             then selectValue allSols   -- choose (non-det) any value 
             else lev2' (xs, ys)        -- try the other matches in case of failure
   else lev2' (xs, ys)    
  where 
    lev2' (_ : b, _ : c) | n > 0 = lev2 (n - 1) b c
    lev2' (_ : b, c    ) | n > 0 = lev2 (n - 1) b c
    lev2' (b    , _ : c) | n > 0 = lev2 (n - 1) b c  

I know that this is not as elegant any more...

Note that I did not test if the performance is actually better, because I did not have the time to do it. But in my understanding it should be better.