Recursion and Backtracking in Haskell

Question

I decided to teach myself Haskell and tried to translate some code from Java to Haskell so I can get more familiar with recursion, backtracking and search tree pruning.

Java Code :

private static boolean isListOkay(ArrayList<Integer> numbers) {
    return listSum(numbers) == 8 && numbers.size() == 3;
}

private static int listSum(ArrayList<Integer> numbers) {

    int sum = 0;

    for (Integer number : numbers)
        sum += number;

    return sum;
}

public static ArrayList<Integer> sumTo8(ArrayList<Integer> numbers) {
    return sumTo8(numbers, 0, new ArrayList<Integer>());
}

private static ArrayList<Integer> sumTo8(ArrayList<Integer> numbers, int i, ArrayList<Integer> list) {

    if (isListOkay(list))
        return list;

    else if (i == numbers.size() && !isListOkay(list))
        return null;

    else if (listSum(list) > 8 || listSum(list) == 8 && list.size() != 3)
        return null;

    else {

        int currentNumber = numbers.get(i);

        ArrayList<Integer> pickIt = new ArrayList<>(list);
        pickIt.add(currentNumber);

        ArrayList<Integer> leaveIt = new ArrayList<>(list);

        ArrayList<Integer> pickItResult = sumTo8(numbers, i + 1, pickIt);

        if (pickItResult == null)
            return sumTo8(numbers, i + 1, leaveIt);

        return pickItResult;
    }


}

Haskell code :

listSumUtil :: [Int] -> Int -> Int
listSumUtil [] sum = sum
listSumUtil (x:xs) sum = x + y
  where y = listSumUtil xs sum

listSum :: [Int] -> Int
listSum list = listSumUtil list 0

sumTo8Util :: [Int] -> [Int] -> [Int]

sumTo8Util [] list
  | sum == 8 && listLength == 3 = list
  | otherwise = []
    where sum = listSum list
          listLength = length list

sumTo8Util (x:xs) l2 =
  if sum > 8 && listLength > 3 then []
  else if sum == 8 && listLength == 3 then l2
  else (if l3 == [] then l4 else l3)
    where sum = listSum l2
          listLength = length l2
          l3 = sumTo8Util xs pickIt
          pickIt = l2 ++ [x]
          l4 = sumTo8Util (x:xs) l2

sumTo8 :: [Int] -> [Int]
sumTo8 list = sumTo8Util list []

The Java code is working and I was able to compile the Haskell one. When I executed main though there was no output and it just kept running so there must be an infinite loop somewhere and here is where I need your help. How would one implement the exact Java code in Haskell ? Am I missing something in my implementation? As you see I avoided syntactic sugar in my Haskell code because I just started and can't understand it yet.

Update 1 :

Added the else if sum == 8 && listLength == 3 then l2 condition in Haskell code but still doesn't work.

Update 2 :

Found a way to do it.

Working code :

listSum :: [Int] -> Int
listSum list =  foldl (+) 0 list
  
insertAtEnd :: [Int] -> Int -> [Int]
insertAtEnd [] c = [c]
insertAtEnd (h:t) c = h : insertAtEnd t c  
  
sumTo8Util :: [Int] -> Int -> [Int] -> [Int]
sumTo8Util lst i rlst 
  | (length rlst == 3) && (listSum rlst == 8) = rlst
  | (i == length lst) && ((listSum rlst /= 8) || (length rlst /= 3)) = []
  | otherwise = if (length pickIt == 0) then (sumTo8Util lst (i+1) rlst) else pickIt
    where number = lst !! i
          nrlst =  insertAtEnd rlst number
          pickIt = sumTo8Util lst (i+1) nrlst 
  
sumTo8 :: [Int] -> [Int]
sumTo8 list = sumTo8Util list 0 []   

Basically I try to trigger backtrack by returning the empty list.

If there is an alternative that makes use of backtrack and is way more efficient than my code* feel free to suggest it.

*Pretty sure it will be as I've been teaching myself Haskell for a few days now

Answer 1

First, no need to reinvent the simplest of wheels:

listSum :: [Int] -> Int
listSum = sum
  
insertAtEnd :: [Int] -> Int -> [Int]
insertAtEnd xs c = xs ++ [c]
  
sumTo8 :: [Int] -> [Int]
sumTo8 list  =  helper list 0 [] 
  where
  helper :: [Int] -> Int -> [Int] -> [Int]
  helper lst i rlst 
   | (length rlst == 3) && (sum rlst == 8) = rlst
   | (i == length lst) && ((sum rlst /= 8) || (length rlst /= 3)) = []
   | otherwise = if (length pickIt == 0) 
                 then (helper lst (i+1) rlst) 
                 else pickIt
     where number = lst !! i
           pickIt = helper lst (i+1) (rlst ++ [number])

Second, no need to make sure not test is true when we've already established that test is false. And calculating the whole list's length just to check whether it is 0 or not is much better done testing whether the list is null:

sumTo8 :: [Int] -> [Int]
sumTo8 list  =  g list 0 [] 
  where
  g lst i rlst 
   | (length rlst == 3) && (sum rlst == 8)  =  rlst
   | (i == length lst)   =  []
   | null pickIt         =  g lst (i+1) rlst
   | otherwise           =  pickIt
     where 
          pickIt = g lst (i+1) (rlst ++ [lst !! i])

Third, using patterns is that much more visually apparent than calling functions; and most importantly, accessing ith element from the start of list, for growing i, is the same as advancing along the list and accessing its head -- but the latter is so much more efficient (linear process instead of quadratic):

sumTo8 :: [Int] -> [Int]
sumTo8 list  =  g list [] 
  where
  g _  rlst@[_,_,_] | sum rlst == 8  =  rlst
  g []     _             =  []
  g (n:ns) rlst 
   | null pickIt         =  g ns rlst
   | otherwise           =  pickIt
     where 
          pickIt = g ns (rlst ++ [n])

Fourth, producing an invalid answer to signal failure is very non-Haskellish.

In Haskell it is idiomatic to have types reflect the true nature of data.

Instead of returning -1 from a function which is contracted to only produce positive integers; or returning an empty list from a function which is supposed to produce three-element list as its result, in Haskell we put that result inside some sort of a container data type which signals to us the nature of its result in some specific way.

For instance there's this Maybe type which either wraps the result under its Just data constructor ("tag"), or uses Nothing for the special case of failure. Thus it is equivalent to having either one solution, or none.

We could restructure the code to do that, but instead, let's note that having one or no elements is a particular case of having several or none; which is captured by the list data type, so that [a] can represent having one solution a, [a,b] -- two solutions a and b, and [] can represent having no solutions.

Appending two lists together is done with ++ which just puts the elements of the second after all the elements of the first, in the new resulting list.

Indeed, producing just the very first solution is the same as taking the first solution from the list of all solutions:

sumTo8 :: [Int] -> [[Int]]
sumTo8 list  =  take 1 (g list [])
  where
  g _  rlst@[_,_,_] | sum rlst == 8  =  [rlst]
  g []     _     =  []
  g (n:ns) rlst  =  g ns (rlst ++ [n])
                    ++
                    g ns rlst

Fifth, why limit ourselves just to the very first one, in a language with lazy evaluation?

sumTo8 :: [Int] -> [[Int]]
sumTo8 list  =  g list []
  where
  g _  [a,b,c] | a+b+c == 8  =  [ [c,b,a] ]
  g []     _     =  []
  g (n:ns) rlst  =  g ns (n : rlst)   -- we either pick
                    ++                -- the current element
                    g ns rlst         -- or don't

Then when this list is explored lazily, that is equivalent to depth first search with backtracking.

Now the code is that much more clear so we can finally start seeing new opportunities for search pruning like keeping the current sum of the picked elements, aborting the futile branch earlier, when the running total is already over the target; or stop picking new elements when we already have three; etc.

The common theme being, advancing our knowledge gradually, so that we have some partial knowledge at each point on our journey, instead of blindly making choices and testing their validity only at the very end.