我决定自学Haskell,并尝试将一些代码从Java翻译成Haskell,这样我就可以更熟悉递归,回溯和搜索树修剪。
爪哇代码 :
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;
}
}
哈斯克尔代码:
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 :
添加了else 如果总和 == 8 && 列表长度 == 3 则 Haskell 中的 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 []
基本上,我尝试通过返回空列表来触发回溯。
如果有另一种方法可以利用回溯并且比我的代码*更有效,请随时提出建议。
*很确定它会,因为我已经自学了几天的哈斯克尔
首先,无需重新发明最简单的轮子:
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
,与沿着列表前进并访问其头部相同 - 但后者更有效(线性过程而不是二次过程):
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中,让类型反映数据的真实性质是惯用的。
在Haskell中,我们不是从收缩为仅产生正整数的函数返回-1
;也不是从应该产生三元素列表作为结果的函数返回空列表,而是将该结果放入某种容器数据类型中,该数据类型以某种特定方式向我们发出其结果的性质。
例如,有这种Maybe
类型,它要么将结果包装在其Just
数据构造函数("标记")下,要么将Nothing
用于失败的特殊情况。因此,它相当于有一个解决方案,或者没有解决方案。
我们可以重组代码来做到这一点,但相反,让我们注意,有一个或没有元素是有几个或没有元素的特殊情况;它由列表数据类型捕获,因此[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
然后,当懒惰地探索此列表时,这相当于具有回溯的深度优先搜索。
现在代码更加清晰,因此我们终于可以开始看到搜索修剪的新机会,例如保留当前拾取元素的总和,在运行总数已经超过目标时更早地中止徒劳的分支;或者当我们已经有三个元素时停止选择新元素;等等。
共同的主题是,逐步推进我们的知识,以便我们在旅程的每个点上都有一些部分的知识,而不是盲目地做出选择,只在最后测试它们的有效性。