Haskell 中的递归和回溯

Question

我决定自学 Haskell 并尝试将一些代码从 Java 翻译成 Haskell 这样我就可以更熟悉递归、回溯和搜索树修剪。

Java代码：

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代码：

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 []

Java 代码正在运行，我能够编译 Haskell 代码。当我执行 main 时虽然没有输出并且它只是保持运行所以一定有一个无限循环的地方，这就是我需要你帮助的地方。如何在 Haskell 中实现确切的 Java 代码？我在实施中遗漏了什么吗？如您所见，我在我的 Haskell 代码中避免了语法糖，因为我刚开始，还不能理解它。

更新 1：

在 Haskell 中添加了 else if sum == 8 && listLength == 3 then l2 条件代码，但仍然不起作用。

更新 2：

找到方法了。

工作代码：

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 []

基本上我尝试通过返回空列表来触发回溯。

如果有使用回溯并且比我的代码更有效的替代方法*，请随时提出建议。

*很确定这将是因为我已经自学了几天 Haskell

Answer 1

首先，无需重新发明最简单的轮子：

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])

其次，当我们已经确定 test 为假时，无需确保 not test 为真。并且计算整个列表的 length 只是为了检查它是否为 0 更好地测试列表是否为 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])

第三，使用模式比调用函数更直观；最重要的是，从列表的开头访问第 i 个元素，以增加 i，与沿着列表前进并访问其 head 相同——但后者效率更高（线性过程而不是二次过程）：

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])

第四，对信号失败产生无效答案是非常非Haskellish。

在 Haskell 中，类型反映数据的真实性质是惯用的。

而不是从一个只产生正整数的函数返回 -1；或者从一个应该产生三元素列表作为结果的函数返回一个空列表，在 Haskell 中，我们将该结果放入某种容器数据类型中，该数据类型向我们表明其结果的性质具体方法

例如，有一个 Maybe 类型，它要么将结果包装在其 Just 数据构造函数（“标记”）下，要么使用 Nothing 来处理失败的特殊情况。因此，它相当于有一个解决方案，或者 none.

我们可以重组代码来做到这一点，但是，让我们注意，有一个或没有元素是具有多个或 none 的一种特殊情况；它由 list 数据类型捕获，因此 [a] 可以表示有一个解决方案 a、[a,b] -- 两个解决方案 a和b，[]可以表示无解。

将两个列表附加在一起是通过 ++ 完成的，它只是将第二个列表的元素放在第一个列表的所有元素之后，在新的结果列表中。

事实上，只生成第一个解决方案与从列表的所有个解决方案中获取第一个解决方案相同：

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

第五，为什么我们只局限于第一个，在一种惰性求值的语言中？

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

那么当这个列表被懒惰地探索时，这相当于带回溯的深度优先搜索。

现在代码更清晰了，所以我们终于可以开始看到搜索修剪的新机会，比如保持所选元素的当前总和，在运行总数已经达到时更早地中止无用的分支超过目标；或者当我们已经有了三个元素时停止选择新元素；等等

共同的主题是，逐步推进我们的知识，使我们在每个点上都有一些局部知识on our journey，而不是盲目地做出选择并在最后才检验其有效性。

Haskell 中的递归和回溯

Recursion and Backtracking in Haskell

haskell

recursion

functional-programming

backtracking

code-translation